Graph Visualization: A Survey
Graph Visualization
Overview
Survey is focused on the use of graph visualization techniques to
Applications, Key Issues
problems in Information Visualization.
Graph Layout
Graphs - a natural way to represent relationships.
Navigation and Interaction
Graphs in Infoviz: Are there inherent relationships among the input
Clustering
data elements?
Systems
NO: Unstructed Data - Infoviz must be used to discover relationships.
Current State of Graph Visualization
YES: Graphs can be used to represent the relationships - data
Reference
elements (nodes) and edges (relationships).
I.Herman, G. Melancon, M.S. Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on
Visualization and Computer Graphics, Volume 6(1), January, 2000.
1
ITCS 6010/8010: Information Visualization
Graph Visualization
Survey is focused on structured data and the use of graphs applied
to Infoviz domain.
ITCS 6010/8010: Information Visualization
Graph Visualization
Applications
Key Issues in Graph Visualization
File hierarchies, organization charts, biological taxonomies
Web site maps, browsing history
Size is the key issue in visualizing graphs.
Biology: Evolutionary, phylogenetic trees, genetic maps, biochemi-
Large graphs are constrained by display resources, and usability
cal pathways, protein function
Computer Science: data structures, object oriented systems, ER
(interaction, for instance)
Very little work on applying cognitive science or human factors.
diagrams, scene graphs (graphics)
ITCS 6010/8010: Information Visualization
Graph Visualization
ITCS 6010/8010: Information Visualization
Graph Visualization
Example Tree Layout
Graph Layout Algorithms
Reingold and Tilford Algorithm
Background: Graph Drawing
Given a set of nodes and a set of edges (relations), calculate the position
of the nodes and the curve to be drawn for each edge.
Well studied subject (hundreds of publications, books!)
Planarity: Graphs drawn on a plane with no edge crossing
Layout types: grid layouts (nodes at integer coords), force-directed
models, simulated annealing based layouts.
Aesthetic Issues: Nodes, edges evenly distributed, isomorphic substructures, straight line edges, etc.
Isomorphic subtrees are always laid out the same way
Distance between nodes is a parameter.
ITCS 6010/8010: Information Visualization
Graph Visualization
ITCS 6010/8010: Information Visualization
Graph Visualization
Layout Algorithm Issues
Size: Graphs with thousands of nodes can make most layout algo-
Layout Algorithm Issues (contd)
rithms almost useless.
NicheWorks, H3Viewer are among systems that can handle large
graphs.
Predictability: Consecutive runs of an algorithm should not result in
radically different visual representations (preserving mental map)
High Node Density: Traditional algorithms cannot scale up, making
interaction difficult.
Time Complexity: Real-time (or near real-time) updates of the graph
is needed in highly interactive applications, where the graph can be
modified.
Can also use 3D layouts or non-Euclidean geometry.
Extremely large graphs - need methods to simplify (reduce) graph
size (clustering, grouping)
ITCS 6010/8010: Information Visualization
Graph Visualization
ITCS 6010/8010: Information Visualization
Graph Visualization
Traditional Layout
Child nodes below common ancestor
Reingold and Tilford algorithm - the best known - can produce topdown or lef to right layouts, as well as grid positioning.
H-Tree: Representation for binary trees; uses axis-aligned representaton of edges.
Radial Trees (Eades)
Balloon Views - planarized Cone Trees
Tree maps, Onion Graphs, Cushion Treemaps
ITCS 6010/8010: Information Visualization
Graph Visualization
ITCS 6010/8010: Information Visualization
10
Graph Visualization
Traditional Layout (contd)
Spring Layouts: or force-directed
Models nodes and edges as physical bodies tied with springs.
Uses Hookes law to define forces between bodies
Can lead to well balanced layouts, some optimzed for minimizing
edge crossings and predictable layouts.
Disadvantage: Computational complexity is generally O(N 3),
most methods are highly unpredictable.
ITCS 6010/8010: Information Visualization
11
Graph Visualization
ITCS 6010/8010: Information Visualization
12
Graph Visualization
Spanning Trees
3D Layouts
Most traditional layout algorithms work well on small graphs
A practical solution is to layout the graph by computing the spanning
tree (tree layouts are typically of O(N ) complexity).
Once the tree is laid out, the other edges can then be added to tree.
Methods:
3D layouts, in combination with interactive viewing can accommodate larger graphs, while compensating for occlusion
Most force-directed and simulated annealing approaches can also
be extended to 3D.
3D layouts also use visual cues such as transparency, depth queu-
Can use breadth-first or depth-first search, starting from a likely
root node.
If edges have weight, can use various optimization criteria (and
heuristics) in the layout algorithm
ITCS 6010/8010: Information Visualization
13
Graph Visualization
ing, etc.
Classic Example: Cone Trees (a direct 3D algorithm) and their extensions (disk trees)
ITCS 6010/8010: Information Visualization
15
Graph Visualization
Cone Trees
3D Radial Layout
ITCS 6010/8010: Information Visualization
14
Graph Visualization
ITCS 6010/8010: Information Visualization
16
Graph Visualization
Other 3D Layout Examples
Hyperbolic Layouts
SGI file system navigator (until version 5) (seen in Jurassic Park!)
Perspective Wall - data representation as posters on large walls
Viznet, Vitesse - data mapped onto a sphere
views
Makes it possible to view and interact with large trees, and thus crucial for real-life Infoviz applications.
Difficulties with 3D layouts
A mapping from hyperbolic to Euclidean space - two models, Klein
3D navigation in 2D displays and 2D input devices
and Poincare.
VR and immersive environments are not commonplace
ITCS 6010/8010: Information Visualization
Provides a distorted view of a tree in 2D or 3D, similar to fish-eye
17
Graph Visualization
ITCS 6010/8010: Information Visualization
18
Graph Visualization
Hyperbolic Layouts(contd)
Hyperbolic Layouts(contd)
Hyperbolic Layouts(contd)
Klein Model:
Klein model uses an open disc (sphere in 3d) as a subset hyperbolic plane contains points internal to the disc
Line segments of equal length in hpyerbolic plane get exponentially smaller as they approach the perimeter
Poincare Model: Similar to the Klein model, but segments are arcs,
intersecting orthogonally at the perimeter of the disc.
ITCS 6010/8010: Information Visualization
19
Graph Visualization
ITCS 6010/8010: Information Visualization
20
Graph Visualization
Hyperbolic Layouts(contd)
Navigation and Interaction
Crucial tools to dealing with large graphs
Can help reveal graph structure
Real-time interaction is an important goal.
The small wedges seen in Euclidean plane (resulting in unusable
layouts is very different in the hyperbolic plane (wedges are opened
up)
ITCS 6010/8010: Information Visualization
21
Graph Visualization
ITCS 6010/8010: Information Visualization
22
Graph Visualization
Space-Scale Diagrams
Represent points in image as rays (with point, magnification)
Choose paths to destination as a combination of zoom and pan ac-
Zoom and Pan
tions
Standard graphics interaction operations, manipulated by affine
transformations, followed by a redraw.
Geometric zoom vs. Semantic Zoom.
Zooming in, can cause loss of context
ITCS 6010/8010: Information Visualization
23
Graph Visualization
ITCS 6010/8010: Information Visualization
24
Graph Visualization
Fisheye Distortion(contd)
Focus+Context Techniques
Techniques that allow users to focus on some detail of the visualization,
without losing context.
Fisheye Distortion
Simple distortions use a radial function, for eg.,
h(x) = (d + 1)/(d + 1/x)
ITCS 6010/8010: Information Visualization
25
Graph Visualization
ITCS 6010/8010: Information Visualization
26
Graph Visualization
Fisheye Distortion(contd)
Cartesian Fisheye: Distortion applied to X and Y independently.
Fisheye Distortion(contd)
Approximation of segments with linear elements can introduce edge
crossings.
ITCS 6010/8010: Information Visualization
27
Graph Visualization
ITCS 6010/8010: Information Visualization
28
Graph Visualization
Focus+Context and Layout
Clustering
Fisheye distortion is typically a processing step separate from the
Advantageous to reduce the number of elements displayed, espe-
layout.
Hyberbolic layout is the exception, as the technique is designed with
the goal of focus+context.
Hyperbolic layouts - changing focus is equivalent to changing the
center of the Euclidean circle(sphere).
Other Examples: mapping onto spheres and ellipsoids, followed by
perspective projection, Perspective Wall.
ITCS 6010/8010: Information Visualization
29
cially very large graphs/trees.
Structure-based clustering: uses only structural information about
the graph
Content-based clustering: node and edge attributes are used to determine clusters.
Most clustering work is structure based.
Clustering - used to accomplish filtering and search.
Graph Visualization
ITCS 6010/8010: Information Visualization
30
Graph Visualization
Cluster Layout
Clustering Approaches
Can just layout the clusters by themselves - good high level view of
the graph structure
Locate disjoint clusters (simpler to navigate)
Choose clusters with the least number of edges between members
(Ratio-Cut technique)
Use glyphs to represent clusters and treat them as supernodes
with abridgemens between clusters.
Force-directed cluster layout: nodes that are related to each other
are attracted, while all nodes have a minimal repulsion force (O(N 3 )
Hierarchical clustering
complexity).
ITCS 6010/8010: Information Visualization
31
Graph Visualization
ITCS 6010/8010: Information Visualization
32
Graph Visualization
Cluster Representation
Node Metrics for Clustering
Structure or content based.
Combination of structure and content based metrics are more powerful, eg. linear weighted combination.
Representation of unselected nodes
Ghosting - deemphasizing nodes
Hiding
Grouping - grouping under a new super-node representation
ITCS 6010/8010: Information Visualization
33
Graph Visualization
Graph Drawing - Systems, Journals,
Conferences
A very large community of researchers, users
Large number of systems have been implemented
Graph Drawing Symposia - dedicated to this domain
Journal of Graph Algorithms and Applications
Significant ties to CHIXX, UISTXX, InfoVizXX, IEEE TVCG, CG
Forum
ITCS 6010/8010: Information Visualization
35
Graph Visualization
ITCS 6010/8010: Information Visualization
34
Graph Visualization
