Walshaw, Chris ORCID: 0000-0003-0253-7779 (2003) A multilevel algorithm for force-directed graph-drawing. Journal of Graph Algorithms and Applications, 7 (3). pp. 253-285. ISSN 1526-1719 (doi:https://doi.org/10.7155/jgaa.00070)

Full text not available from this repository.

Abstract

We describe a heuristic method for drawing graphs which uses a multilevel 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, G0, G1, …, GL. The coarsest graph, GL, 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 Gl is taken from its coarser and smaller child graph, Gl+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 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 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Item Type:	Article
Additional Information:	[1] The Journal of Graph Algorithms and Applications is distributed in electronic form. [2] CMS Ref. No: 03/56. Published electronically
Uncontrolled Keywords:	graph-drawing, multilevel optimisation, force-directed placement
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Computer software
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Related URLs:	Publisher Publisher Organisation
Last Modified:	14 Oct 2016 09:01
URI:	http://gala.gre.ac.uk/id/eprint/705

Actions (login required)

View Item