A Multilevel Algorithm for Force-Directed Graph Drawing

A Multilevel Algorithm for Force-Directed Graph Drawing C. Walshaw School of Computing and Mathematical Sciences, University of Greenwich, Park Row, Greenwich, London, SE10 9LS, UK. email: C.Walshaw@gre.ac.uk Mathematics Research Report 00/IM/60 April 20, 2000 Abstract 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 de ne 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 optimised 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 100,000 vertices. It is also very fast and can compute a layout in around 30 seconds for a 10,000 vertex graph to around 10-20 minutes for the larger graphs. Keywords: Graph drawing, multilevel, force directed placement. 1 Introduction Graph drawing algorithms are a basic enabling technology which is used to help with the understanding of large sets of inter-related data. By presenting data in a visual form it can often be easily digested by the user and both regular patterns and anomalies can be more easily identi ed. 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. 1.1 Motivation The motivation behind our interest in graph drawing, and in fact behind our approach to addressing the problem, both arise from our work in the eld of graph partitioning. More often than not, the types of graph we wish to partition arise from computational meshes which need to be distributed amongst the processors of a parallel computer to simulate some real life process or phenomenon. It is fairly normal to have access to the coordinate information of the mesh and hence some form of coordinate system for the graph vertices (e.g. if each vertex represents a triangular or tetrahedral element one might simply position graph vertices at the centroid of that element). However, we are sometimes required to partition graphs either with no coordinate information or for which we do not have access to the coordinate information. Our initial interest in graph drawing therefore arose in trying to visualise the graph in order to help explain partitioning results...

Website: staffweb.cms.gre.ac.uk | Filesize: -
No of Page(s): 22
Download A Multilevel Algorithm for Force-Directed Graph Drawing - CiteSeer.pdf