This section provides some background information about graph layout in general, not specifically related to the Views Graph Layout package.

Simply speaking, a graph is a data structure which 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 very 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 instance, 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, this involves determining the location of the nodes and the shape of the links. For some applications, the location of the nodes may be already known (based on the geographical positions of the nodes, for example). However, 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.

But what is meant by an “appropriate” drawing of a graph? In practical applications, it is often necessary for the graph drawing to respect certain quality criteria. These criteria may vary depending on the application field or on a given standard of representation. It is often difficult to speak about what a good layout consists of. Each end user may 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.