Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00070
A Multilevel Algorithm for ForceDirected GraphDrawing
Vol. 7, no. 3, pp. 253285, 2003. Regular paper.
Abstract We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a forcedirected placement algorithm.
The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G_{0}, G_{1}, …, G_{L}.
The coarsest graph, G_{L}, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original.
At each successive change of level, l, the initial layout for G_{l} is taken from its coarser and smaller child graph, G_{l+1}, and refined using forcedirected placement.
In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing.
The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices.
It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 57 minutes for the largest graphs.
This is an order of magnitude faster than recent implementations of forcedirected placement algorithms.
Keywords: graphdrawing, multilevel optimisation, forcedirected placement. 
Journal Supporters
