Scalable, Versatile and Simple Constrained Graph Layout

We describe a new technique for graph layout subject to constraints. Compared to previous techniques the proposed method is much faster and scalable to much larger graphs. For a graph with n nodes, in edges and c constraints it computes incremental layout in time O(nlog n + m + c) per iteration. Also, it supports a much more powerful class of constraint: inequalities or equalities oiler the Euclidean distance between nodes. We demonstrate the power of this technique by application to a number of diagramming conventions which previous constrained graph layout methods could not support. Further; the constraint-satisfaction method-inspired by recent work in position-based dynamics-is far simpler to implement than previous methods.