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 , pp. 320-331(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_30).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_30
Classifications: Z Theory > Z.999 Others
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.900 Tree
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/293

Actions (login required)

View Item View Item