Accelerating Force-Directed Graph Drawing with RT Cores

Stefan Zellmann, Martin Weier, Ingo Wald
Accepted at IEEE Visualization (Short Papers) - 2020

Abstract

Graph drawing with spring embedders employs a V ×V computation phase over the graph’s vertex set to compute repulsive forces. Here, the efficacy of forces diminishes with distance: a vertex can effectively only influence other vertices in a certain radius around its position. Therefore, the algorithm lends itself to an implementation using search data structures to reduce the runtime complexity. NVIDIA RT cores implement hierarchical tree traversal in hardware. We show how to map the problem of finding graph layouts with force-directed methods to a ray tracing problem that can subsequently be implemented with dedicated ray tracing hardware. With that, we observe speedups of 4× to 13× over a CUDA software implementation.

Images and movies

 

BibTex references

@InProceedings{ZWW20,
  author       = {Zellmann, Stefan and Weier, Martin and Wald, Ingo},
  title        = {Accelerating Force-Directed Graph Drawing with RT Cores},
  booktitle    = {Accepted at IEEE Visualization (Short Papers)},
  year         = {2020},
}

Other publications in the database

» Martin Weier