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 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 Journal Article
%1 lwz-ffdgd-Algorithms16
%A Lipp, Fabian
%A Wolff, Alexander
%A Zink, Johannes
%D 2016
%J Algorithms
%K myown
%N 3
%P article 53, 17 pages
%R 10.3390/a9030053
%T Faster Force-Directed Graph Drawing with the
Well-Separated Pair Decomposition
%V 9
%X 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 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).
@article{lwz-ffdgd-Algorithms16,
abstract = {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).},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Lipp, Fabian and Wolff, Alexander and Zink, Johannes},
biburl = {https://www.bibsonomy.org/bibtex/2a0a78a3ba326b401ba557658d503c8c2/awolff},
doi = {10.3390/a9030053},
interhash = {b7a3c202329e61872f41c20cc7a93ccd},
intrahash = {a0a78a3ba326b401ba557658d503c8c2},
journal = {Algorithms},
keywords = {myown},
number = 3,
pages = {article 53, 17 pages},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Faster Force-Directed Graph Drawing with the
Well-Separated Pair Decomposition},
volume = 9,
year = 2016
}