Walshaw, C. ORCID: https://orcid.org/0000-0003-0253-7779 (2001) A multilevel algorithm for force-directed graph drawing. In: Graph Drawing: 8th International Symposium, GD 2000 Colonial Williamsburg, VA, USA, September 20–23, 2000 Proceedings. Lecture Notes in Computer Science (1984). Springer Berlin Heidelberg, Berlin, Heidelberg, Germany, pp. 171-182. ISBN 9783540415541 ISSN 0302-9743 (doi:10.1007/3-540-44541-2_17)

Full text not available from this repository.

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 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 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 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 force-directed placement algorithms.

Item Type:	Conference Proceedings
Title of Proceedings:	Graph Drawing: 8th International Symposium, GD 2000 Colonial Williamsburg, VA, USA, September 20–23, 2000 Proceedings
Additional Information:	[1] This paper was first presented at the Graph Drawing: 8th International Symposium, (GD 2000), held from 20-23 September 2000 in Colonial Williamsburg, Virginia, USA. [2] ISBN: 978-3-540-41554-1 (Print) 978-3-540-44541-8 (Online).
Uncontrolled Keywords:	algorithm analysis and problem complexity, computer graphics, discrete mathematics in computer science, combinatorics
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:00
URI:	http://gala.gre.ac.uk/id/eprint/520

Actions (login required)

View Item