Drawing Huge Graphs by Algebraic Multigrid Optimization
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in Multiscale Modeling & Simulation
- Vol. 1 (4) , 645-673
- https://doi.org/10.1137/s154034590241370x
Abstract
We present an extremely fast graph drawing algorithm for very large graphs, which we term ACE (for Algebraic multigrid Computation of Eigenvectors). ACE exhibits a vast improvement over the fastest algorithms we are currently aware of; using a serial PC, it draws graphs of millions of nodes in less than a minute. ACE nds an optimal drawing by minimizing a quadratic energy function. The minimization problem is expressed as a generalized eigenvalue problem, which is solved rapidly using a novel algebraic multigrid technique. The same generalized eigenvalue problem seems to come up also in other elds, hence ACE appears to be applicable outside graph drawing too.Keywords
This publication has 12 references indexed in Scilit:
- An algorithm for drawing general undirected graphsPublished by Elsevier ,2003
- A Fast Multi-Scale Method for Drawing Large GraphsJournal of Graph Algorithms and Applications, 2002
- A multi-scale algorithm for drawing graphs nicelyDiscrete Applied Mathematics, 2001
- Graph visualization and navigation in information visualization: A surveyIEEE Transactions on Visualization and Computer Graphics, 2000
- Drawing graphs nicely using simulated annealingACM Transactions on Graphics, 1996
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- Optimal linear labelings and eigenvalues of graphsDiscrete Applied Mathematics, 1992
- Graph drawing by force‐directed placementSoftware: Practice and Experience, 1991
- Algebraic multigrid theory: The symmetric caseApplied Mathematics and Computation, 1986
- An r-Dimensional Quadratic Placement AlgorithmManagement Science, 1970