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, Karlsruhe, Germany , pp. 20-29 (Official URL:

Full text not available from this repository.


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
ID Code:758

Repository Staff Only: item control page


Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42 (1984) 149-160.

Kamada, T., Kawai, S.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters 31 (1989) 7-15.

Fruchterman, T., Reingold, E.: Graph Drawing by Force-directed Placement. Software{Practice and Experience 21 (1991) 1129-1164.

Davidson, R., Harel, D.: Drawing Graphs Nicely Using Simulated Annealing. ACM Transaction on Graphics 15 (1996) 301-331.

Hachul, S., Jünger, M.: Drawing large graphs with a potential-eld-based multilevel algorithm. In Pach, J., ed.: Graph Drawing. Volume 3383 of Lecture Notes in Computer Science., Springer (2004) 285-295.

Barnes, J., Hut, P.: A hierarchical O(N logN) force-calculation algorithm. Nature 324 (1986) 446-449.

Quigley, A., Eades, P.: FADE: Graph Drawing, Clustering, and Visual Abstraction. In Marks, J., ed.: Graph Drawing 2000. Volume 1984 of Lecture Notes in Computer Science., Springer-Verlag (2001) 197-210.

Tunkelang, D.: JIGGLE: Java Interactive Graph Layout Environment. In Whitesides, S.H., ed.: Graph Drawing 1998. Volume 1547 of Lecture Notes in Computer Science., Springer-Verlag (1998) 413-422.

Greengard, L.: The Rapid Evaluation of Potential Fields in Particle Systems. ACM distinguished dissertations. The MIT Press, Cambridge, Massachusetts (1988).

Hachul, S.: A Potential-Field-Based Multilevel Algorithm for Drawing Large Graphs. PhD thesis, Institut fur Informatik, Universität zu Köln, Germany (2005) URN: urn:nbn:de:hbz:38-14097, URL:

Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18 (1975) 509-517.

Welzl, E.: Smallest enclosing disks (balls and ellipses). New Results and New Trends in Computer Science 555 (1991) 359-370.

Lauther, U.: The c++ class library turbo - a toolbox for discrete optimization. Software@Siemens (2000) 34-36.