Drawing huge graphs by algebraic multigrid optimization

Y Koren; L Carmel; David Harel

doi:10.1137/S154034590241370X

Back

Drawing huge graphs by algebraic multigrid optimization

Journal article

Peer reviewed

Drawing huge graphs by algebraic multigrid optimization

Y Koren, L Carmel and David Harel

Multiscale Modeling & Simulation, Vol.1(4), pp.645-673

2003

DOI: https://doi.org/10.1137/S154034590241370X

Files and links (2)

url

https://doi.org/10.1137/S154034590241370XView

Published (Version of record) Restricted

url

https://ezproxy.weizmann.ac.il/login?url=http://dx.doi.org/10.1137/S154034590241370XView

Published (Version of record) Restricted

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 finds 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 fields; hence ACE appears to be applicable outside graph drawing too.

Details

Title: Drawing huge graphs by algebraic multigrid optimization
Creators: Y Koren (null)
L Carmel (null)
David Harel (null) - 972WIS_INST___83
Resource Type: Journal article
Publication Details: Multiscale Modeling & Simulation, Vol.1(4), pp.645-673; 2003
Number of pages: 29
Language: English
DOI: https://doi.org/10.1137/S154034590241370X
Record Identifier: 993263514803596

Metrics

8 Record Views