Below are screenshots of a system built to experiment
with graph visualization in 3D.
A pseudo-physical simulation of repulsive and attractive
forces automatically produces a layout of the graph.
Nodes and edges can be interactively created, dragged, or deleted,
as the simulation runs.
The graph visualized below corresponds to my website's structure. Scripts written in Bourne shell and Perl scan my website and produce a plain text description of the corresponding graph.
The plain text description can then be read in by the
visualization program for viewing.
After creating this prototype, I learned that the ideas it uses
are an example of a well established technique
known as force-directed layout of graphs. Here are some
related references I came across:
- An overview of graph drawing:
Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis.
Graph Drawing: Algorithms for the Visualization of Graphs.
Prentice Hall, 1999.
- A survey of force-directed methods:
Franz J. Brandenburg, Michael Himsolt, and Christoph Rohrer.
An experimental comparison of force-directed
and randomized graph drawing algorithms.
Proceedings of Symposium on Graph Drawing (GD '95), pages 76-87, 1995.
- Use of simulated annealing:
R. Davidson and D. Harel.
Drawing graphs nicely using simulated annealing.
ACM Transactions on Graphics (TOG), 15(4):301-331, October 1996.
- The "spring-embedder", the original force directed method:
A heuristic for graph drawing.
Congressus Numerantium, 42:149-160, 1984.
- Use of attractive and repulsive forces:
T. M. J. Fruchterman and E. M. Reingold.
Graph drawing by force-directed placement.
Software, Practice and Experience, 21(11):1129-1164, 1991.
- Other early work:
J. B. Kruskal and J. Seery.
Designing network diagrams.
First General Conference on Social Graphics, pages 22-50, 1980.
U. S. Department of the Census.
- Other early work, referenced by
Davidson, Wylie, and Boyack in InfoVis 2001:
N. Quinn and M. Breur.
A force directed component placement procedure
for printed circuit boards.
IEEE Transactions on Circuits and Systems,
1979, CAS-26, (6), 377-388.