Home  Issues  Aims and Scope  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 LineSets for Drawing Planar 3Trees
Vol. 17, no. 2, pp. 5979, 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 straightline 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 3trees with n vertices. In both cases we give lineartime algorithms to find such drawings. A byproduct of our algorithm is the generalization of the known bijection between plane 3trees and rooted full ternary trees to the bijection between planar 3trees and unrooted full ternary trees. We also identify some subclasses of planar 3trees 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
Shinichi Nakano
