Geometry in Action

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.

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.