Technical Reports

The ICICS/CS Reading Room


UBC CS TR-2007-23 Summary

GLUG: GPU Layout of Undirected Graphs, October 15, 2007 Stephen Ingram, Tamara Munzner and Marc Olano, 13 pages

We present a fast parallel algorithm for layout of undirected graphs, using commodity graphics processing unit (GPU) hardware. The GLUG algorithm creates a force-based layout minimizing the Kamada Kawai energy of the graph embedding. Two parameters control the graph layout: the number of landmarks used in the force simulation determines the influence of the global structure, while the number of near neighbors affects local structure. We provide examples and guidelines for their use in controlling the visualization. Our layouts are of comparable or better quality to existing fast, large-graph algorithms. GLUG is an order of magnitude faster than the previous CPU-based FM3 algorithm. It is considerably faster than the only previous GPU-based approach to force-directed placement, a multi-stage algorithm that uses a mix of CPU partitioning and GPU force simulation at each step. While GLUG has a preprocessing stage that runs on the CPU, the core algorithm operates entirely on the GPU.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.