%0 Journal Article %1 lwz-ffdgd-algorithms16 %A Lipp, Fabian %A Wolff, Alexander %A Zink, Johannes %D 2016 %J Algorithms %K experiments force-directed graph-drawing myown well-separated-pair-decomposition %N 3 %P 53 %R 10.3390/a9030053 %T Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition %U http://www.mdpi.com/1999-4893/9/3/53 %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 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).

@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 = {2016-08-04T14:43:26.000+0200}, author = {Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, biburl = {https://www.bibsonomy.org/bibtex/2a0a78a3ba326b401ba557658d503c8c2/fabianlipp}, doi = {10.3390/a9030053}, interhash = {b7a3c202329e61872f41c20cc7a93ccd}, intrahash = {a0a78a3ba326b401ba557658d503c8c2}, issn = {1999-4893}, journal = {Algorithms}, keywords = {experiments force-directed graph-drawing myown well-separated-pair-decomposition}, number = 3, pages = 53, timestamp = {2016-09-13T18:46:51.000+0200}, title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition}, url = {http://www.mdpi.com/1999-4893/9/3/53}, volume = 9, year = 2016 }