Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00196 Cubic graphs have bounded slope parameter Balázs Keszegh , János Pach , Dömötör Pálvölgyi , and Géza Tóth 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.
|
Accepted: November 2009. Published: January 2010. Submitted: October 2008. Revised: August 2009. Final: November 2009. Reviewed: July 2009. Communicated by Ioannis Tollis and Maurizio Patrignani |
Journal of Graph Algorithms and Applications |