Three Dimensional Drawings of Bounded Degree Trees

Frati, Fabrizio and Di Battista, Giuseppe (2007) Three Dimensional Drawings of Bounded Degree Trees. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 89-94 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_10).

Full text not available from this repository.

Abstract

We show an algorithm for constructing 3D straight-line drawings of balanced constant degree trees. The drawings have linear volume and optimal aspect ratio. As a side effect, we also give an algorithm for constructing 2D drawings of balanced constant degree trees in linear area, with optimal aspect ratio and with better angular resolution with respect to the one of [8]. Further, we present an algorithm for constructing 3D poly-line drawings of trees whose degree is bounded by n^{1/3} in linear volume and with optimal aspect ratio.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_10
Classifications:M Methods > M.900 Tree
P Styles > P.060 3D
ID Code:764

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.

R. F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199-208, 1997.

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. Prentice Hall, Upper Saddle River, NJ, 1999.

S. Felsner, G. Liotta, and S. K. Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl., 7(4):363-398, 2003.

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

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.

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