Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (Extended Abstract)

Hachul, Stefan and Jünger, Michael (2004) Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (Extended Abstract). In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 285-295 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_29).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_29
Classifications:P Styles > P.720 Straight-line
M Methods > M.400 Force-directed / Energy-based
ID Code:595

Repository Staff Only: item control page

References

S. Aluru et al. Distribution-Independent Hierarchical Algorithms for the N-body Problem. Journal of Supercomputing, 12:303-323, 1998.

The AT&T graph collection: www.graphdrawing.org

J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324(4):446-449, 1986.

R. Davidson and D. Harel. Drawing Graphs Nicely Using Simulated Annealing ACM Transaction on Graphics, 15(4):301-331, 1996.

P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

T.M.J. Fruchterman and E.M. Reingold. Graph Drawing by Force-directed Placement. Software-Practice and Experience, 21(11):1129-1164, 1991.

P. Gajer et al. A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs. In J. Marks, editor, Graph Drawing 2000, volume 1984 of Lecture Notes in Computer Science, pages 211-221. Springer-Verlag, 2001.

L. F. Greengard. The Rapid Evaluation of Potential Fields in Particle Systems. ACM distinguished dissertations. The MIT Press, Cambridge, Massachusetts, 1988.

D. Harel and Y. Koren. A Fast Multi-scale Method for Drawing Large Graphs. In J. Marks, editor, Graph DRawing 2000, volume 1984 of Lecture Notes in Computer Science, pages 183-196. Springer-Verlag, 2001.

D. Harel and Y. Koren. Graph Drawing by High-Dimensional Embedding. In M. T. Goodrich and S. G. Kobourov, editors, Graph Drawing 2002, volume 2528 of Lecture Notes in Computer Science, pages 207-219. Springer-Verlag, 2002.

M. Jünger et al. Graph Drawing Software, volume XII of Mathematics and Visualization, chapter AGD - A Library of Algorithms for Graph DRawing, pages 149-169. Springer-Verlag, 2004.

T. Kamada and S. Kawai. An Alorithm for Drawing General Undirected Graphs. Information Processing Letters, 31:7-15, 1989.

Y. Koren et al. Drawing Huge Graphs by Algebraic Multigrid Optimization. Multiscale Modeling and Simulation, 1(4):645-673, 2003.

A. Quigley and P. Eades. FADE: Graph Drawing, Clustering, and Visual Abstraction. In J. Marks, editor, Graph Drawing 2000, volume 1984 of Lecture Notes in Computer Science, pages 197-210. Springer-Verlag, 2001.

D. Tunkelang. JIGGLE: Java Interactive Graph Layout Environment. In S. H. Whitesides, editor, Graph Drawing 1998, volume 1547 of Lecture Notes in Computer Science, pages 413-422. Springer-Verlag, 1998.

C. Walshaw's graph collection: www.gre.ac.uk/~c.walshaw/partition

C. Walshaw. A Multilevel Algorithm for Force-Directed Graph Drawing. In J. Marks, editor, Graph Drawing 2000, volume 1984 of Lecture Notes in Computer Science, pages 171-182. Springer-Verlag, 2001.