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 -