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:

*Arc label anchor points*which denote absolute arc labels positions*Edge control points*which denote also absolute positions. When arcs are displayed by open polygones, the control points are traversed. In case of smooth curves, it depends on the graphical tool kit if the control point positions are interpolated or only approximated (the regular case).*Arc port nodes*- Points to determine the graph node display size. At the time, this is feasible only for the visibility representation model.

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

.

- An arc label anchor point given by abstractMixedGraph::ArcLabelAnchor()
- A sequence of control points enumerated by abstractMixedGraph::ThreadSuccessor()
- Occasionally, two port nodes on the boundary of the arc end nodes visualizations.

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

- In the most simple case, the straight line drawing of simple graphs, no control points exist. The arc label anchor points and the port nodes are implicit and determined by the display of graph nodes.
- For all available orthogonal drawing methods, the number of control points is 3 or less. In high-degree models, port nodes are explicit, and are implicit in models which admit a maximum node degree of 4 or less.

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.

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.

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:

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:

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,..):

- The small node model is limited to graphs where node degrees are at most 4. In this model, no explicit port nodes are handled. There are specialized methods for planar graphs and for binary trees, but also a method for the non-planar setting.
- The edge display can be restricted to a certain number of bends. No more than three bends per edge are used in the library methods.
- In the 1-visibility representation model, edges are bend-free and running only in vertical directions. The nodes only have horizontal extent. Thus this model is naturally restricted to planar graphs.
- In the Kandinsky model, two grids are used. Nodes are displayed as squares of equal size in a coarse grid which is specified by the nodeSpacing parameter. When post optimization is turned off, every edge has exactly one control point. There are methods for the general and for the planar setting, for trees and for redrawing a graph, in order to maintain the so-called
*mental map*.

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!

- Visibility representation: For a given biconnected planar (represented) graph, bipolar orientations of the input graph and its dual graph are computed. The node coordinates are determined by the distance labels in these digraphs. If the input graph is not biconnected, it is augmented. There is an optional post-processing mode, reducing the node sizes to the minimum of what is possible without re-routing the arcs. For graphs where the node degree is bounded by 3, a small node drawing can be obtained.
- 4-orthogonal drawings: The method also applies to non-planar graphs. It checks for the existence of a planar representation and occasionally adapts itself to the planar setting. However, the input graph must be biconnected (Augmentation does not make sense here!)
- Kandinski drawings: The so-called
*staircase method*starts with an exterior edge and inserts the other nodes step by step, according to a*canonical ordering*which is available for triconnected planar graphs only. In each intermediate step, the overall shape is a half-square triangle, and node are inserted on the diagonal side. There is an interface which extends the method to non-triconnected graphs by triangulation of the input graph.

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.

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.

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:

- By specifying LAYERED_FEEDBACK, the the top-down arc orientations are explicitly computed (In case of directed acyclic graphs, all arcs will point downwards). If this option is not specified, the orientations must be either given in advance, are implicated by an existing layer assignment or by the given drawing (depending on the other rules for vertical placement).
- When specifying LAYERED_EDGE_SPAN, nodes are assigned to layers by applying the exact edge span minimization code.
- When specifying LAYERED_COLOURS, all nodes with finite colour index are forced to the respective layer. If the layering is not complete, the edge span minimization code method is applied.
- In any case, arcs spanning more than one layer, are subdivided by control points. This completes the vertic placement phase.
- By specifying LAYERED_SWEEP, the crossing minimization code is applied. This performs local optimization between two adjacent layers, sweeping top-down and bottom-up again, until no further improvement is possible. Crossing minimization is the performance critical part of the layered drawing method. After that step, the relative order of nodes in each layer is fixed.
- When specifying LAYERED_FDP, a one dimensional force directed method does the horizontal node alignment. The node moves are either unlimited or preserve the relative node order set by the crossing minimization code.
- By specifying LAYERED_ALIGN, an LP model is applied to maximize the slopes of the edge segments.

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: