Scalable, Versatile and Simple Constrained Graph Layout

Loading...
Thumbnail Image
Date
2009
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd.
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(nlogn+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.
Description

        
@article{
:10.1111/j.1467-8659.2009.01449.x
, journal = {Computer Graphics Forum}, title = {{
Scalable, Versatile and Simple Constrained Graph Layout
}}, author = {
Dwyer, Tim
}, year = {
2009
}, publisher = {
The Eurographics Association and Blackwell Publishing Ltd.
}, ISSN = {
1467-8659
}, DOI = {
/10.1111/j.1467-8659.2009.01449.x
} }
Citation