G-Space: a linear time graph layout

Brian Wylie; Jeffrey Baumes; Timothy M. Shead

doi:10.1117/12.768012

28 January 2008 G-Space: a linear time graph layout

Brian Wylie, Jeffrey Baumes, Timothy M. Shead

Proceedings Volume 6809, Visualization and Data Analysis 2008; 68090E (2008) https://doi.org/10.1117/12.768012
Event: Electronic Imaging, 2008, San Jose, California, United States

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.

Citation Download Citation

Brian Wylie, Jeffrey Baumes, and Timothy M. Shead "G-Space: a linear time graph layout", Proc. SPIE 6809, Visualization and Data Analysis 2008, 68090E (28 January 2008); https://doi.org/10.1117/12.768012

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available