A Multilevel Algorithm for ForceDirected Graph DrawingWalshaw, C. (2001) A Multilevel Algorithm for ForceDirected Graph Drawing. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 171182(Official URL: http://dx.doi.org/10.1007/3540445412_17). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540445412_17
AbstractWe describe a heuristic method for drawing graphs which uses a multilevel technique combined with a forcedirected 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 forcedirected 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 forcedirected placement algorithms.
Actions (login required)
