ACE: a fast multiscale eigenvectors computation for drawing huge graphs
2003pp. 137–144
Citations Over TimeTop 10% of 2003 papers
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 an improvement of something like two orders of magnitude over the fastest algorithms we are aware of; it draws graphs of millions of nodes in less than a minute. ACE finds an optimal drawing by minimizing a quadratic energy function. The minimization problem is expressed as a generalized eigenvalue problem, which is rapidly solved using a novel algebraic multigrid technique. The same generalized eigenvalue problem seems to come up also in other fields, hence ACE appears to be applicable outside of graph drawing too.
Related Papers
- → Solving the Cardiac Bidomain Equations for Discontinuous Conductivities(2006)76 cited
- → Multigrid Software for Industrial Applications - From MG00 to SAMG(2009)12 cited
- → Some Recent Advances in Multigrid Methods(1991)3 cited
- → Multigrid methods IV : proceedings of the Fourth European Multigrid Conference, Amsterdam, July 6-9, 1993(1994)2 cited