Faster force-directed graph drawing with the well-separated pair decomposition (Q1736822): Difference between revisions
From MaRDI portal
Latest revision as of 22:53, 18 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Faster force-directed graph drawing with the well-separated pair decomposition |
scientific article |
Statements
Faster force-directed graph drawing with the well-separated pair decomposition (English)
0 references
26 March 2019
0 references
Summary: The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only \(O(m+n\log n)\) time per iteration when laying out a graph with \(n\) vertices and \(m\) edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).
0 references
force-directed graph drawing
0 references
well-separated pair decomposition
0 references
Fruchterman-Reingold algorithm
0 references
experiments
0 references
number of crossings
0 references
deviation of edge lengths
0 references
runtime
0 references