Graph drawing - Definition and Overview

Graphs are often represented pictorially as follows: draw a dot for every vertex, and for every edge draw an arc connecting its endpoints. If the graph is directed, indicate the endpoint of an edge by an arrow.

There are different approaches to graph layout and these are considered under a branch of graph theory termed as graph drawing.

Note that this graphical representation (a layout) should not be confused with the graph itself (the abstract, non-graphical structure). Very different layouts can correspond to the same graph (see external link #1). All that matters is which vertices are connected to which others by how many edges.

Some of the well known layouts are

• spring layout - by using an energy function that is minimized so that nodes and edges spread out by repulsion.
• orthogonal layout - layout with edges running horizontally or vertically, with approaches that reduce the number of edge crossovers and area covered. These are of great interest in the areas of VLSI and PCB layout design.
• symmetric layout - these attempt to find symmetry groups within the graph
• tree layout - these show a rooted tree-like formation, suitable for trees (ie graphs without cycles)
• hierarchical layouts - these attempt to find a source and sink within a directed graph and arrange the nodes in layers with most edges starting from the source and flowing in the direction of the sink.

Academic Conferences

One of the top academic conferences for new research in graph drawing is the annually held International Symposium on Graph Drawing (GD).

GD 2004 (http://www.gd2004.org/)

Open Problems

Recently, a wiki for keeping track of the open problems in the field of graph drawing has been set up.

http://problems.graphdrawing.org

See also

• State diagrams

References

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications 4:235-282 (1994). http://www.cs.brown.edu/people/rt/gd.html
• Isabel F. Cruz, Roberto Tamassia. Graph Drawing Tutorial. http://www.cs.brown.edu/people/rt/gd.html

External links

Here are some examples of graph layouts:

• http://www.aisee.com/gallery
• http://www.research.att.com/sw/tools/graphviz/examples/

Popular graph layout tools

• http://www.graphviz.org
• http://www.cs.uni-sb.de/RW/users/sander/html/gsvcg1.html
• http://www.aisee.com
• http://www.tulip-software.org
• http://www.oreas.com/
• http://www.ilog.com
• http://www.algorithmic-solutions.com/enalgocomskomm.htm
• http://www.jgraph.com/
• http://www.yworks.com/en/products.htm
• ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/doc/tr-A03-94.ps.gz
• http://www.gravisto.org
• http://www.wilmascope.org
• http://www.cs.uleth.ca/~vpak/gluskap