Straight-Line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio (Extended Abstract)
Garg, Ashim and Rusu, Adrian (2002) Straight-Line Drawings of Binary Trees with Linear Area and Arbitrary Aspect Ratio (Extended Abstract). In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 320-331 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_30).
Full text not available from this repository.
Trees are usually drawn planar, i.e. without any crossings. In this paper, we investigate the area requirement of (non-upward) planar straight-line grid drawings of binary trees. Let T be a binary tree with n nodes. We show that T admits a planar straight-line grid drawing with area O(n) and with any pre-specified aspect ratio in the range [1,n^\alpha], where \alpha is a constant such that 0 \leq \alpha < 1. We also show that such a drawing can be constructed in O(n log n) time.
Repository Staff Only: item control page