| dc.contributor.author | Gove, Robert | en_US |
| dc.contributor.editor | Gleicher, Michael and Viola, Ivan and Leitte, Heike | en_US |
| dc.date.accessioned | 2019-06-02T18:29:03Z | |
| dc.date.available | 2019-06-02T18:29:03Z | |
| dc.date.issued | 2019 | |
| dc.identifier.issn | 1467-8659 | |
| dc.identifier.uri | https://doi.org/10.1111/cgf.13724 | |
| dc.identifier.uri | https://diglib.eg.org:443/handle/10.1111/cgf13724 | |
| dc.description.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/ | en_US |
| dc.publisher | The Eurographics Association and John Wiley & Sons Ltd. | en_US |
| dc.subject | Human | |
| dc.subject | centered computing | |
| dc.subject | Graph drawings | |
| dc.subject | Empirical studies in visualization | |
| dc.title | A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts | en_US |
| dc.description.seriesinformation | Computer Graphics Forum | |
| dc.description.sectionheaders | Graphs and Networks | |
| dc.description.volume | 38 | |
| dc.description.number | 3 | |
| dc.identifier.doi | 10.1111/cgf.13724 | |
| dc.identifier.pages | 739-751 | |
