Symmetric Drawings of Trees in Three Dimensions



Seok-Hee Hong and Peter Eades, Drawing Trees Symmetrically in Three Dimensions, Algorithmica, Vol. 36, No. 2, pp. 153-178, 2003.

Symmetric graph drawing enables a clear understanding of the structure of the graph. Previous work on symmetric graph drawing has focused on two dimensions. Symmetry in three dimensions is much richer than that of two dimensions. This is the first paper to extend symmetric graph drawing into three dimensions. More specifically, the paper investigates the problem of drawing trees symmetrically in three dimensions. First, we suggest a model for drawing trees symmetrically in three dimensions. Based on this model, we present a linear time algorithm for finding the maximum number of three-dimensional symmetries in trees. We also present a three-dimensional symmetric drawing algorithm for trees.


Seok-Hee Hong and Peter Eades, An Algorithm for Finding Three Dimensional Symmetry in Trees, Proceeding of Graph Drawing 2000, Lecture Notes in Computer Science 1984, Springer, pp. 360-371, 2000.

This paper presents a model for drawing trees symmetrically in three dimensions and a linear time algorithm for nding maximum number of three dimensional symmetries in trees.

For Viewing large drawings, pls click the drawings.
To see the animated drawing, pls click Animated Gif.
To see the AVI movie, pls click AVI.
To view the VRMLFiles, pls download the CosmoPlayer.
Pictures are produced by Oliver Mather.

 
Pyramid configuration : Fig3 (a)
Animated Gif
AVI
VRML
 
Pyramid configuration : Fig3 (b)
Animated Gif
AVI
VRML
 
Pyramid configuration : Fig3 (c)
Animated Gif
AVI
VRML
 
Prism configuration : Fig4 (a)
Animated Gif
AVI
VRML
 
Prism configuration : Fig4 (b)
Animated Gif
AVI
VRML
 
Prism configuration : Fig4 (c)
Animated Gif
AVI
VRML
 
Cube configuration : Fig1 (b)
Animated Gif
AVI
VRML
 
Cube configuration : Fig5
Animated Gif
AVI
VRML
 
Pyramid with no fixed subtree
Animated Gif
AVI
VRML