Graph layout

Layout models

The layout model determines many but not all of the display parameters: For example, colours, edge widths and text labels are assigned independently of the layout model, whereas node and arc shape modes are layout model dependent.

Any transition from one layout model to another requires to call abstractMixedGraph::Layout_ConvertModel() which does some kind of garbage collection for the old layout points and sets the correct display parameters for the new model. When calling a layout method, this is done implicitly. There may be various drawing methods supporting the same layout model!

In the very basic setting, the straight line model, graph drawing just means to position the graph nodes in the Euclidian plane. But this only works with simple graphs (graphs without parallel edges and loops). Node and arc labels are placed according to certain global rules. It is obvious that such rules produce readable drawings without overlaps only in special cases.

The are several drawing methods which produce straight line drawings, for example placement of all nodes on a circle or exposing a predecessor tree. The resulting drawings may be input to a force directed placement (FDP) method. The latter do not always produce straight line drawings but call sparseRepresentation::Layout_ArcRouting() in order to expose possible parallel edges.

The more elaborate layout models require to distinguish between graph nodes and layout points. The latter are addressed by node indices ranged in an interval [0,1,..,n+ni-1]. All graph nodes are mapped to layout points, called node anchor points. The additional layout points can be grouped as follows:

For the time being, graph node indices and the respective node anchor point indices coincide, that is NodeAnchorPoint(v)==v.

[See API]

Arc routing

The display of any arc is determined by the following layout nodes:

Depending on the applied layout model, these nodes are either implicit or represented by a layout node index and respective coordinates:

Provided that the number of control points is generally bounded, use sparseRepresentation::GetArcControlPoints() to write the control point sequence of a specified arc to aa array, including the port nodes. The result depends on the arc orientation bit. If the number of control points is not known in advance, the sequence of control points of any forward arc a (an even arc index!) is obtained by this recurrency rule:

controlPoint[0] = PortNode(a);

for (i=0;controlPoint[i]!=NoNode;++i) { controlPoint[i+1] = ThreadSuccessor(controlPoint[i]); }

If the layout model uses explicit port nodes, those are the extremal points in the control point sequence, namely controlPoint[0] and controlPoint[i-1].

Manipulation of arc routings is somewhat tricky: Currently, control points cannot be assigned independently from arc label anchor points. Use the most high-level operation sparseRepresentation::InsertArcControlPoint() which still has some side effects: It will implicitly allocate and position an arc label anchor point if it does not exist in advance.

[See API]

Bounding boxes

Bounding boxes determine the extra space between the display boundaries and the graph nodes (layout points are not considered). The bounding box is retrieved component-wise by calling abstractMixedGraph::Layout_GetBoundingInterval().

By default, bounding intervals are the extremal coordinate values augmented by the node spacing parameter value, and thus computed dynamically. The drawback of this rule is, that the bounding intervals can change dynamically with the graph nodes. In particular, for proper subgraphs, different intervals result.

To fix up such behavior, sparse graph objects can maintain two layout nodes which denote the upper-left and lower-right corner of the bounding box. The coordinates refer to the same metric space as the graph node coordinates.

If the current bounding box is as desired, and should stay unchanged with subsequent modifications of the graph or its drawing, just call abstractMixedGraph::Layout_FreezeBoundingBox(). There is also a method abstractMixedGraph::Layout_ReleaseBoundingBox() to revert to the dynamic bouding box computation.

All layout codes and most graph constructors (in particular, the copy constructors) set up a fixed bounding box.

In case of circular or radial drawings, the bounding box is the tight square around the bounding sphere.

[See API]

Planar straight-line drawing

Basically, planar drawing means to create a drawing of a planar graph without any edge crossings. In fact, all planar drawing methods depend on a particular planar representation, that is a clockwise ordering of incidence lists according to a virtual plane drawing. Before drawing a planar graph, it is necessary to determine such a planar representation! If no exterior arc has been specified in advance, an exterior face with a maximum number of nodes is set up.

The library comes up with a method for convex drawing of triconnected planar graphs. This method has been be extended to arbtrirary planar graphs by making the input graph triconnected, then applying the convex drawing method and mapping back the node placement to the original graph. The final drawing probably has non-convex faces even if the input graph is triconnected, since graphs are actually triangulated. It is recommended either to apply the convex method directly or to use the restricted force directed placement (FDP) method for post-precessing.

The following is a convex drawing of the dodecahedron. The good resolution of area and angles stems from the regularity of the input graph:


[See API]

Circular drawing and outerplanarity

The basic method of placing all nodes on a circle only depends on a particular clock-wise node order. This may be specified explicitly by the node colour register (with arbitrary tie-breaking for nodes with equal colour indices). It is also possible to use the predecessor arc labels, with the special intent to expose Hamiltonian cycles. In the general case, the method backtracks on predecessor arcs as long as possible and places the traversed nodes, and then selects a further unmapped node for backtracking.

There is another specialization of the circular method which travels around the exterior face of a planar graph. It is restricted to the class of outerplanar graphs. This denotes all graphs which have a plane drawing with all nodes on the exterior face. The outerplanar Planar representation representation must be given in advance.

The next two figures show the same outerplanar graph, starting with the single circular drawing:


Some biconnected outerplanar graphs also admit an equilateral drawing. In that drawing, all nodes of a single interior face form a regular polyhedron. Observe that all equilateral drawings of a graph are congruent. A plane drawing results only in special cases. The original intent was to obtain paper models of Platonian and Archimedian polyhedra. For this purpose, there is another method to cut triconnected planar graphs along the edges of some spanning tree. What follows, is an example of such a paper model, obtained for the octahedron:


[See API]

Force directed layout

Force directed drawing is a post-opimization strategy for straight line drawings. It models attracting and repelling forces between nodes and, occasionally, between node-edge pairs. One iterates for a node placement which brings all forces into equilibriance. The classical spring embedder moves all nodes simultaneously, but the much faster GEM code moves only one node at a time. There is a version which restricts the node movements such that nodes do not cross any edges. The application to plane drawings is obvious, but the method can be used for general graphs, in order to maintain a so-called mental map.

[See API]

Orthogonal drawing algorithms

An orthogonal drawing is a drawing where all graph nodes are displayed by rectangles and all arcs are displayed by polygones running in a rectangular grid. The display points at which an arc is attached to its end nodes, are called port nodes. For sake of readability, overlapping nodes and crossings of edges with non-incident nodes are excluded.

There are various specializations of this general orthogonal grid drawing model. Most refer to the output of particular drawing algorithms, and usually restrict the input graph somehow (planarity, connectivity, loops, parallels,..):

For the small-node model and for the Kandiski model, but not for the visibility-representation model, post-optimization procedure exist. By that, grid lines can be merged and nodes can move from one grid line to an adjacent line, but only if this reduces the number of control points or the total edge length. The effects are tremendous, but the final drawings are still far from optimal, especially in terms of the required area.

The following is a small node drawing of a dodekahedron. The library does not provide an exact method for bend minimization, but it is easy to see that this particular drawing is bend-minimal:


This figure has not been generated automatically, but by using the interactive Kandinski method. Although the procedure does not mind plane or small-node drawings, it is helpful for post-processing such drawings!

[See API]

Planar case

The library admits three strategies to obtain plane orthogonal drawings, quite different to orchestrate:

The following figure has been obtained from applying the staircase method to the dodecahedron without any post-proceesing. In this example, the post optimization code would reduce the area by a factor of 10.3 (to the same area as in the previous drawing), and the number of bends by a factor of 5.0 (two more bends than in the optimal solution above):


An example of a visibility representation can be found with the description of series-parallel graphs.

[See API]

Orthogonal tree drawing

An HV-drawing of a binary tree is a plane straight line drawing such that the child nodes of any node are placed right-hand or below of the parent node. It is a rather small class of graph to which the method can be applied. But the results are appealing for that symmetries are exposed, as in the following drawing of a depth 4 regular binary tree:

Trees with high degree nodes can be drawn in the 1-bent Kandinski model. As in the binary case, parent nodes appear in the upper left corner of the spanned subtree bounding box. Other than for HV-trees, child nodes are always displayed below of the parent nodes.

[See API]

Layered Drawing

In a layered drawing, the node set is partitioned into independent sets (the layers), each layer is assigned to a horizontal grid line, and control points are placed wherever edges would cross grid lines in a straight line drawing. This first phase of the strategy is called vertical placement. Then in the horizontal placement phase, the nodes are arranged within their layers. Hereby, original graph nodes and control points are treated almost the same.

The optimization goals in the vertical placement step are the aspect ratio and the total edge span (this denotes the number of required control points). If the graph is directed or mixed, it is also intended to orient the arcs top-down. The goals in the horizontal placement are to prevent from edge crossings and to maximize the slopes of the edge segments.

Although it is a couple of more or less independent tools, the layered drawing code is called through a single interface function. If LAYERED_DEFAULT is specified, the graph is drawn from scratch. One should not expect plane or even upward-plane drawings for planar graphs. The main reason is that the crossing minimization code does not question the layer assignment done in advance.

Frankly, the rules which code is applied under which conditions are complicated:

In order to refine a given plane drawing, one should specify LAYERED_EDGE_SPAN and a method for horizontal placement, but skip the crossing minimization step. If no implicit top-down orientation has been computed in advance and delivered by the edge colours, the orientation is chosen as for the current drawing. It is not required that the previous drawing is in the layered model, but on the other hand, nodes might move vertically.

The following shows an edge span minimum upward drawing of upward planar digraph. This has been obtained in the default mode. In order to obtain a plane drawing, one node must be shifted manually to the next layer. But even then, the crossing minimization code would not clean up all edge crossings automatically:


[See API]

Return to main page