A graph is a data structure that represents
a set of entities, called nodes, connected by a set of links. A
node can also be referred to as a vertex. A link can also be
referred to as an edge or a connection. In practical applications,
graphs are frequently used to model a wide range of things:
computer networks, software program structures, project management
diagrams, and so on. Graphs are powerful models because they
permit applications to benefit from the results of graph theory
research. For example, efficient methods are available for finding
the shortest path between two nodes, the minimum cost path, and so
on.
Layout of a graph
Graph layout is used in graphical user
interfaces of applications that need to display graph models. To
lay out a graph means to draw the graph so that an appropriate,
readable representation is produced. Essentially, it involves
determining the location of the nodes and the shape of the
links. For some applications, the location of the nodes is
already be known (for example, based on the geographical
positions of the nodes). For other applications, the location is
not known (a pure “logical” graph) or the known location, if
used, would produce an unreadable drawing of the graph. In these
cases, the location of the nodes must be computed.
What is meant by an “appropriate” drawing
of a graph? In practical applications, it is often necessary for
the graph drawing to observe certain quality criteria. These
criteria can vary depending on the application field or on a
given standard of representation. It is often difficult to tell
what a good layout consists of. Each user can have different,
subjective criteria for qualifying a layout as “good”. However,
one common goal exists behind all the criteria and standards:
the drawing must be easy to understand and provide easy
navigation through the complex structure of the graph.
What is a good layout?
To deal with the various needs of
different applications, many classes of graph layout algorithms
have been developed. A layout algorithm addresses one or more
quality criteria, depending on the type of graph and the
features of the algorithm, when laying out a graph.
The most common criteria are:
- Minimizing the number of link crossings
- Minimizing the total area of the drawing
- Minimizing the number of bends (in orthogonal drawings)
- Maximizing the smallest angle formed by consecutive incident links
- Maximizing the display of symmetries
How can a layout algorithm meet each of these quality criteria
and standards of representation? If you look at each individual
criteria, some can be met easily, at least for some classes of
graphs. For other classes, it might be difficult to produce a
drawing that meets the criteria. For example, minimizing the
number of link crossings is relatively simple for trees (that
is, graphs without cycles). For general graphs, minimizing the
number of link crossings is a mathematical NP-complete problem (that is, with all
known algorithms, the time required to perform the layout grows
fast with the size of the graph).
If you want to meet several criteria at
the same time, an optimal solution might not exist for each one
individually, because many of the criteria are mutually
contradictory. Time-consuming trade-offs might be necessary. In
addition, it is not a trivial task to assign weights to each
criteria. Multicriteria optimization is, in most cases, too
complex to implement, and much too time-consuming. For these
reasons, layout algorithms are often based on heuristics and
might provide less than optimal solutions with respect to one or
more of the criteria. Fortunately, in practical terms, the
layout algorithms still often provide reasonably readable
drawings.
Methods for using layout algorithms
Layout algorithms can be employed in
various ways in the various applications in which they are used.
The most common ways of using an algorithm are:
-
The layout algorithm does everything without any user intervention, except for perhaps the choice of the layout algorithm to be used. Sometimes, a set or rules can be coded to choose automatically (and dynamically) the most appropriate layout algorithm for the particular type of graph to lay out.
-
The application user is free to improve the result of the automatic layout procedure by hand. In some cases, this user can move and “pin” nodes at wanted locations and perform the layout again. In other cases, a part of the graph is automatically set as “read-only” and the user can modify the rest of the layout.
- Layout from scratchThe layout algorithm is completely redone (“from scratch”) each time the graph is changed.
- Incremental layoutWhen the layout algorithm is performed a second time on a modified graph, it tries to preserve the stability of the layout as much as possible. The layout is not performed again from scratch. The layout algorithm also tries to save CPU time by using the previous layout as an initial solution. Some layout algorithms and layout styles are incremental by nature. For others, incremental layout might be impossible.