Logo

Login | Create Account

Straight-Line Orthogonal Drawings of Binary and Ternary Trees

Frati, Fabrizio (2008) Straight-Line Orthogonal Drawings of Binary and Ternary Trees. [Conference Paper]

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
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
Deposited By:GDEA, Administration
Deposited On:24 Jun 2008
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=76

Repository Staff Only: item control page

References

1. 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.

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

3. 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.

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

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

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

7. 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.

8. 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.

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

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

11. 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.

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.