Multipole-Based Force Approximation Revisited - a Simple but Fast Implementation Using a Dynamized Enclosing-Circle-Enhanced k-d-Tree

Lauther, Ulrich (2007) Multipole-Based Force Approximation Revisited - a Simple but Fast Implementation Using a Dynamized Enclosing-Circle-Enhanced k-d-Tree. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 20-29(Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_4).

Full text not available from this repository.

Abstract

Most force-directed graph drawing algorithms depend for speed crucially on efficient methods for approximating repulsive forces between a large number of particles. A combination of various tree data structures and multi-pole approximations has been successfully used by a number of authors. If a multi-level approach is taken, in the late (and due to the large number of particles computationally intensive) steps, movements of particles are quite limited. We utilize this fact by basing force-calculations on an easy updatable tree data structure. Using explicit distance checks instead of relying on implicit guarantees provided by quadtrees and avoiding local expansions of the multi-pole expansion leads to a very simple implementation that is faster than comparable earlier methods. The latter claim is supported by experimental results.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_4
Classifications: M Methods > M.400 Force-directed / Energy-based
URI: http://gdea.informatik.uni-koeln.de/id/eprint/758

Actions (login required)

View Item View Item