Graph Drawing
Graph drawing can be thought of as a form of data visualization, but
unlike most other types of visualization the information to be
visualized is purely combinatorial, consisting of edges connecting a set
of vertices. Applications of graph drawing include genealogy, cartography
(subway maps
form one of the standard
examples of a graph drawing),
sociology,
software engineering (visualization of
connections between program modules), VLSI design, and
visualization of hypertext links. Typical
concerns of graph drawing algorithms are the area needed to draw a
graph, the types of edges (straight lines or bent), the number of edge
crossings for nonplanar graphs, separation of vertices and edges so they
can be distinguished visually, and preservation of properties such as
symmetry and distance. The area has a large literature, concentrated in
the annual Graph Drawing symposia, and I won't try to link here to all
available research projects and papers on the subject, only those with some
particular historical or application interest.
- aiSee graph
visualization software.
- Atlas of science.
G. Edgar describes this project in which the publishers of Science
Citation Index use graph drawing techniques to clarify the relations
between different research specialties.
- CSE690: Graph Drawing Seminar, Auburn U.
- da Vinci graph visualization system, M. Fröhlich, U. Bremen.
- Fan Chung's graph
drawing page.
- Gallery
of social structures, L. Krempel, Max-Planck-Inst. Köln.
Graph drawing applications in sociology.
- Graphdrawing.org
clearinghouse for graph drawing research.
- Graph
Drawing, Roberto Tamassia, Brown U.
This page contains pointers to a
long annotated bibliography, a graph drawing tutorial, and
information on the annual Graph Drawing conference.
- Graph Drawing:
GD '92 and '93 reports, programs, and proceedings
(TeX and PS formats).
GD
'97, Rome, Sept. 1997.
GD
'98, Montreal, Aug. 1998.
GD '99, Prague, Sep. 1999.
GD '00, Virginia, Sep. 2000.
GD '01, Vienna, Sep. 2001.
GD '02, Irvine, Sep. 2002.
GD '03, Perugia, Sep. 2003.
- Graph
drawing research, A. Frick, Karlsruhe.
- Graphlet,
a toolkit for implementing graph editors and graph drawing algorithms.
- GraphML
XML-based language for standardization of graph drawing software
input/output formats.
Other previously used graph formats include
MALF,
edge list, node edge list, parenthesized,
GXL,
GraphXML,
GML,
LEDA.GRAPH,
XGMML,
BCG,
Aldebaran,
graph6 (g6), and sparse6 (s6),
so there is obviously a lot of benefit to be gained from standardization.
- GraphViz package: dot and
neato graph drawing software, E. Koutsofios and S. North.
- GVF, open-source
Java graph visualization framework.
- JGraph
component-based Java software for drawing graphs for business users and
domain specific data.
- JGraphEd,
Java graph-editing software with many built-in graph algorithms.
- My own research on
graph drawing.
- Schnyder's grid-embedding algorithm.
Lecture notes for two graph algorithm classes.
- Three-dimensional
Tutte embedding, K. Chilakamarri, N. Dean, and M. Littman.
Three-dimensional convex drawing of nonplanar graphs.
- Ioannis Tollis'
graph drawing research and
papers.
- Tom Sawyer Software,
producers of commercial graph drawing and editing software.
-
Visualizing the structure of the WWW in hyperbolic space,
T. Munzner and P. Burchard. Hyperbolic graph drawings and
fly-throughs.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
