|
Graph
Visualization Tools
Why Visualize?
It is easy to dismiss
visualization tools by dubbing them “pretty pictures,” and
claiming that they are used only to illustrate existing results.
However, a well-designed visualization tool can allow the
user to ‘see’ structure in a graphed data set that is
difficult or impossible to see in its raw form.
The tools presented here have been used to understand the
structure of complicated web sites, to spot inefficiencies in the
NLANR cache hierarchy, and to display packet flows from a network
simulator.
Tasks
Visualization proceeds in
three separate steps: graph layout, interaction, and animation.
Calculating any useful
general graph layout is NP-hard.
Instead of trying to lay out a general graph, many layout
algorithms first extract a spanning tree from the general graph
and then lay that out in a hierarchical fashion (H3Viewer,
Otter).
Another approach is to punt and use a node’s geographical
location (Otter).
A topological force-directed layout algorithm can be used
to find a reasonable layout for general graphs (NAM).
Finally, several heuristic layout algorithms have been
developed (Ineato, Dotty).
Once a graph is laid out
on the screen, the tool should allow the user to interact with the
graph. Examples
interactions:
Finally, some tools will
show the state of a graph over time using animation techniques.
Animation can be useful for showing packet flows and graph
evolution.
Tools
These pages contain an
overview of several notable network visualization tools.
-
H3Viewer
is a highly scalable 3D graph viewer that uses distortion to
give the user a focus + context view of the graph.
-
Otter is
a feature-rich 2D graph viewer.
-
NAM/Javis
are packet flow animators for the Network Simulator (NS).
-
Ineato uses a
topological force-directed layout algorithm on general graphs.
-
Dotty uses
heuristic algorithms to draw directed acyclic graphs
(hierarchies).
Links
Graph
Visualization Tools presentation, September 2000.
Interactive
Visualization of Large Graphs and Networks, Tamara Munzer’s
Ph.D. Thesis - This thesis contains a synopsis of graph
visualization tools as well as a description of H3Viewer.
|