Hachul, Stefan and Jünger, Michael (2005). Large-Graph Layout with the Fast Multipole Multilevel Method. Working Paper.

[img]
Preview
PDF
zaik2006-509.pdf

Download (1MB) | Preview

Abstract

The visualization of of large and complex networks or graphs is an indispensable instrument for getting deeper insight into their structure. Force-directed graph-drawing algorithms are widely used to draw such 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 with 100000 nodes in less than 5 minutes. Furthermore, it clearly visualizes even the structures of those graphs that turned out to be challenging for other methods.

Item Type: Preprints, Working Papers or Reports (Working Paper)
Creators:
CreatorsEmailORCIDORCID Put Code
Hachul, StefanUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-548927
Date: 2005
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54892

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item