Optimal-area upward drawings of AVL trees (Extended abstract)

Crescenzi, P. and Piperno, A. (1995) Optimal-area upward drawings of AVL trees (Extended abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 307-317 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_386).

Full text not available from this repository.

Abstract

We prove that any AVL tree admits a linear-area planar straight-line grid strictly-upward drawing, that is, a drawing in which (a) no two edges intersect, (b) each edge is mapped into a single straight-line segment, (c) each node is mapped into a point with integer coordinates, and (d) each node is placed below its parent.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_386
Classifications:P Styles > P.840 Upward
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:200

Repository Staff Only: item control page

References

G.M. Adelson-Velskii and E.M. Landis. An algorithm for the organization of information. Soviet Math. Dokl., 3:1259-1262, 1962.

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

G. Di Battista, P.Eades, and R. Tamassia. Algorithms for drawing graphs: an annotated bibliography. Computational Geometry: Theory and Applications, to appear. A preliminary version is available via anonymous ftp from wilma.cs.brown.edu, gdbiblio.tex.Z and gdbiblio.ps.Z in /pub/papers/compgeo.

P. Eades, T. Lin, and X. Lin. Minimum size h-v drawings. In Proc. Int. Workshop AVI '92, pages 386-394, 1992.

Y. Horibe. An Entropy View of Fibonacci Trees. Fibonacci Quarterly, 20:168-178, 1982.

Y. Horibe. Notes on Fibonacci Trees and Their Optimality. Fibonacci Quarterly, 21:118-128, 1983.

D.E. Knuth. The Art of Computer Programming, Addison Wesley, 1975.

A. Garg, M.T. Goodrich, and R. Tamassia. Area-efficient upward tree drawing. In Proc. ACM Symp. on Computational Geometry, pages 359-368, 1993.

R.L. Graham, D.E. Knuth, and O. Patashnik. Concrete Mathematics, Addison Wesley, 1989.

E. Reingold and J. Tilford. Tidier drawing of trees. IEEE Trans. on Software Engineering, SE-7:223-228, 1981.

K.J. Supowit and E. Reingold. The complexity of drawing trees nicely. Acta Informatica, 18:377-392, 1983.