Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00295
A Note on MinimumSegment Drawings of Planar Graphs
Vol. 17, no. 3, pp. 301328, 2013. Regular paper.
Abstract A straightline 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 straightline drawing is a maximal set of edges that form a straight line segment. A ksegment drawing of G is a straightline 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 NPhard to determine whether a plane graph G with maximum degree four has a ksegment drawing, where k ≥ 3. The problem remains NPhard when the drawing is constrained to be convex. We also prove that given a partial drawing Γ of a plane graph G, it is NPhard to determine whether there exists a ksegment drawing of G that contains all the segments specified in Γ, even when G is outerplanar. The problem remains NPhard for planar graphs with maximum degree three in R^{3} when given subsets of the vertices are restricted to be coplanar. Finally, we investigate a worstcase lower bound on the number of segments required by straightline 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
