论文标题
段编号：某些类别的平面图的算法和通用下限
The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs
论文作者
论文摘要
平面图$ g $的段数是$ g $的平面直线图所需的最小线段。 Dujmović，Eppstein，Suderman和Wood [CGTA'07]引入了该图表的视觉复杂性。有针对树木的最佳算法和最佳案例的最佳算法，用于外平面图，2树和平面3树。众所周知，每个立方三合一的平面$ n $ vertex图（$ k_4 $除外）都有段编号$ n/2+3 $，这是一类有意义的平面图唯一已知的通用下限。 我们表明，最多可以使用$ n+3 $段来绘制每个三连电4型图4的平面图。该界限紧密至添加剂常数，改善了Dujmović等人更普遍的结果所隐含的$ 7N/4+2 $的上限，并为立方图提供了结果。我们还为仙人掌图提供了一种简单的最佳算法，从而概括了树木的上述结果。我们证明了外部路径，最大外平面图，2树和平面3树的第一个线性通用下限。这表明这些图形类的现有算法是恒定因素近似值。对于最大的外部路径，我们的界限是最好的，并且可以推广到圆弧。
The segment number of a planar graph $G$ is the smallest number of line segments needed for a planar straight-line drawing of $G$. Dujmović, Eppstein, Suderman, and Wood [CGTA'07] introduced this measure for the visual complexity of graphs. There are optimal algorithms for trees and worst-case optimal algorithms for outerplanar graphs, 2-trees, and planar 3-trees. It is known that every cubic triconnected planar $n$-vertex graph (except $K_4$) has segment number $n/2+3$, which is the only known universal lower bound for a meaningful class of planar graphs. We show that every triconnected planar 4-regular graph can be drawn using at most $n+3$ segments. This bound is tight up to an additive constant, improves a previous upper bound of $7n/4+2$ implied by a more general result of Dujmović et al., and supplements the result for cubic graphs. We also give a simple optimal algorithm for cactus graphs, generalizing the above-mentioned result for trees. We prove the first linear universal lower bounds for outerpaths, maximal outerplanar graphs, 2-trees, and planar 3-trees. This shows that the existing algorithms for these graph classes are constant-factor approximations. For maximal outerpaths, our bound is best possible and can be generalized to circular arcs.
