• Login
    View Item 
    •   Eurographics DL Home
    • Computer Graphics Forum
    • Volume 38 (2019)
    • 38-Issue 3
    • View Item
    •   Eurographics DL Home
    • Computer Graphics Forum
    • Volume 38 (2019)
    • 38-Issue 3
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    v38i3pp739-751.pdf (20.13Mb)
    1195-file1.zip (35.14Mb)
    Date
    2019
    Author
    Gove, Robert ORCID
    Pay-Per-View via TIB Hannover:

    Try if this item/paper is available.

    Metadata
    Show full item record
    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/
    BibTeX
    @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}
    }
    URI
    https://doi.org/10.1111/cgf.13724
    https://diglib.eg.org:443/handle/10.1111/cgf13724
    Collections
    • 38-Issue 3

    Eurographics Association copyright © 2013 - 2023 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA
     

     

    Browse

    All of Eurographics DLCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    BibTeX | TOC

    Create BibTeX Create Table of Contents

    Eurographics Association copyright © 2013 - 2023 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA