Directed Graph Layout through Constrained Energy Minimisation (DiG-CoLa)

Stress Majorisation has been shown to be an effective way to minimise an energy state of a physical system modelling a graph. In order to give the user more control over the layout of the graph, constraints are a simple yet effective way for a user to give requirements to a layout algorithm. However in previous layout algorithm work, the addition of constraints was not possible, or the constraints were translated to the layout algorithm as additional spring forces. However this merely alters the goal function that is approximated in each iteration of the algorithm, and adds extra complexity to the force model, and in doing so, causes the stress function to become overly complicated, prone to numerical stiffness, and causes problems by the stress function becoming stuck in local minima, as well as never truly enforcing the constraint on the graph.

Dwyer et al. approaches this problem differently in [23]. They developed a layout algorithm that extends Stress Majorisation by iteratively minimising the quadratic forms that approximate and bound the stress function defined in Eq , subject to level constraints where all directed edges in the graph must point downwards. If a vertex $u$ has a directed edge to another vertex $v$ then in the final layout $u$ must be physically higher in the vertical dimension then $v$ . This approach places the vertices into layers, similar to a layered layout.

Dwyer et al. achieve level constraints by subjecting the quadratic function to linear constraints that represent the desire to reflect the hierarchical nature of the directed graph. By solving this quadratic program, the majorisation process still monotonically decreases thus still guaranteeing convergence, but with level constraints enforced on the graph.