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
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.
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
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.
A graph containing fourteen crossings
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
Graph produced with the algorithm of Roberto Tamassia, minimizing the number of bends for a fixed embedding
Drawing of the same graph (see 4a) produced by the same algorithm but with a different embedding as input
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.
Graph layed out for a VLSI design using the best known strategy
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|