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
form one of the standard
examples of a graph drawing),
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
- 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
of social structures, L. Krempel, Max-Planck-Inst. Köln.
Graph drawing applications in sociology.
clearinghouse for graph drawing research.
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).
'97, Rome, Sept. 1997.
'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.
drawing research, A. Frick, Karlsruhe.
a toolkit for implementing graph editors and graph drawing algorithms.
XML-based language for standardization of graph drawing software
Other previously used graph formats include
edge list, node edge list, parenthesized,
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.
component-based Java software for drawing graphs for business users and
domain specific data.
Java graph-editing software with many built-in graph algorithms.
- My own research on
- Schnyder's grid-embedding algorithm.
Lecture notes for two graph algorithm classes.
Tutte embedding, K. Chilakamarri, N. Dean, and M. Littman.
Three-dimensional convex drawing of nonplanar graphs.
- Ioannis Tollis'
graph drawing research and
- 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
Geometry in Action,
a collection of applications of computational geometry.
from a common source file.