Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012
DOI: 10.7155/jgaa.00285
Universal Line-Sets for Drawing Planar 3-Trees
Vol. 17, no. 2, pp. 59-79, 2013. Regular paper.
Abstract A set S of lines is universal for drawing planar graphs with n vertices if every planar graph G with n vertices can be drawn on S such that each vertex of G is drawn as a point on a line of S and each edge is drawn as a straight-line segment without any edge crossing. It is known that ⎣[(2(n−1))/3]⎦ parallel lines are universal for any planar graph with n vertices. In this paper we show that a set of ⎣[(n+3)/2]⎦ parallel lines or a set of ⎡[(n+3)/4]⎤ concentric circles are universal for drawing planar 3-trees with n vertices. In both cases we give linear-time algorithms to find such drawings. A by-product of our algorithm is the generalization of the known bijection between plane 3-trees and rooted full ternary trees to the bijection between planar 3-trees and unrooted full ternary trees. We also identify some subclasses of planar 3-trees whose drawings are supported by fewer than ⎣[(n+3)/2]⎦ parallel lines.
Submitted: April 2012.
Reviewed: August 2012.
Revised: September 2012.
Accepted: December 2012.
Final: December 2012.
Published: January 2013.
Communicated by Shin-ichi Nakano
article (PDF)
BibTeX