Drawing large graphs with a potential-field-based multilevel algorithm. (English) Zbl 1111.68583

Pach, János (ed.), Graph drawing. 12th international symposium, GD 2004, New York, NY, September 29–October 2, 2004. Revised selected papers. Berlin: Springer (ISBN 3-540-24528-6/pbk). Lecture Notes in Computer Science 3383, 285-295 (2005).
Summary: 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.
For the entire collection see [Zbl 1069.68012].


68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI