A Multilevel Algorithm for Force-Directed Graph-Drawing

Journal of Graph Algorithms and Applications http://jgaa.info/ vol. 7, no. 3, pp. 253–285 (2003) A Multilevel Algorithm for Force-Directed Graph-Drawing Chris Walshaw School of Computing and Mathematical Sciences, University of Greenwich, Old Royal Naval College, Greenwich, London, SE10 9LS, UK. http://www.gre.ac.uk/∼c.walshaw C.Walshaw@gre.ac.uk Abstract We describe a heuristic method for drawing graphs which uses a mul- tilevel framework combined with a force-directed 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 force-directed 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 exam- ples 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 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms. Keywords: graph-drawing, multilevel optimisation, force-directed place- ment. Communicated by Michael Kaufmann: submitted March 2002; revised August 2003. C. Walshaw, Multilevel Force-Directed Drawing, JGAA, 7(3) 253–285 (2003)254 1 Introduction Graph-drawing algorithms form a basic enabling technology which can be used to help with the understanding of large sets of inter-related data. By presenting data in a visual form it can often be more easily digested by the user and both regular patterns and anomalies can be identified. However most data sets do not contain any explicit information on how they should be laid out for easy viewing, although normally such a layout will depend on the relationships between pieces of data. Thus if we model the data points with the vertices of a graph and the relationships with the edges we can use graph-based technology and, in particular, graph-drawing algorithms to infer a ‘good’ layout from an arbitrary data set based on the relationships. There has been considerable research into graph-drawing in recent years and a comprehensive survey can be found in [2]. Many such algorithms are based on physical models and the vertices are placed so as to minimise the ‘energy’ in the physical system (see below, §2.3). Typically such algorithms are able to display structures and symmetries in the graph but their computational cost in terms of CPU time is very high. 1.1 Motivation The motivation behind our approach to graph-drawing...

Website: www.emis.de | Filesize: -
No of Page(s): 33
Download A Multilevel Algorithm for Force-Directed Graph-Drawing.pdf