Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002
DOI: 10.7155/jgaa.00086
Straightline Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio
Vol. 8, no. 2, pp. 135160, 2004. Regular paper.
Abstract Trees are usually drawn planar, i.e. without any edgecrossings.
In this paper, we investigate the area requirement of (nonupward) planar straightline grid
drawings of binary trees.
Let T be a binary tree with n nodes.
We show that T admits a planar straightline grid drawing with area
O(n) and with any prespecified aspect ratio in the range [n^{−ϵ},n^{ϵ}], where ϵ is any constant, such that 0 < ϵ < 1. We also show that such a drawing can be
constructed in O(nlogn) time. In particular, our result shows
that optimal area (equal to O(n)) and optimal aspect ratio (equal to 1)
are simultaneously achievable for such drawings.
