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.

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
ID Code:293

Repository Staff Only: item control page

References

T. Chan, M. Goodrich, S. Rao Kosaraju, and R. Tamassia. Optimizing area and aspect ratio in straight-line orthogonal tree drawings. Comput. Geom. Theory Appl. to appear. Prel. version in Proc. Graph Drawing '96, LNCS, vol. 1190, pp. 63-75.

P. Crescenzi, G. Di Battista, and A. Piperno. A note on optimal area algorithms for upward drawings of binary trees. Comput. Geom. Theory Appl., 2:187-200, 1992.

P. Crescenzi, P. Penna, and A. Piperno. Linear-area upward drawings of AVL trees. Comput. Geom. Theory Appl., 9:25-42, 1998.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

A. Garg, M.T. Goodrich, and R.Tamassia. Planar upward tree drawings with optimal area. Internat. J. Comput. Geom. Appl., 6:333-356, 1996.

C.E. Leiserson. Area-efficient graph layouts (for VLSI). In Proc. 21st Annu. IEEE Sympos. Found. Comput. Sci., pages 270-281, 1980.

C.-S. Shin, S.K. Kim, S.-H. Kim, and K.-Y. Chwa. Area-efficient algorithms for straight-line tree drawings. Comput. Geom. Theory Appl., 15:175-202, 2000.

L. Trevisan. A note on minimum-area upward drawing of complete and Fibonacci trees. Inform. Process. Lett., 57(5):231-236, 1996.

L. Valiant. Universality consierations in VLSI circuits. IEEE Trans. Comput., C-30(2):135-140, 1981.