TY - GEN
T1 - The Segment Number
T2 - 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022
AU - Goeßmann, Ina
AU - Klawitter, Jonathan
AU - Klemz, Boris
AU - Klesen, Felix
AU - Kobourov, Stephen
AU - Kryven, Myroslav
AU - Wolff, Alexander
AU - Zink, Johannes
N1 - Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - The 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.
AB - The 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.
KW - Lower/upper bounds
KW - Segment number
KW - Visual complexity
UR - http://www.scopus.com/inward/record.url?scp=85140761715&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85140761715&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-15914-5_20
DO - 10.1007/978-3-031-15914-5_20
M3 - Conference contribution
AN - SCOPUS:85140761715
SN - 9783031159138
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 271
EP - 286
BT - Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers
A2 - Bekos, Michael A.
A2 - Kaufmann, Michael
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 22 June 2022 through 24 June 2022
ER -