INTRODUCTION TO GRAPH DRAWING Fall 2010 Battista, G. D., Eades, P., Tamassia, R., and Tollis, I. G. 1998 Graph Drawing: Algorithms for the Visualization of Graphs. 1st. Prentice Hall PTR. DIVIDE AND CONQUER Rooted tree Layered Drawing: vertices are placed on horizontal layers Radial Drawing: layers are mapped on
concentric circles HV-Drawing: edges are drawn as rightward horizontal or downward vertical segment. Recursive Winding: drawings with constant aspect ratio and small area 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 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
Layered Drawing Radial Drawing HV-Drawing Recursive Winding LAYERING A simple method for constructing downward planar drawing:
Vertex with depth i is placed into layer Li Root placed in the top layer L0 Layered drawing is strictly downward. Vertex v of depth i has y(v) = - i LAYERING In-Order Traversal: Vertex v is j-th vertex encountered in inorder traversal of the tree, then x(v) = j Problems: Much wider than necessary Parent not centered with respect to children
TREE TRAVERSALS SHORT REVIEW In Order: A,B,C,D,E,F,G,H,I Pre Order: F,B,A,D,C,E,G,I,H Post Order: A,C,E,D,B,H,I,G,F LAYERED-TREE-DRAW ALGORITHM input = binary tree T output = layered drawing of T Divide and conquer Reduce width
Horizontally centers parent vertex Yields aesthetically pleasing drawings LAYERED-TREE-DRAW ALGORITHM Base Case: If T has only 1 vertex, drawing is trivially defined Divide: recursively apply algorithm
to draw left and right subtrees of T. Conquer: move drawings of subtrees until horizontal distance = 2. place the root r vertically one level above and horizontally half way between its children. If only one child, place root at horizontal distance 1 from child. LAYERED-TREE-DRAW ALGORITHM Base Case:
If T has only 1 vertex, drawing is trivially defined Divide: recursively apply algorithm to draw left and right subtrees of T. Conquer: move drawings of subtrees until horizontal distance = 2. place the root r vertically one level
above and horizontally half way between its children. If only one child, place root at horizontal distance 1 from child. LAYERED-TREE-DRAW ALGORITHM left contour: Sequence of vertices v0 vh such that vi is the leftmost vertex of T with depth i (right contour is defined similarly) In the conquer step, follow right contour of left subtree and left contour of right subtree
LAYERED-TREE-DRAW ALGORITHM Compute left and right contour of vertex v: scan right contour of left subtree (T) and left contour of right subtree (T ) gather displacements of vertices on the left & right contour keep the max increasing displacement at any depth LAYERED-TREE-DRAW
ALGORITHM L(T) = left contour list R(T) = right contour list 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 LAYERING SUMMARY Time Complexity: Pre order: linear Post order: linear Hence, algorithm runs in linear time. TREE DRAWING ALGORITHM Layered Drawing
Radial Drawing HV-Drawing Recursive Winding RADIAL DRAWING A variation of layered drawing Root at the origin
Layers are concentric circles centered at the origin Vertices of depth i placed on circle Ci 17 RADIAL DRAWING: WEDGE ANGLE Subtree rooted at vertex v
is drawn within annulus wedge W v. It may seem reasonable to choose wedge angle to be proportional to l(v) = number of leavs in the subtree rooted at v This can lead to edge crossings, because edge with endpoints within Wv can extend outside Wv and intersect other edges. 18 RADIAL DRAWING: WEDGE ANGLE Prevent edge crossings - restrict vertices to convex subset of wedge. Suppose: vertex v lies on Ci, tangent to Ci through v meets Ci+1 at a and b. Region Fv is convex. We restrict subtree rooted at v to lie within Fv
Children of v arranged on Ci+1 according to # of leaves in their respective subtrees. More precisely for each child u of v, the angle u of wedge Wu is u = min( [ v * l(u) / l(v)], ) v = angle of Wv, = angle formed by Fv child u is placed on Ci at the center of Wv. 19 TREE DRAWING ALGORITHM Layered Drawing Radial Drawing
HV-Drawing Recursive Winding 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: 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 ALGORITHM *** 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. LEMMAS AND THEOREMS Let T be a binary tree with n vertices, the height of the drawing of T constructed by the Right-Heavy-HVTree-Drawing Algorithm is at most logn. Let T be a binary tree with n vertices, Right-HeavyHV-Tree-Drawing Algorithm construct a drawing of T in O(n) time, such that:
is an hv-drawing The area of is O(nlogn) The width of is at most n-1 The height of is at most logn RIGHT-HEAVY-HV-TREE-DRAWING HV-drawing (downward, planar, grid, straightline 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 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. 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 Largest subtree TREE DRAWING ALGORITHM Layered Drawing Radial Drawing
HV-Drawing Recursive Winding RECURSIVE WINDING Similar to HV-drawing For binary tree Produce planar downward straight-line Tgrid T1 k-2 drawing Constant aspect ratio
T Almost linear area T Tk-1 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 Arrange the tree so that l(left(v)) l(right(v)) at every vertex v; Give a parameter A>1,if lA, 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 k1 be an index with l(v )>l-A and k 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
v1 Note that l l, since T is right heavy l1 + + lk-1 = l - l(vk) < A Max{l,l}= l(vk+1) l-A Let Ti=T(left(vi)) and li=l(left(vi)) for i=1,,kv2 1 T1 Let T=T(left(vk)), T=T(right(vk)), T2 l=l(left(vk)), and l=l(right(v k))
Vk-2 Vk-1 Tk-2 vk Tk-1 T T RECURSIVE WINDING TREE DRAWING
k=1 k=2 If k=1, T and T are drawn recursively below v ; 1 v1 v1 If k=2, T1 is drawn with right-heavy-HV-tree, while T T T1 and T are drawn recursively; If k=3, T1,Tk-2 are drawn from left to right with right- T T heavy-HV-tree. Tk-1 is drawn right-heavy-HV-tree and then reflected around y-axis and rotated by /2. T and
T 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) T1 Tk-2 Tk-1 T k>2 T 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), l ++l } + log l + 1 k-2 2 k-1 1 t(l) t(l) + t(l) + O(l + + l 1 k-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(log ) 2A
t(l) t(l) + t(l) + O(A) Because Max{l,l}= l(vk+1) l-A, W(l) = O(l/AlogA + A) RECURSIVE WINDING TREE DRAWING The running time is O(n); By setting A as A = (llog l), the height and 2 width of the drawing are both O(nlogn). An example
