A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts (Unknown language)

In: Computer Graphics Forum   ;  38 ,  3  ;  739-751  ;  2019
  • ISSN:
  • Conference paper  /  Electronic Resource

How to get this document?

Download
Commercial Copyright fee: €14.50 Basic fee: €4.00 Total price: €18.50
Academic Copyright fee: €4.50 Basic fee: €2.00 Total price: €6.50

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/

  • Title:
    A Random Sampling O(n) Force-calculation Algorithm for Graph Layouts
  • Author / Creator:
  • Published in:
    Computer Graphics Forum ; 38 ; 3 ; 739-751
  • Publisher:
    The Eurographics Association
  • Year of publication:
    2019
  • Size:
    13 pages
  • ISSN:
  • DOI:
  • Type of media:
    Conference paper
  • Type of material:
    Electronic Resource
  • Language:
    Unknown language
  • Source:
  • Export:
Feedback