Tree Visualisations – Summary
August 8, 2011 § Leave a comment
An interesting class, covering an introduction to trees (and terminology).
The Tidier Drawing Algorithm was presented which assigns layers according to depths, and works by postorder traversal (determining horizontal displacement from parent), followed by pre-order traversal (computing x-coordinates). During postorder traversal, left and right contours are utilized to prevent overlaps, this is linear time (as we following the Minimum heights of trees). TDA takes up O(n^2) area. A property of TDA’s are that axially isomorphic subtrees have congruent drawings up to a translation and a reflection in the y-axis. Width can also be optimized, and it can also be generalized to rooted trees.
Radial Drawings (where layers are represented by concentric circles) are used for ‘Free Trees’ where the center (minimum distance to all other nodes) is a root. (Variants include choice of root, radii of circles and size of wedges). They can be used to display Symmetry. Radial drawings have a linear running time.
Binary trees can also be represented as a hv-drawing. A variation is the Right-Heavy-HV-Tree-Draw, where subtrees with the larger number of vertices are placed to the right. Though this has a good area O(nlogn), it has a bad aspect ratio. Aspect Ration can be improved with horizontal / vertical combinations for odd / even depths. (Through dynamic programming, hv-drawings can be constructed for a general binary tree in O(n^2) time).
These are but a few of the many different tree visualisation methods:
- Tidier Drawing Algorithm
- Radial Drawings
- Indented Layout
- Radial Dendrogram
- Hyperbolic Tree Browser (2D/3D)
- Balloon Tree Drawing
- Space-Filling Tree Layout
- Variations of Treemap (Cushion, Voronoi)
- Icicle Trees (Adjacency Diagram)
- Information Slice and Sunburst Diagrams
- Space-Filling by Circle Packing
- Cone Tree
- Polyphone (2.5D Tree Visualisation)
- Phyllo Tree
- Beam Tree
- Botanical Tree
- Collapsible Cylindrical Trees