A Note on Minimum-Segment Drawings of Planar Graphs
Vol. 17, no. 3, pp. 301-328, 2013. Regular paper.
Abstract A straight-line drawing of a planar graph G is a planar drawing of G such that each vertex is mapped to a point on the Euclidean plane, each edge is drawn as a straight line segment, and no two edges intersect except possibly at a common endpoint. A segment in a straight-line drawing is a maximal set of edges that form a straight line segment. A k-segment drawing of G is a straight-line drawing of G such that the number of segments is at most k. A plane graph is a fixed planar embedding of a planar graph. In this paper we prove that it is NP-hard to determine whether a plane graph G with maximum degree four has a k-segment drawing, where k ≥ 3. The problem remains NP-hard when the drawing is constrained to be convex. We also prove that given a partial drawing Γ of a plane graph G, it is NP-hard to determine whether there exists a k-segment drawing of G that contains all the segments specified in Γ, even when G is outerplanar. The problem remains NP-hard for planar graphs with maximum degree three in R3 when given subsets of the vertices are restricted to be coplanar. Finally, we investigate a worst-case lower bound on the number of segments required by straight-line drawings of arbitrary spanning trees of a given planar graph.
Submitted: August 2012.
Reviewed: March 2013.
Revised: May 2013.
Accepted: June 2013.
Final: June 2013.
Published: June 2013.
Communicated by Giuseppe Liotta
article (PDF)