English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The segment number of a planar graph $G$ is the smallest number of linesegments needed for a planar straight-line drawing of $G$. Dujmovi\'c,Eppstein, Suderman, and Wood [CGTA'07] introduced this measure for the visualcomplexity of graphs. There are optimal algorithms for trees and worst-caseoptimal algorithms for outerplanar graphs, 2-trees, and planar 3-trees. It isknown that every cubic triconnected planar $n$-vertex graph (except $K_4$) hassegment number $n/2+3$, which is the only known universal lower bound for ameaningful class of planar graphs.  We show that every triconnected planar 4-regular graph can be drawn using atmost $n+3$ segments. This bound is tight up to an additive constant, improves aprevious upper bound of $7n/4+2$ implied by a more general result of Dujmovi\'cet al., and supplements the result for cubic graphs. We also give a simpleoptimal algorithm for cactus graphs, generalizing the above-mentioned resultfor trees. We prove the first linear universal lower bounds for outerpaths,maximal outerplanar graphs, 2-trees, and planar 3-trees. This shows that theexisting algorithms for these graph classes are constant-factor approximations.For maximal outerpaths, our bound is best possible and can be generalized tocircular arcs.

The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs