A Multilevel Force-directed Graph Drawing Algorithm Using Multilevel Global Force Approximation

C. Crawford, C. Walshaw & A. Soper


In this paper we discuss an efficiency saving for multilevel force directed placement algorithms. Typically such algorithms use a Barnes Hut octree (or sometimes a grid) in order to approximate global repulsive forces. Here we instead exploit the graph coarsening structure, already in place to facilitate the multilevel scheme, in order to provide a hierarchical approximation to the global forces. Not only is this more efficient, but also it takes better account of the graph structure than an octree or a grid.

Keywords: graph; drawing; forced directed placement; multilevel refinement

Tue Nov 13 10:15:09 GMT 2012