Introduction to Graph drawing - InnoVis

Introduction to Graph drawing - InnoVis

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

Recently Viewed Presentations

  • Business Communication: Process and Product, 8e Mary Ellen

    Business Communication: Process and Product, 8e Mary Ellen

    Coping with challenges of multiple time zones, vast distances, and different languages. Developing new skills and attitudes. Practicing cultural awareness, flexibility, and patience. Requirements. ... PowerPoint Presentation Last modified by: MHE
  • Design of experiments (DOE) Steps Define problem Define

    Design of experiments (DOE) Steps Define problem Define

    Design of experiments (DOE) Steps Define problem Define experimental objectives Select factors that influence quality Select control & noise factors
  • Cues, Questions and Advance Organizers

    Cues, Questions and Advance Organizers

    Cues, Questions and Advance Organizers Karen Richardson Cues and Questions A way to help students use what they already know about a topic Activate prior knowledge Cues are "hints" about what they are going to learn Questions elicit from students...
  • Ecosystems: What They are (Chapter 2) small large

    Ecosystems: What They are (Chapter 2) small large

    Ecosystems: What They are (Chapter 2) Biosphere: Earth from the moon Organisms: Energy Sources Producers: plants and bacteria derive energy from inorganic sources phototrophs & chemotrophs Consumers: grazers, carnivores,etc. derive energy from living organisms (organic sources) Decomposers: fungi, scavengers, etc....
  • Introduction to The Odyssey - Mrs. Russo&#x27;s Class Website

    Introduction to The Odyssey - Mrs. Russo's Class Website

    Introduction to The Odyssey. Homer. No one knows for sure who Homer was. Later Greeks believed he was a blind minstrel, or singer, from the island of Chios. ... Helen's abduction from Sparta by the Trojans sparked the Trojan War....
  • path to electron - Florida State University

    path to electron - Florida State University

    The path to the electron (Horst Wahl, QuarkNet lecture, summer 2000) Early history of electricity -- beginnings, Franklin, Galvani, Volta Electricity: beginning of quantitative era - Coulomb, Ampère, Faraday Electric field Currents and magnetic field, induction Towards a field theory...
  • FFY2010 Annual EAP Section 2.0 Risk Management Training

    FFY2010 Annual EAP Section 2.0 Risk Management Training

    Where's my laptop? 7 Top Tips for Keeping Your Data Secure Tip 5: Properly dispose of information no longer needed Where's that usb drive? 7 Top Tips for Keeping Your Data Secure Tip 6: Keep your computer patched Patch Management...
  • Voltage-Gated Calcium Channels

    Voltage-Gated Calcium Channels

    D,e) same as b,c but for construct R2Q_WT. Since R2Q_Wt and R2Q+WT for Rb are similar to what observed in WT CNGA1 channels, but not Cs We can say the size of the permeating ion is important. Raising the possibility...