GLUG: GPU Layout of Undirected Graphs

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.