Faster ForceDirected Graph Drawing with the WellSeparated Pair DecompositionLipp, Fabian and Wolff, Alexander and Zink, Johannes (2015) Faster ForceDirected Graph Drawing with the WellSeparated Pair Decomposition. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 5259(Official URL: http://dx.doi.org/10.1007/9783319272610_5). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_5
AbstractThe forcedirected paradigm is one of the few generic approaches to drawing graphs. Since forcedirected 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 speed up this computation by using an approximation based on the wellseparated 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 then a hundred vertices—without a significant influence on the quality of the drawings (in terms of number of crossings and deviation in edge lengths).
Actions (login required)
