Tree Drawing Algorithms and Visualization Methods : Tree Drawing Algorithms and Visualization Methods Kai (Kevin) Xu
Slide2 : Course website:
http://www.cs.usyd.edu.au/~visual/comp4048/
Assignments:
Paper presentation
Visualization project
Outline : Outline Tree drawing algorithms
Tree visualisation
Tree Drawing Algorithm : Tree Drawing Algorithm Terminology
Layered Drawing
Radial Drawing
HV-Drawing
Recursive Winding
Terminology : Terminology Tree:
Acyclic graph
Rooted tree
Root: a distinguished vertex in tree
Usually treated as a directed graph: all edges oriented away from the root
Direct edge u->v: u is the parent of v and v is the child of u
Leaf: no child
Ordered tree: rooted tree with an ordering for the children of every vertex
Terminology : Terminology Binary tree: rooted tree with every node has at most two children
Left and right child
One child, either left or right
Subtree rooted at v: the subgraph induced by all vertices that have v as their “ancestor”
Binary tree: left and right subtree
Depth of a vertex: number of edges between it and the root
Height of a tree: maximum depth
Tree Drawing Algorithm : Tree Drawing Algorithm Terminology
Layered Drawing
Radial Drawing
HV-Drawing
Recursive Winding
A Rather Simple Layering Algorithm : A Rather Simple Layering Algorithm Placing vertex with depth i into layer Li
Root in the top layer L0.
y-coordinate decided.
Ordering vertices in each layer
Keep the left-right order of two vertices the same as their parents to avoid crossings.
Compute the x-coordinate.
Requirement 1: placing the parent in the horizontal span of its children (possibly in a central position).
Requirement 2: sometimes the ordering of the children is fixed.
Horizontal coordinate assignment : Horizontal coordinate assignment Solution 1: using in-order traversal
Set the x-coordinate as vertex rank in in-order traversal
Problems:
Much wider than necessary
Parent is not centered with respect to children
An Improved Layered Tree Drawing Algorithm : An Improved Layered Tree Drawing Algorithm Divide and conquer
Divide step:
recursively apply the algorithm to draw the left and right subtrees of T.
Conquer step:
move the drawings of subtrees until their horizontal distance equals 2.
place the root r vertically one level above and horizontally half way between its children.
If there is only one child, place the root at horizontal distance 1 from the child.
Layered Drawing: Binary Tree : Layered Drawing: Binary Tree Two traversals
step 1. post-order traversal
For each vertex v, recursively computes the horizontal displacement of the left & right children of v with respect to v.
step 2. pre-order traversal
Computes x-coordinates of the vertices by accumulating the displacements on the path from each vertex to the root.
Post-Order Traversal : Post-Order Traversal left (right) contour: the sequence of vertices vi such that vi is the leftmost (rightmost) vertex of T with depth i
After we process v, we maintain the left and right contour of the subtree rooted at v as a linked list.
In the conquer step, we need to follow the right contour of the left subtree and the left contour of the right subtree
Left and Right Contour of Subtree : Left and Right Contour of Subtree Compute the left and right contour of vertex v:
scan the right contour of the left subtree (T’) and the left contour of the right subtree (T’’ )
accumulate the displacements of the vertices on the left & right contour
keep the max cumulative displacement at any depth
Three cases:
case 1: height(T’) = height(T’’)
case 2: height(T’) < height(T’’)
case 3: height(T’) > height(T’’)
Left and Right Contour of Subtree : Left and Right Contour of Subtree L(T) (R(T)): left (right) contour of the subtree T rooted at v
case 1: height(T’) = height(T’’)
L(T) = L(T’) + v
R(T) = R(T’’) + v
case 2: height(T’) < height(T’’)
R(T) = R(T’’) + v
L(T) = v+ L(T’) + {part of L(T’’) starting from w}
h’: depth of T’
w: the vertex on L(T’’) whose depth = h’+1
case 3: height(T’) > height(T’’) : similar to case2
Layered Drawing : Layered Drawing Two traversals
step 1. post-order traversal
step 2. pre-order traversal
Computes x-coordinates of the vertices by accumulating the displacements on the path from each vertex to the root.
Time Complexity : Time Complexity Pre-order traversal (step 2):
linear
Post-order traversal (step 1):
Linear, but why?
it is necessary to travel down the contours of two subtrees T’ and T’’ only as far as the height of the subtree of lesser height
the time spent processing vertex v in the post-order traversal is proportional to the minimum heights of T’ and T”
The sum is no more than the number of vertices of the tree
Can be visualized by connecting vertices with same depth
Hence, the algorithm runs in linear time
Drawing Width and Area : Drawing Width and Area Local horizontal compaction at each conquer step does not always compute a drawing of minimal width
can be solved in polynomial time using linear programming
Area:
O(n2)
Generalization : Generalization generalization to rooted trees
reasonable drawing
root is placed at the average x-coordinates of its children
small imbalance problem:
The picture show the result when the algorithm works from left to right.
Tree Drawing Algorithm : Tree Drawing Algorithm Terminology
Layered Drawing
Radial Drawing
HV-Drawing
Recursive Winding
Radial Drawing : Radial Drawing A variation of layered drawing
Root at the origin
Layers are concentric circles centered at the origin
Usually draw each subtree in an annulus wedge W
Wedge Angle : Wedge Angle Choose wedge angle to be proportional to the leave number in the subtree
Problem: edge intersecting with level circle
Wedge angle : Wedge angle To guarantee planarity, define convex subset F of the wedge.
The tangent to circle ci through v meet circle ci+1 at a and b
The unbounded region F formed by the line segment ab and the rays from origin through a and b is convex
The final wedge angle is the lesser between the angle of F and angle proportional to number of leaves.
Time and Area : Time and Area Time:
Linear
Area
Polynomial
Equal distance between circles
Tree height: h
Maximum child number: dM
Area:
O(h2dM2)
First circle has perimeter as least dM (minimum distance between two vertices is 1)
It’s radius is O(dM)
The radius of final circle is O(hdM)
Radial Drawing : Radial Drawing Used for free trees (tree without a root)
Select a root minimize tree height
Can be found in linear time using simple recursive leaf pruning algorithm
One or two centers
Variations:
choice of root,
radii of the circles,
how to determine the wedge angle
Tree Drawing Algorithm : Tree Drawing Algorithm Terminology
Layered Drawing
Radial Drawing
HV-Drawing
Recursive Winding
HV-Drawing – Binary Tree : HV-Drawing – Binary Tree HV-drawing of a binary tree T: straight-line grid drawing such that for each vertex u, a child of u is either
horizontally aligned with and to the right of u, or vertically aligned with and below u
the bounding rectangles of the subtrees of u do not intersect
Planar, straight-line, orthogonal, and downward
Divide & Conquer Method : Divide & Conquer Method Divide: recursively construct hv-drawings for the left & right subtrees
Conquer: perform either
a horizontal combination or
a vertical combination
The height & width are each at most n-1
Right-Heavy-HV-Tree-Drawing : Right-Heavy-HV-Tree-Drawing 1. Recursively construct drawing of the left & right subtrees
2. Using only horizontal combination, place the subtree with the largest number of vertices to the right of the other one. height of the drawing is at most logn
Right-Heavy-HV-Tree-Drawing : Right-Heavy-HV-Tree-Drawing HV-drawing (downward, planar, grid, straight-line and orthogonal)
Width is at most
n-1
Height is at most
logn
The larger subtree is always placed to the right
The size of parent subtree is at least twice the size of vertical child subtree
area O(nlogn)
Area-Aspect Ratio : Area-Aspect Ratio Right-Heavy-HV-Tree-Draw
Good area bound, but bad aspect ratio
Better aspect ratio:
use both vertical and horizontal combinations
Alternating the combination
Odd level: horizontal, even level: vertical
O(n) area and constant aspect ratio
Optimization and Extension : It is possible to construct an HV-drawing of a binary tree that is optimal with respect to area or perimeter in O(n2) time.
Use dynamic programming approach
Right-Heavy-HV-Tree-Drawing can be extended to general rooted tree
Downward, planar, grid, straight-line
Area O(nlogn)
Width is at most n-1
Height is at most logn Optimization and Extension
Tree Drawing Algorithm : Tree Drawing Algorithm Terminology
Layered Drawing
Radial Drawing
HV-Drawing
Recursive Winding
Recursive Winding : Recursive Winding Similar to HV-drawing
For binary tree
Produce planar downward straight-line grid drawing
Constant aspect ratio
Almost linear area
Recursive Winding : Recursive Winding Input: a binary tree with n vertices and l leaves.
n=2l-1
For a vertex v:
left(v): left child; right(v): right child
T(v): subtree rooted at v
l(v): number of leaves in T(v)
Recursive winding tree drawing
H(l): height of the drawing of T with l leaves
W(l): width of the drawing of T with l leaves
t(l): running time
Recursive Winding Tree Drawing : Recursive Winding Tree Drawing Arrange the tree so that l(left(v)) ≤ l(right(v)) at every vertex v;
Give a parameter A>1,if l≤A, then draw the tree using right-heavy-HV-tree;
H(l) ≤log2l, W(l)≤A, and t(l)=O(A);
If l>A, define a sequence {vi}: v1 is the root and vi+1=right(vi) for i=1,2,…;
Let k≥1 be an index with l(vk)>l-A and l(vk+1)≤ l-A.
Such a k can be found in O(k) time, since l(v1), l(v2), … is a strictly decreasing order
Recursive Winding Tree Drawing : Recursive Winding Tree Drawing Let Ti=T(left(vi)) and li=l(left(vi)) for i=1,…,k-1
Let T’=T(left(vk)), T’’=T(right(vk)), l’=l(left(vk)), and l’’=l(right(vk))
Note that
l’≤ l’’, since T is right heavy
l1 + … + lk-1 = l - l(vk) < A
Max{l’,l’’}= l(vk+1)≤ l-A … vk T’ T’’
Recursive Winding Tree Drawing : Recursive Winding Tree Drawing If k=1, T’ and T’’ are drawn recursively below v1;
If k=2, T1 is drawn with right-heavy-HV-tree, while T’ and T’’ are drawn recursively;
If k=3, T1,…Tk-2 are drawn from left to right with right-heavy-HV-tree. Tk-1 is drawn right-heavy-HV-tree and then reflected around y-axis and rotated by π/2. T’ and T’’ are drawn recursively below and then reflected around y-axis so that their roots are placed at upper right-hand corners. (This is the “recursive winding”)
Recursive Winding Tree Drawing : Recursive Winding Tree Drawing Bounds:
H(l) ≤ max{H(l’) + H(l’’) + log2A + 3, lk-1-1}
W(l) ≤ max{W(l’) + 1, W(l’’), l1+…+lk-2} + log2lk-1 + 1
t(l) ≤ t(l’) + t(l’’) + O(l1+ … + lk-1 + 1)
Because L1 + … + lk-1 = l-l(vk) < A,
H(l) ≤ max{H(l’) + H(l’’) + O(logA), A}
W(l) ≤ max{W(l’), W(l’’), A} + O(log2A)
t(l) ≤ t(l’) + t(l’’) + O(A)
Because Max{l’,l’’}= l(vk+1)≤ l-A,
W(l) = O(l/A·logA + A)
Recursive Winding Tree Drawing : Recursive Winding Tree Drawing The running time is O(n);
By setting A as A = √(l·log2l), the height and width of the drawing are both O(√nlogn).
An example
Tree Visualization : Tree Visualization While tree drawing algorithm is more theoretical, tree visualization is more applied.
We will see examples of different tree visualization methods.
Indented Layout : Indented Layout Places all items along vertically spaced rows
Uses indentation to show parent child relationships
Example: Windows explorer
Problems:
Only showing part of the tree
Bad aspect ratio (not space efficient)
But still the most popular one!?
Dendrogram : Dendrogram Essentially a layered drawing
with bended orthogonal edges
Layering are done according to the leaves:
All the leaves are on the same layer
Now commonly used in bioinformatics to represent
The result of hierarchical clustering
Phylogenetic trees
More on this in the “biological networks” lecture
Balloon trees : Balloon trees A variation of radial layout
children are drawn in a circle centered at their parents.
Effective on showing the tree structure
At the cost of node details
Hyperbolic Tree : Hyperbolic Tree Simulate the distortion effect of fisheye lens
Enlarge the focus and shrink the rest
Focus+context
Interaction technique; can be combined with different layout.
3D hyperbolic tree:
projecting a graph one a sphere produces a similar distortion effect
This example also uses balloon tree drawing.
3D tree visualization - Cone tree : 3D tree visualization - Cone tree Cone trees are a 3D extension of the 2D layered tree drawing method.
Parent at the tip of a cone, and its children spaced equally on the bottom circle of the cone
Either horizontal or vertical
The extension to 3D does not necessarily means more information can be displayed
Occlusion problem
Couple with interaction is essential
More on this in the “graph visualization evaluation” lecture
Other 3D tree visualizations : Other 3D tree visualizations 3D poly-plane tree visualization
Put subtrees on planes
arrange these planes in 3D to reduce occlusion
In this example, layered drawing is used within each plane
3D layered tree
Only one cone
Layers are the parallel circles on the surface
Example: color indicate the layer
Space-filling methods - Treemap : Space-filling methods - Treemap Treemap use containment to show the hierarchy.
It partitions the space recursively according to the size of subtrees
It is space-efficient compare to node-link diagram
It is effective in showing the leaf nodes; on the other size, it is difficult to see the non-leave nodes
Variations of treemap : Variations of treemap Cushion treemap
Use shading to help identify the levels in a treemap
Voronoi treemap
Similar idea but uses voronoi diagram as partition
The space does not have to be rectangle.
Beamtree : Beamtree A variation of treemap in 3D.
Using overlap instead of nesting to show the hierarchy
3D version: representing each node as a beam
A bigger example
Space-filling tree layout : Space-filling tree layout Try to use as much screen space as possible
Layout a tree according to the recursive partition of the screen space
The area allocated to a subtree is proportional to its size.
A bigger example: 55000 nodes
Use all the screen space
Not very effective on showing the tree structure
Other space filling methods - Icicle Trees : Other space filling methods - Icicle Trees Edges implied by adjacency and spatial relationship.
icicle tree in the infovis toolkit (jean-daniel fekete)
Information slice and Sunburst Diagrams : Information slice and Sunburst Diagrams Information slice
also a space-filling visualization method.
Radial version of icicle trees.
Node size is proportional to the angle swept by a node.
Sunburst
With extra focus+context
Details are shown outside or inside the ring
Elastic hierarchies : Elastic hierarchies hybrid of node-link diagrams and treemaps
Using node-link diagram inside a treemap produces lots of crossings
TreeViewer : TreeViewer Visualizes trees in a form that closely resembles botanical trees
The root is the tree stem
Non-leave nodes are branches
Leave nodes are “bulbs” at the end of branches
Example: Unix home directory.
Collapsible Cylindrical Trees : Collapsible Cylindrical Trees Telescope metaphor: A set of nested cylinders
A cylinder is constructed for the children of a node, and it has a smaller radius.
This cylinder is nested and hidden within the cylinder contain the parent
It can be pulled out to the right of theparent cylinder or collapsed as necessary. only one path of the hierarchy is visible at once
represented by a number of ever decreasing cylinders
All cylinders of level 1 nodes are shown in a horizontal fashion, like being put on a stick.