%0 Generic %1 goemann2022segment %A Goeßmann, Ina %A Klawitter, Jonathan %A Klemz, Boris %A Klesen, Felix %A Kobourov, Stephen %A Kryven, Myroslav %A Wolff, Alexander %A Zink, Johannes %D 2022 %K graph_theory visual_complexity %T The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs %U https://arxiv.org/abs/2202.11604v3 %X 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 K4) 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.

@misc{goemann2022segment, abstract = {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 K4) 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. }, added-at = {2024-03-01T09:05:51.000+0100}, archiveprefix = {arXiv}, author = {Goeßmann, Ina and Klawitter, Jonathan and Klemz, Boris and Klesen, Felix and Kobourov, Stephen and Kryven, Myroslav and Wolff, Alexander and Zink, Johannes}, biburl = {https://www.bibsonomy.org/bibtex/2c209dacfa28ebd467dedb22a9c27a8a3/tabularii}, description = {[2202.11604v3] The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs}, eprint = {2202.11604}, interhash = {0bba80a9d168282823f6099fe80a1a4b}, intrahash = {c209dacfa28ebd467dedb22a9c27a8a3}, keywords = {graph_theory visual_complexity}, primaryclass = {cs.CG}, timestamp = {2024-03-01T09:05:51.000+0100}, title = {The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs}, url = {https://arxiv.org/abs/2202.11604v3}, year = 2022 }