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.


Actions:
Download: [img] PDF - Preprinted Version
Download (1MB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: [error in script] 0 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 68-XX Computer science > 68Wxx Algorithms > 68W01 General

  • Additional Information: submitted to ACM Transactions on Graphics
    Uncontrolled Keywords: fast algorithms, graph drawing, large graphs, multilevel methods, N-body problem
    Subjects: 68-XX Computer science > 68Wxx Algorithms > 68W01 General
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Stefan Hachul
    Date Deposited: 10 Jan 2006 00:00
    Last Modified: 12 Jan 2012 10:29
    Deposit Information:
    ZAIK Number: [error in script]
    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