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.