1 H3: Laying Out Large Directed Graphs in 3D Hyperbolic Space Andrew Chan CPSC 533C March 24, 2003

2 H3 Image from:

3 Ideas behind H3 u Creating an optimal layout for a general graph is tough u Creating an optimal layout for a tree is easier u Often it is possible to use domain- specific knowledge to create a hierarchical structure from a graph

4 Stumbling Blocks u The deeper the tree, the more nodes; exponential growth u You can see an overview, or you can see fine details, but not both

5 Solution u A layout based on hyperbolic space, that allows for a focus + context view u H3 used to lay out hierarchies of over nodes

6 Related Work u H3 has its roots in graph-drawing and focus+context work

7 2D Graph and Tree Drawing u Thinking very small-scale u Frick, Ludwig, Mehldau created categories for graphs; # of nodes ranged from 16 in the smallest category, to > 128 in the largest

8 2D Tree Drawing (cont’d) MosiacG System Zyers and Stasko Image from: er/270.html

9 3D Graph Drawing SGI fsn file-system viewer Image from: n.map2.jpg

10 3D Graph Drawing (cont’d) u Other work centered around the idea of a mass-spring system – Node repel one another, but links attract – Difficulty in converging when you try to scale the systems u Aside: Eric Brochu is doing similar work in 2D -

11 3D Tree Drawing Cone Trees, Robertson, Mackinlay, Card Image from: 06-Robertson-CHI91-Cone.pdf

12 Hyperbolic Focus+Context Hyperbolic Tree Browser, Lamping, Rao Image from: 5/Electronic/documnts/papers/jl _figs/strip1.htm

13 Alternate Geometry u Information at: u Euclidean geometry – 3 angles of a triangle add up to? – Shortest distance between two points? u Spherical geometry – How we think about the world – Shortest way from Florida to Philippines?

14 Alternate Geometry (cont’d) u Hyperbolic Geometry / Space – Is important to the Theory of Relativity – The “fifth” dimension – Can be projected into 2-D as a pseudosphere – Key: As a point moves away from the center towards the boundary circle, its distance approaches infinity

15 H3’s Layout Image from:

16 Finding a Tree from a Graph u Most effective if you have domain- specific knowledge u Examples: – File system – Web site structure – Function call graphs

17 Tree Layout Cone tree layout versus H3 Layout Image from:

18 Sphere Packing u Need an effective way to place information u Cannot place spheres randomly u Want to have a fast algorithm

19 Sphere Packing (cont’d) Image from:

20 Demo

21 Strengths u Can easily see what the important structures are and the relationships between them u Can let you ignore “noise” in data u Animated transitions u Responsive UI

22 Weaknesses u Starting view only uses part of the sphere u Moving across the tree can disorient you; cost of clicking on the wrong place is high u Labels not present if node too far from center

23 Questions?