Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Sixteenth International Symposium on Graph Drawing, GD 2008
DOI: 10.7155/jgaa.00196
Cubic graphs have bounded slope parameter
Vol. 14, no. 1, pp. 5-17, 2010. Regular paper.
Abstract We show that every finite connected graph G with maximum degree three and with at least one vertex of degree smaller than three has a straight-line drawing in the plane satisfying the following conditions. No three vertices are collinear, and a pair of vertices form an edge in G if and only if the segment connecting them is parallel to one of the sides of a previously fixed regular pentagon. It is also proved that every finite graph with maximum degree three permits a straight-line drawing with the above properties using at most seven different edge slopes.
Submitted: October 2008.
Reviewed: July 2009.
Revised: August 2009.
Accepted: November 2009.
Final: November 2009.
Published: January 2010.
Communicated by Ioannis G. Tollis and Maurizio Patrignani
article (PDF)
BibTeX