论文标题
绘制外部1平面图进行了重新审视
Drawing outer-1-planar graphs revisited
论文作者
论文摘要
在最近的一篇文章（Auer等人，Algorithmica 2016）中，据称每个外部1平面图都具有面积$ O（n \ log n）$的平面可见性表示。在本文中，我们表明这是错误的：有一些外部1平面图在任何平面图中都需要$ω（n^2）$区域。然后Wegive构造（使用交叉，但保留给定的外1平面嵌入），从而导致与O（n log N）区域的正交盒绘制，并且每个边缘最多有两个弯曲。
In a recent article (Auer et al, Algorithmica 2016) it was claimed that every outer-1-planar graph has a planar visibility representation of area $O(n\log n)$. In this paper, we show that this is wrong: There are outer-1-planar graphs that require $Ω(n^2)$ area in any planar drawing. Then wegive a construction (using crossings, but preserving a given outer-1-planar embedding) that results in an orthogonal box-drawing with O(n log n) area and at most two bends per edge.
