A Multilevel Algorithm for Force-Directed Graph Drawing

Walshaw, C. (2001) A Multilevel Algorithm for Force-Directed Graph Drawing. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 171-182(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_17).

Full text not available from this repository.


We describe a heuristic method for drawing graphs which uses a multilevel technique combined with a force-directed placement algorithm. The multilevel process groups vertices to form clusters, uses the clusters to define a new graph and is repeated until the graph size falls below some threshold. The coarsest graph is then given an initial layout and the layout is successively refined on all the graphs starting with the coarsest and ending with the original. In this way the multilevel algorithm both accelerates and gives a more global quality to the force-directed placement. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on a number of examples ranging from 500 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 30 seconds for a 10,000 vertex graph to around 10 minutes for the largest graph. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-44541-2_17
Classifications: M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
M Methods > M.400 Force-directed / Energy-based
G Algorithms and Complexity > G.350 Clusters
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/335

Actions (login required)

View Item View Item