Straight-Line Orthogonal Drawings of Binary and Ternary Trees

Frati, Fabrizio (2008) Straight-Line Orthogonal Drawings of Binary and Ternary Trees. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 76-87 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_11).

Full text not available from this repository.

Abstract

In this paper we provide upper and lower bounds on the area requirement of straight-line orthogonal drawings of $n$-node binary and ternary trees. Namely, we show algorithms for constructing order-preserving straight-line orthogonal drawings of binary trees in $O(n^1.5)$ area, straight-line orthogonal drawings of ternary trees in $O(n^1.631)$ area, and straight-line orthogonal drawings of complete ternary trees in $O(n^1.262)$ area. As far as we know, the ones we present are the first algorithms achieving sub-quadratic area for these problems. Further, for upward order-preserving straight-line orthogonal drawings of binary trees and for order-preserving straight-line orthogonal drawings of ternary trees we provide $Omega(n^2)$ area lower bounds, that we also prove to be tight.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_11
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
M Methods > M.900 Tree
P Styles > P.720 Straight-line
ID Code:830

Repository Staff Only: item control page

References

T. M. Chan, M. T. Goodrich, S. Rao Kosaraju, and R. Tamassia. Optimizing area and aspect ratio in straight-line orthogonal tree drawings. Comput. Geom., 23(2):153-162, 2002.

T. M. Chan. A near-linear area bound for drawing binary trees. Algorithmica, 34(1):1-13, 2002.

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

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

D. Dolev and H. W. Trickey. On linear area embedding of planar graphs. Technical report, Stanford, USA, 1981.

A. Garg, M. T. Goodrich, and R. Tamassia. Planar upward tree drawings with optimal area. Int. Comput. Geometry Appl., 6(3):333-356, 1996.

A. Garg and A. Rusu. Area-efficient order-preserving planar straight-line drawings of ordered trees. Int. J. Comput. Geometry Appl., 13(6):487-505, 2003.

A. Garg and A. Rusu. Straight-line drawings of general trees with linear area and arbitrary aspect ratio. In ICCSA (3), pages 876-885, 2003.

S.K. Kim. Simple algorithms for orthogonal upward drawings of binary and ternary trees sung. In CCCG, pages 115-120, 1995.

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

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

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