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.
Users
Please
log in to take part in the discussion (add own reviews or comments).