Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings

Chan, Timothy and Goodrich, Michael T. and Kosaraju, Rao and Tamassia, Roberto (1997) Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 63-75 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_38).

Full text not available from this repository.

Abstract

We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspekt ratio to be chosen as being O(1) or sometimes even an arbitrary parameter. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". We investigate both upward and non-upward drawings, achieving area bounds of O(nlogn) and O(nloglogn), respectively, and we show that, at least in the case of upward drawings, our area bound is optimal to within constant factors.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_38
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.070 Area / Edge Length
D Aesthetics > D.999 Others
M Methods > M.900 Tree
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:66

Repository Staff Only: item control page

References

R. P. Brent and H. T. Kung. On the area of binary tree layouts. Inform. Process. Lett., 11:521-534, 1980.

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 and A. Piperno. Optimal-area upward drawings of AVL trees. In R. Tamassia and I. G. Tollis, editors, Graph Drawing (GD '94), LNCS 894, Springer-Verlag, pp. 307-317, 1995.

G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis, Algorithms for automatic graph drawing: an annotated bibliography, Computational Geom. Theory Appl. 4, pp. 235-282, 1994.

A. Garg, M. Goodrich and R. Tamassia. Area-efficient upward tree drawings. In Proc. 9th Annu. ACM Symp. Comput. Geom., pp. 359-368, 1993.

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

C. E. Leiserson. Area-efficient graph layouts (for VLSI). ACM Doctoral Dissertation Award Series. MIT Press, Cambridge, MA, 1983.

E. Reingold and J. Tilford. Tidier drawing of trees. IEEE Trans. Software Eng., SE-7(2):223-228, 1976.

Y. Shiloach. Arrangements of Planar Graphs on the Planar Lattice. PhD thesis, Weizmann Institute of Science, 1976.

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

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