Drawing Graphs Nicely

  

 

Input description: A graph G.

Problem description: Draw a graph G so as to accurately reflect its structure.

Discussion: Drawing graphs nicely is a problem that constantly arises in applications, such as displaying file directory trees or circuit schematic diagrams.    Yet it is inherently ill-defined. What exactly does nicely mean? We seek an algorithm that shows off the structure of the graph so the viewer can best understand it. We also seek a drawing that looks aesthetically pleasing.   Unfortunately, these are ``soft'' criteria for which it is impossible to design an optimization algorithm. Indeed, it is possible to come up with two or more radically different drawings of certain graphs and have each be most appropriate in certain contexts. For example, page contains three different drawings of the Petersen graph. Which of these is the ``right'' one?  

Several ``hard'' criteria can partially measure the quality of a drawing:

• Crossings - We seek a drawing with as few pairs of crossing edges as possible, since they are distracting.  
• Area - We seek a drawing that uses as little paper as possible, while ensuring that no pair of vertices are placed too close to each other.  
• Edge length - We seek a drawing that avoids long edges, since they tend to obscure other features of the drawing.  
• Aspect ratio - We seek a drawing whose aspect ratio (width/height) reflects that of the desired output medium (typically a computer screen at 4/3) as close as possible.  

Unfortunately, these goals are mutually contradictory, and the problem of finding the best drawing under any nonempty subset of them will likely be NP-complete.

Two final warnings before getting down to business. For graphs without inherent symmetries or structure to display, it is likely that no really nice drawing exists, especially for graphs with more than 10 to 15 vertices. Even when a large, dense graph has a natural drawing, the shear amount of ink needed to draw it can easily overwhelm any display. A drawing of the complete graph on 100 vertices, , contains approximately 5,000 edges, which on a pixel display works out to 200 pixels an edge. What can you hope to see except a black blob in the center of the screen?

Once all this is understood, it must be admitted that certain graph drawing algorithms can be quite effective and fun to play with. To choose the right one, first ask yourself the following questions:

• Must the edges be straight, or can I have curves and/or bends? - Straight-line drawing algorithms are simpler than those with polygonal lines,   but to visualize complicated graphs such as circuit designs, orthogonal polyline drawings seem to work best. Orthogonal means that all lines must be drawn either horizontal or vertical, with no intermediate slopes.    Polyline means that each graph edge is represented by a chain of straight-line segments, connected by vertices or bends.
• Can you build a natural, application-specific drawing algorithm? - If your graph represents a network of cities and roads,   you are unlikely to find a better drawing than placing the vertices in the same position as the cities on a map. This same principle holds for many different applications.
• Is your graph either planar or a tree? - If so, use one of the special planar graph    or tree drawing algorithms of Sections and .
• How fast must your algorithm be? - If it is being used for interactive update and display, your graph drawing algorithm had better be very fast. You are presumably limited to using incremental algorithms, which change the positions of the vertices only in the immediate neighborhood of the edited vertex.   If you need to print a pretty picture for extended study, you can afford to be a little more extravagant.

As a first, quick-and-dirty drawing for most applications, I recommend simply spacing the vertices evenly on a circle, and then drawing the edges as straight lines between vertices.   Such drawings are easy to program and fast to construct, and have the substantial advantage that no two edges can obscure each other, since no three vertices will be nearly collinear. As soon as you allow internal vertices into your drawing, such artifacts can be hard to avoid. An unexpected pleasure with circular drawings is the symmetry that is sometimes revealed because consecutive vertices appear in the order they were inserted into the graph.   Simulated annealing can be used to permute the circular vertex order so as to minimize crossings or edge length, and thus significantly improve the drawing.

A good, general-purpose heuristic for drawing graphs models the graph as a system of springs and then uses energy minimization to space the vertices.    Let adjacent vertices attract each other with a force proportional to the logarithm of their separation, while all nonadjacent vertices repel each other with a force proportional to their separation distance. These weights provide incentive for all edges to be as short as possible, while spreading the vertices apart. The behavior of such a system can be approximated by determining the force acting on each vertex at a particular time and then moving each vertex a small amount in the appropriate direction. After several such iterations, the system should stabilize on a reasonable drawing. The input and output figures above demonstrate the effectiveness of the spring embedding on a particular small graph.

If you need a polyline graph drawing algorithm, my recommendation is that you study several of the implementations presented below, particularly graphEd and GraphViz,    and see whether one of them can do the job. You will have to do a significant amount of work before you can hope to develop a better algorithm.

Once you have a graph drawn, this opens another can of worms, namely where to place the edge/vertex labels. We seek to position the labels very close to the edges or vertices they identify, and yet to place them such that they do not overlap each other or important graph features. Map labeling heuristics are described in [WW95]. Optimizing label placement can be shown to be an NP-complete problem, but heuristics related to bin packing (see Section ) can be effectively used.   

Implementations: Georg Sander maintains a comprehensive WWW page on graph drawing at http://www.cs.uni-sb.de/RW/users/sander/html/gstools.html. This is well worth checking out and probably should be your first stop in hunting down programs for graph drawing.

The best ftp-able package of graph drawing algorithms is GraphEd, by Michael Himsolt. GraphEd [Him94] is a powerful interactive editor that enables the user to construct and manipulate both directed and undirected graphs. It contains a variety of graph and tree drawing algorithms, including planar drawings, polyline drawings, upward drawings of directed acyclic graphs (DAGs), and spring embeddings, and allows variations in node, edge, and label styles. Sgraph is an interface to GraphEd to support user-specific extensions written in C. It includes a modest library of algorithms for planarity testing, maximum flow, matching, and connectivity testing. GraphEd can be obtained by anonymous ftp from forwiss.uni-passau.de (132.231.20.10) in directory /pub/local/graphed. GraphEd is free for noncommercial use. Graphlet is a more recent project by the same group, available at http://www.fmi.uni-passau.de/Graphlet.

GraphViz is a popular graph drawing program developed by Stephen North of Bell Laboratories. It represents edges as splines and can construct useful drawings of quite large and complicated graphs. I recommend it, even though licensing considerations make it impossible to include on the Algorithm Repository or CD-ROM. A noncommercial license is available from http://portal.research.bell-labs.com/orgs/ssr/book/reuse/.

Combinatorica [Ski90] provides Mathematica implementations of several graph drawing algorithms, including circular, spring, and ranked embeddings. See Section for further information on Combinatorica.

daVinci is a graph drawing and editing system whose layout algorithm seeks to minimize edge crossings and line bends, from Michael Froehlich at the University of Bremen. Information about daVinci is available from http://www.informatik.uni-bremen.de/ davinci. Binaries are available for a variety of UNIX workstations, although source code is not available.

Notes: A significant community of researchers in graph drawing has emerged in recent years, fueled by or fueling an annual conference on graph drawing, the proceedings of which are published by Springer-Verlag's Lecture Notes in Computer Science series. Perusing a volume of the proceedings will provide a good view of the state of the art and of what kinds of ideas people are thinking about.

The best reference available on graph drawing is the annotated bibliography on graph drawing algorithms by Giuseppe Di Battista, Peter Eades, and Roberto Tamassia [BETT94], which is also available from http://www.cs.brown.edu/ rt. See [BGL 95] for an experimental study of graph drawing algorithms.

Although it is trivial to space n points evenly along the boundary of a circle, the problem is considerably more difficult on the surface of a sphere. Extensive tables of such spherical codes for in up to five dimensions have been construction by Sloane, Hardin, and Smith, and are available from netlib (see Section ) in att/math/sloane.

Related Problems: Drawing trees (see page ), planarity testing (see page ).