Scalable, Versatile and Simple Constrained Graph Layout
Tim Dwyer · Computer Graphics Forum · 2009
Abstract 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, m edges and c constraints it computes incremental layout in time O(n log n+m+c) per iteration. Also, it supports a much more powerful class of constraint: inequalities or equalities over 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.
Cited by 88 works. doi:10.1111/j.1467-8659.2009.01449.x
Authors
References
- An algorithm for drawing general undirected graphs
- Methods for Visual Understanding of Hierarchical System Structures
- Position based dynamics
- Efficient, High-Quality Force-Directed Graph Drawing
- Advanced Character Physics
- Computing the intersection-depth of polyhedra
- Using constraints to achieve stability in automatic graph layout algorithms
- An interactive constraint-based system for drawing graphs
- IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs
- An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs