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.00287
Drawing Unordered Trees on k-Grids
Christian Bachmaier and Marco Matzeder
Vol. 17, no. 2, pp. 103-128, 2013. Regular paper.
Abstract We present almost linear area bounds for drawing trees on the octagonal grid. For complete 7-ary trees we establish an upper and lower bound of Θ(n1.129) and for complete ternary trees the bounds of O(n1.048) and Θ(n), where the latter needs edge bends. For arbitrary ternary trees we obtain an upper bound of O(n log log n) with bends and good aspect ratio by applying the recursive winding technique. We explore the unit edge length and area complexity of drawing unordered trees on k-grids with k∈{4,6,8} and generalize the NP-hardness results of the orthogonal grid to the octagonal and hexagonal grids.
Submitted: April 2012.
Reviewed: July 2012.
Revised: August 2012.
Accepted: December 2012.
Final: December 2012.
Published: January 2013.
Communicated by Shin-ichi Nakano
article (PDF)
BibTeX