论文标题
关于平面贪婪图纸的面积要求
On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs
论文作者
论文摘要
在本文中，我们研究了平面平面图的平面贪婪图纸的面积要求。 CAO，Strelzoff和Sun展示了三连电平面图的分区的家庭$ \ cal h $，并声称符合处方飞机嵌入的$ \ Mathcal H $中图形的每个平面贪婪绘图都需要指数面积。但是，我们表明，$ \ cal H $中的每个$ n $ vertex图实际上都有一个平面贪婪的图纸，符合嵌入$ o（n）\ times o（n）$ grid上的规定的平面。这重新打开了一个问题，即三核平面图是否在多项式大小的网格上录入平面贪婪图纸。此外，我们通过证明每$ n $ vertex halin Graph在$ o（n）\ times o（n）$ grid上承认平面贪婪的绘画，从而为上述问题提供了积极答案的证据。这两种结果都是通过实际构造凸和角度 - 单酮的图纸来获得的。最后，我们考虑$α$ -Schnyder图纸，如果$α\ leq 30^\ circ $，则是贪婪的，因此是贪婪的，并表明存在平面三角形的三角形，每个$α$ -Schnyder绘制都有固定的$α<60^\ Circ $需要任何解决方案的指示面积。
In this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family $\cal H$ of subdivisions of triconnected plane graphs and claimed that every planar greedy drawing of the graphs in $\mathcal H$ respecting the prescribed plane embedding requires exponential area. However, we show that every $n$-vertex graph in $\cal H$ actually has a planar greedy drawing respecting the prescribed plane embedding on an $O(n)\times O(n)$ grid. This reopens the question whether triconnected planar graphs admit planar greedy drawings on a polynomial-size grid. Further, we provide evidence for a positive answer to the above question by proving that every $n$-vertex Halin graph admits a planar greedy drawing on an $O(n)\times O(n)$ grid. Both such results are obtained by actually constructing drawings that are convex and angle-monotone. Finally, we consider $α$-Schnyder drawings, which are angle-monotone and hence greedy if $α\leq 30^\circ$, and show that there exist planar triangulations for which every $α$-Schnyder drawing with a fixed $α<60^\circ$ requires exponential area for any resolution rule.
