Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

A Simple and Powerful Heuristic for Speeding Up Force-Directed Graph Layout

Published

Author(s)

John V. Cugini, D L. Banks

Abstract

Force-directed layout is a commonly used technique to generate visually pleasing representations of graphs. The calculation time for direct implementation is, however, proportional to the square of the number of nodes, thus limiting its usefulness to small and medium-sized graphs, especially for interactive applications. We present a very simple heuristic for accelerating the performance of force-directed layout. Resulting improvements are typically between 15- and 20-fold. We analyze the conditions under which the heuristic works and present a statistical model for computing the expected speedup.
Citation
International Conference on Computer Graphics and Interactive Techniques

Keywords

designed experiment, force-directed algorithm, graph drawing, graph layout

Citation

Cugini, J. and Banks, D. (1999), A Simple and Powerful Heuristic for Speeding Up Force-Directed Graph Layout, International Conference on Computer Graphics and Interactive Techniques (Accessed April 15, 2024)
Created October 20, 1999, Updated February 17, 2017