Share Email Print

Proceedings Paper

G-Space: a linear time graph layout
Author(s): Brian Wylie; Jeffrey Baumes; Timothy M. Shead
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

We describe G-Space, a straightforward linear time layout algorithm that draws undirected graphs based purely on their topological features. The algorithm is divided into two phases. The first phase is an embedding of the graph into a 2-D plane using the graph-theoretical distances as coordinates. These coordinates are computed with the same process used by HDE (High-Dimensional Embedding) algorithms. In our case we do a Low-Dimensional Embedding (LDE), and directly map the graph distances into a two dimensional geometric space. The second phase is the resolution of the many-to-one mappings that frequently occur within the low dimensional embedding. The resulting layout appears to have advantages over existing methods: it can be computed rapidly, and it can be used to answer topological questions quickly and intuitively.

Paper Details

Date Published: 28 January 2008
PDF: 12 pages
Proc. SPIE 6809, Visualization and Data Analysis 2008, 68090E (28 January 2008); doi: 10.1117/12.768012
Show Author Affiliations
Brian Wylie, Sandia National Labs. (United States)
Jeffrey Baumes, Kitware, Inc. (United States)
Timothy M. Shead, Sandia National Labs. (United States)

Published in SPIE Proceedings Vol. 6809:
Visualization and Data Analysis 2008
Katy Börner; Matti T. Gröhn; Jinah Park; Jonathan C. Roberts, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?