Automatic Graph Drawing


A graph is a mathematical structure that is widely used to describe the relationships between different objects. The objects are called the nodes of the graph and the relationships are called edges. Every edge connects two nodes. One example for a structure that can be described as a graph are relationships between people. Suppose there is a group of people, some of which know each other; this can be expressed using a graph in which the nodes are the people and there is an edge connecting two people if they know each other.

Graph drawing is the art to draw a graph in such a way that the relationships between the objects are easily understood by looking at the picture. The nodes are usually drawn as circles or rectangles while the edges are drawn as curves connecting two of these shapes.
 
 
Hand made graph drawing
The optimized drawing of the graph on the left
Transformation to an optimized graph drawing of the same graph
Figure 1a:
Hand made graph drawing
Figure 1b:
The optimized drawing 
of the graph on the left
Figure 1c:
Animation of the transformation 
from Figure 1a to 1b

In industry, such drawings are widely used, e.g., as Entity-Relationship-Diagrams, data flow graphs or call graphs in database design, software engineering or CASE tools.

The following picture shows an example of an Entity-Relationship-Diagram taken from an internal documentation of a big company.

Figure 2: An Entity-Relationship-Diagram 

The goal of automatic graph drawing is to develop algorithms that compute a good drawing automatically. Since an exact definition of a good drawing is needed for this purpose, the graph drawing community has developed objective criteria to measure the quality of a drawing. One of these criteria is the number of crossings between edges in the drawing. We want to have as few crossings as possible. Other crietria are the length of the edges of the graph and the number of bends in the edges.

A Selection of Research Areas in the Algorithms and Data Structures Group

Crossing minimization

Graphs that can be drawn without edge crossings are called planar graphs. We can easily test, if a graph is planar, and there are several algorithms to draw a planar graph without crossing edges.

If a graph is not planar, we want to draw it with as few crossings as possible, because crossings significantly decrease the readability of a drawing. Since it is very hard to find a drawing of a non planar graph with the minimum number of crossings, we use the following approach to compute a drawing with a small number of crossings. We first delete a small number of edges from the given graph such that the resulting graph is planar. Then we compute a drawing of this planar subgraph without crossings. Finally we reinsert the deleted edges into this drawing in such a way that the number of edge crossings is minimized. Using this approach, the number of crossings of the final drawing depends on the planar subgraph and the drawing of this subgraph.

The following two pictures show the same graph. The drawing on the left contains fourteen crossings, the drawing on the right contains only one crossing.

Figure 3a:
A graph containing fourteen crossings
Figure 3b:
Crossing minimization of the same graph shown in Figure 1a shows only one crossing remaining

Finding the optimum embedding

Imagine a drawing of a planar graph that has no crossings. Now you are allowed to move the nodes and change the shape of the edges. But a moving node is not allowed to cross an edge and edges are not allowed to cross each other. Then all drawings constructed by the transformation realize the same planar embedding of the graph. A planar embedding describes the sequence of the edges in clockwise direction around each node. The number of planar embeddings of a graph can grow exponentially with the number of nodes. Most known graph drawing algorithms for planar graphs need a planar embedding as input and they produce different drawings depending on the chosen embedding. The goal is to find the embedding that produces the best results when used as input for a graph drawing algorithm.

For the drawing on the left, we have chosen a bad embedding as input for the algorithm of Roberto Tamassia that minimizes the number of bends for a fixed embedding. The drawing on the right shows a drawing of the same graph produced by the same algorithm but with a different embedding as input.
 
 

Figure 5a:
Graph produced with the algorithm of Roberto Tamassia, minimizing the number of bends for a fixed embedding
Figure 5b:
Drawing of the same graph (see 4a) produced by the same algorithm but with a different embedding as input

Compaction

Once the basic structure of a graph drawing is fixed, we want to assign consistent lengths to the edges in order to obtain an aesthetically pleasing drawing. Optimization criteria during this phase include the area of the drawing, the total edge length and the length of the longest edge. The problems of minimizing these objectives are computationally hard. We have designed a new technique to minimize the total edge length or the length of the longest edge in an orthogonal drawing which is based on an integer linear programming approach. In orthogonal drawings each edge is drawn as a sequence of only horizontal and vertical line segments, this drawing standard is among the most popular ones. Compare the two drawings of the graph having same structural properties, i.e. topology and shape. The left drawing is produced using the previously best strategy (iterative one-dimensional compaction with flow-techniques known from VLSI-design), the right layout has been output by our algorithm.
 
 

Figure 4a:
Graph layed out for a VLSI design using the best known strategy
Figure 4b:
The same graph produced by one of our algorithms

Graph Drawing Software developed at Vienna University of Technology

The AGD library is a C++ library containing many state of the art algorithms used for automatic graph drawing. It started as a joint project with the groups of Michael Jünger in Köln and Stefan Näher in Trier (formerly in Halle) and the Max-Planck-Institut für Informatik in Saarbrücken. The project has been funded by the DFG. AGD is easy to use and to expand by adding new algorithms. The library is based on the software packages LEDA and ABACUS.

The graph drawing group at Vienna University of Technology consists of the following people:
 
Petra Mutzel Head coordinates graph drawing activities of the group, planarization, level crossing minimization, planar augmentation
Carsten Gutwenger Ph.D. Student AGD library, planar drawing algorithms, crossing minimization, combinatorial embeddings
Gunnar W. Klau Ph.D. Student orthogonal graph drawing, compaction, labelling
Karsten Klein Master's Student orthogonal graph drawing, compaction
René Weiskircher Ph.D. Student optimizing embeddings, crossing minimization
Thomas Ziegler Ph.D. Student crossing minimization


Interesting links:




Algorithms and Data Structures Group | Inst. of Computer Graphics and Algorithms | TU Wien

If you have any suggestions, please contact webmaster @ads.tuwien.ac.at.
Last modification: 2002-07-23, 19:05