Tree Visualisations – Summary

August 8, 2011 § Leave a comment

Class Notes

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
  • HV-Drawing
  • ——————————
  • Indented Layout
  • Dendrogram
  • Radial Dendrogram
  • Hyperbolic Tree Browser (2D/3D)
  • Balloon Tree Drawing
  • Space-Filling Tree Layout
  • Treemap
  • 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
and many more. A vast amount of which can be found at “A Visual Survey of Tree Visualization“.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Tree Visualisations – Summary at DECO } Han.

meta