Incremental Procedure for Separation Constraint Layout (IPSep-CoLa)

Both layered and force-directed algorithms are well defined, popular and implemented to some degree in both static and dynamic graphing tools. They work well for small graphs and relatively sparse graphs where $\frac{\vert E\vert}{\vert V\vert}$ is relatively low, but they do not always find an optimal layout. Further a goal function like that in Eq  can be overly simplistic for certain applications where other layout criteria need to be considered. That is, users may wish to draw a piece of work for a particular domain, with a specific convention in mind. An example is that in a UML^2.2 class diagram it is often desired to have a parent class above all it's children or subclasses, in order to show the inheritance relationship between those classes. This desire translates into a constraint placed upon the final work.

There exists techniques to handle these application specific constraints, however the contention put forward by Dwyer et al. in [24], is that current techniques are brittle because they can only handle a particular type of constraint upon the layout. The algorithm put forward in [24] provides a robust constraint framework, that can be applied to graphs in all application domains.

IPSep-CoLa extends the DiG-CoLa model by the addition of a family of separation constraints, which are designed around the equalities/inequalities between pairs of coordinate variables in each dimension; eg $x_{1} + S = x_{2}$ or $x_{3} + S \le x_{4}$ for some separation constraint $S$ . One such separation constraint is that certain vertices in the graph must be below others, which was shown in DiG-CoLa. Other such constraints that can be placed into the constraint family through IPSep-CoLa are containment constraints where nodes are contained within a certain area, alignment constraints that force nodes to be aligned with each other in either dimension, and non-overlap constraints, where, when the graph is finally laid out, the geometric shapes that represent the vertices do not overlap each other on the page. The algorithm implements these constraints through an extension of Stress Majorisation, and the work in DiG-CoLa allowing the graph to be iteratively improved through the solving of quadratic goal functions, subject to various constraints placed upon the graph.

Figure: A graph showing terrorist cells with cluster constraints, directed edge constraints and non overlap constraints. Reproduced from [24]

The graph shown in Fig  shows a terrorist network. Placing clustering constraints on portions of the graph allow a reader to see groups within the overall network, and how the individuals within the groups relate to each other. The addition of non-overlap constraints prevent the node labels from overlapping each other. Directed edge constraints force those terrorists higher in the chain of command to be placed above their subordinates.