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.

Abstract

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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (4MB) | Preview
Download: [img] PDF - Preprinted Version
Download (815kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: [error in script] [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 68-XX Computer science > 68Wxx Algorithms > 68W01 General

  • 65-XX Numerical analysis > 65Kxx Mathematical programming, optimization and variational techniques > 65K99 None of the above, but in this section

  • 68-XX Computer science > 68Wxx Algorithms > 68W25 Approximation algorithms

  • Additional Information: Extended Abstract
    Uncontrolled Keywords: force-directed methods, graph drawing, large graphs, multipole method, N-body simulation, potential field
    Subjects: 68-XX Computer science > 68Wxx Algorithms > 68W01 General
    65-XX Numerical analysis > 65Kxx Mathematical programming, optimization and variational techniques > 65K99 None of the above, but in this section
    68-XX Computer science > 68Wxx Algorithms > 68W25 Approximation algorithms
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Stefan Hachul
    Date Deposited: 02 Feb 2006 00:00
    Last Modified: 12 Jan 2012 10:46
    Deposit Information:
    ZAIK Number: [error in script]
    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