Large-Graph Layout with the Fast Multipole Multilevel Method
Hachul, Stefan and Jünger, Michael
(2005)
Large-Graph Layout with the Fast Multipole Multilevel Method.
Technical Report
, 27 p.
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.
Download: |
Download (1MB) | Preview |
---|---|
Editorial actions: | ![]() |
Item Type: | Paper (Technical Report) |
---|---|
Citations: | 0 (Google Scholar) | |
Uncontrolled Keywords: | fast algorithms graph drawing large graphs multilevel methods N-body problem |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Additional Information: | submitted to ACM Transactions on Graphics |
Related URLs: |
ZAIK Number: | zaik2006-509 |
---|---|
Depositing User: | Stefan Hachul |
Date Deposited: | 10 Jan 2006 00:00 |
Last Modified: | 12 Jan 2012 10:29 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/509 |