Welcome to the MedLibrary.org Wikipedia Supplement on Graph drawing -- Please Click to Return to Front Page

This article or section is missing citations or needs footnotes. Using inline citations helps guard against copyright violations and factual inaccuracies. (July 2008)

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

A drawing of a graph is basically a pictorial representation of an embedding of the graph in the plane, usually aimed at a convenient visualization of certain properties of the graph in question or of the object modeled by the graph.

Overview

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. 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 related to molecular mechanics.
• spectral layout: layout using as coordinates the eigenvectors of a matrix such as the Laplacian derived from the adjacency matrix of the graph.
• 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.

Metrics

K₄ (the complete graph with 4 vertices) can be drawn with or without overlapping edges (move one of the corners inside the triangle formed by the other three corners)

There is no "best" layout of the drawing of a graph — different ways of displaying a graph emphasize different characteristics.

One measure of a graph drawing algorithm's quality is the number of edge crossings it draws. While some graphs cannot be drawn without edge crossings, some graphs can. These are called planar graphs. According to this metric, "good" algorithms draw graphs with as few edge crossings as possible.

Another possible measure is the closeness of vertices. Many graphs look better if non-adjacent vertices are not plotted close to each other. A further measure is the nearness of a vertex to a non-adjacent edge, this distance needs to be sufficiently big for an aesthetically pleasing appearance.

Type of graph drawing

• Hasse diagram, a type of graph drawing specialized to partial orders
• Dessin d'enfant, a type of graph drawing used in algebraic geometry
• State diagrams, graphical representations of finite state machines

See also

• Graphviz, an open-source graph drawing system from AT&T
• Routing, a graph-drawing-like step in the design of integrated circuits

References

• Battista, Giuseppe Di; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1994), "Algorithms for Drawing Graphs: an Annotated Bibliography", Computational Geometry: Theory and Applications 4: 235–282, http://www.cs.brown.edu/people/rt/gd.html .

• Battista, Giuseppe Di; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 9780133016154 .

• Herman, Ivan; Melançon, Guy; Marshall, M. Scott (2000), "Graph Visualization and Navigation in Information Visualization: A Survey", IEEE Transactions on Visualization and Computer Graphics 6: 24–43, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.8892 .

• Jünger, Michael; Mutzel, Petra (2004), Graph Drawing Software, Springer-Verlag, ISBN 9783540008811 .

External links

• Graphdrawing.org: the official web site of the Graph Drawing Steering Committee, organizers of the annual International Symposium on Graph Drawing. Includes a description of the graphml graph description language, example graph data, and links to many other graph drawing resources.
• Graph drawing e-print archive: including information on papers from all Graph Drawing symposia.
• Graph drawing at the Open Directory Project for many additional links related to graph drawing.

Wikipedia content modification information:

• This page was last modified on 9 January 2009, at 11:42.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Graph drawing".

The URL for this specific entry is:

• http://medlibrary.org/medwiki/Graph_drawing

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.