Scalable force directed graph layout algorithms using fast multipole methods

Enas Abdulrahman Yunis, Rio Yokota, Aron Ahmadia

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We present an extension to ExaFMM, a Fast Multipole Method library, as a generalized approach for fast and scalable execution of the Force-Directed Graph Layout algorithm. The Force-Directed Graph Layout algorithm is a physics-based approach to graph layout that treats the vertices V as repelling charged particles with the edges E connecting them acting as springs. Traditionally, the amount of work required in applying the Force-Directed Graph Layout algorithm is O(|V|2 + |E|) using direct calculations and O(|V| log |V| + |E|) using truncation, filtering, and/or multi-level techniques. Correct application of the Fast Multipole Method allows us to maintain a lower complexity of O(|V| + |E|) while regaining most of the precision lost in other techniques. Solving layout problems for truly large graphs with millions of vertices still requires a scalable algorithm and implementation. We have been able to leverage the scalability and architectural adaptability of the ExaFMM library to create a Force-Directed Graph Layout implementation that runs efficiently on distributed multicore and multi-GPU architectures. © 2012 IEEE.
Original languageEnglish (US)
Title of host publication2012 11th International Symposium on Parallel and Distributed Computing
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages180-187
Number of pages8
ISBN (Print)9780769548050
DOIs
StatePublished - Jun 2012

Fingerprint Dive into the research topics of 'Scalable force directed graph layout algorithms using fast multipole methods'. Together they form a unique fingerprint.

Cite this