A Note on Minimum-Segment Drawings of Planar Graphs

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 R³ 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.