Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition

Lipp, Fabian and Wolff, Alexander and Zink, Johannes (2015) Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 52-59(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_5).

Full text not available from this repository.

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 speed up this computation by using an approximation based on the 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 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).

Item Type: Conference Paper
Classifications: M Methods > M.400 Force-directed / Energy-based
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:20
Last Modified: 04 May 2016 16:20
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1477

Actions (login required)

View Item View Item