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.

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.

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:

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.

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: