A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts
Loading...
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and John Wiley & Sons Ltd.
Abstract
This paper proposes a linear-time repulsive-force-calculation algorithm with sub-linear auxiliary space requirements, achieving an asymptotic improvement over the Barnes-Hut and Fast Multipole Method force-calculation algorithms. The algorithm, named random vertex sampling (RVS), achieves its speed by updating a random sample of vertices at each iteration, each with a random sample of repulsive forces. This paper also proposes a combination algorithm that uses RVS to derive an initial layout and then applies Barnes-Hut to refine the layout. An evaluation of RVS and the combination algorithm compares their speed and quality on 109 graphs against a Barnes-Hut layout algorithm. The RVS algorithm performs up to 6.1 times faster on the tested graphs while maintaining comparable layout quality. The combination algorithm also performs faster than Barnes-Hut, but produces layouts that are more symmetric than using RVS alone. Data and code: https://osf.io/nb7m8/
Description
@article{10.1111:cgf.13724,
journal = {Computer Graphics Forum},
title = {{A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts}},
author = {Gove, Robert},
year = {2019},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.13724}
}