Graph drawing

From Free net encyclopedia

As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. Graph drawing is motivated by applications such as VLSI circuit design, social network analysis, cartography, and bioinformatics.

1 Methods
2 Metrics
3 See also
4 References
5 External links
6 Popular graph layout tools

[edit]

Methods

Graphs are usually represented pictorially using dots to represent vertices, and arcs to represent the edges between connected vertices. Arrows can be used to show the orientation of directed edges. Note that this graphical representation (a graph layout or an embedding) 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). In the abstract, all that matters is which vertices are connected to which others by how many edges. In the concrete, however, the arrangement of these vertices and edges impacts understandability, usability, fabrication cost, and aesthetics.

Based on these concepts and caveats, there are different graph layout strategies, such as:

force-based layout: gradient-descent minimization of an energy function based on physical metaphors.
spectral layout: layout based on an energy function that is amenable to global minimization based on techniques from linear algebra.
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 (i.e., 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

In some applications of graph drawing it is important to formally specify, implement, and verify such procedures.

[edit]

Metrics

Image:Complete graph K4.svg

There is no "best" layout — different ways of displaying a graph emphasize different characteristics. One metric of a graph drawing algorithm's quality is the number of overlapping edges it draws. While some graphs cannot be drawn without overlapping edges, some graphs can be drawn with or without them (they are called planar graphs. According to this metric, "good" algorithms draw graphs with as little overlapping as possible.

[edit]

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

[edit]