Drawing Large Graphs with a Potential -Field-Based Multilevel Algorithm

Hachul, Stefan and J√ľnger, Michael (2004) Drawing Large Graphs with a Potential -Field-Based Multilevel Algorithm.
Published In: Graph drawing: 12th international symposium, GD 2004, New York, NY, USA, September 29 - October 2, 2004; revised selected papers, Lecture Notes in Computer Science. 3383 Springer 2004, pp. 285-295.


Force-directed graph drawing algorithms are widely used for drawing general graphs. However, these methods do not guarantee a sub-quadratic running time in general. We present a new force-directed method that is based on a combination of an efficient multilevel scheme and a strategy for approximating the repulsive forces in the system by rapidly evaluating potential fields. Given a graph G=(V,E), the asymptotic worst case running time of this method is {O}(|V|log|V|+|E|) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing 100000 nodes in less than 5 minutes. Furthermore, it clearly visualizes even the structures of those graphs that turned out to be challenging for some other methods.

Download: [img] Postscript - Preprinted Version
Download (4MB) | Preview
Download: [img] PDF - Preprinted Version
Download (815kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2004-472
Depositing User: Stefan Hachul
Date Deposited: 02 Feb 2006 00:00
Last Modified: 12 Jan 2012 10:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/472