@inproceedings{71298a99db534000aa05470d38a33355,
title = "The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs",
abstract = "The of a planar graph G is the smallest number of line segments needed for a planar straight-line drawing of G. Dujmovi{\'c}, Eppstein, Suderman, and Wood [CGTA{\textquoteright}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{\'c} 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.",
keywords = "Lower/upper bounds, Segment number, Visual complexity",
author = "Ina Goe{\ss}mann and Jonathan Klawitter and Boris Klemz and Felix Klesen and Stephen Kobourov and Myroslav Kryven and Alexander Wolff and Johannes Zink",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022 ; Conference date: 22-06-2022 Through 24-06-2022",
year = "2022",
doi = "10.1007/978-3-031-15914-5\_20",
language = "English (US)",
isbn = "9783031159138",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "271--286",
editor = "Bekos, \{Michael A.\} and Michael Kaufmann",
booktitle = "Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers",
address = "Germany",
}