Logo

Login | Create Account

Three Dimensional Drawings of Bounded Degree Trees

Frati, Fabrizio and Di Battista, Giuseppe (2007) Three Dimensional Drawings of Bounded Degree Trees. [Conference Paper]

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
Classifications:M Methods > M.900 Tree
P Styles > P.060 3D
ID Code:764
Deposited By:GDEA, Administration
Deposited On:04 May 2007
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springer.com/dal/home/computer/lncs?SGWID=1-164-22-173721109-0

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.

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.