Premium
Scalable, Versatile and Simple Constrained Graph Layout
Author(s) -
Dwyer Tim
Publication year - 2009
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2009.01449.x
Subject(s) - computer science , graph layout , scalability , graph , constraint (computer aided design) , theoretical computer science , euclidean geometry , graph drawing , algorithm , mathematics , database , geometry
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.