Translator Disclaimer
28 January 2008 G-Space: a linear time graph layout
Author Affiliations +
Proceedings Volume 6809, Visualization and Data Analysis 2008; 68090E (2008)
Event: Electronic Imaging, 2008, San Jose, California, United States
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.
© (2008) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
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);

Back to Top