Fast Interactive 3-D Graph Visualization

Bruß, Ingo and Frick, Arne (1996) Fast Interactive 3-D Graph Visualization. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 99-110 (Official URL: http://dx.doi.org/10.1007/BFb0021794).

Full text not available from this repository.

Abstract

We present a 3-D version of GEM [6],a randomized adaptive layout algorithm for nicely drawing undirected graphs, based on the spring-embedder paradigm [4]. The new version, GEM-3D, contains several improvements besides the adaptation to 3-D geometry. The main result of this work is that for the first time, 3-D layout and presentation techniques are combined available at interactive speed. Even large real-life graphs with hundreds of vertices can be meaningfully displayed by enhancing the presentation with additional visual clues (color, perspective and light) and the possibility of interactive user navigation. In the demonstration, we interactively visualize many graphs (artificial and real-world) of different size and complexity to support our claims. We show that GEM-3D is capable of producing a textbook-like drawing of the PETERSEN graph, a notoriously hard case for automatic drawing tools. To the best of our knowledge, this has not been achieved before by automatic layout algorithms purely based on heuristics.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021794
Classifications:M Methods > M.300 Dynamic / Incremental / Online
P Styles > P.060 3D
ID Code:51

Repository Staff Only: item control page

References

Ingo W. Bruß. Konzeption und Realisierung einer Visualisierungskomponente für komplexe Datenstrukturen unter dem Werkzeug CAKETool. Master's thesis, Universität Karlsruhe, 1995.

R.F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. In Proceedings of Graph Drawing'94, volume 894 of LNCS, pages 1-11. Springer, 1994.

R. Davidson and David Harel. Drawing graphs nicely using simulated annealing. Technical Report CS89-13, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, 1989. revised July 1993, to appear in Communications of the ACM.

P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

Kim M. Fairchild, Steven E. Poltrock, and George W. Furmas. SemNet: Three-Dimensional Graphic Representations of Large Knowledge Bases, chapter 5. Lawrence Erlbaum associates, 1988.

Arne K. Frick, Heiko Mehldau, and Andreas Ludwig. A fast adaptive layout algorithm for undirected graphs. In Proceedings of Graph Drawing'94, volume 894 of LNCS, pages 388-403. Springer, 1994.

T.M.J. Fruchterman and E.M. Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, 21, 1991.

J.G. Hollands, T.T. Carey, M.L. Matthews, and C.A. McCann. Presenting a graphical network: A comparison of performance using fisheye and scrolling views. In Proceedings of the 3rd International Conference on Human-Computer Interaction, pages 313-320, September 1989.

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31, 1989.

Donald E. Knuth. The Stanford GraphBase: A Platform for Combinatorial Computing. ACM Press, New York, 1993.

J.D. Mackinlay, George G. Robertson, and S.K. Card. The perspective wall: Detail and context smoothly integrated. In Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems, pages 173-179. ACM, 1991.

Cathleen McGrath, Jim Blythe, and David Krackhardt. The effect of graph layout on inference from social network data. In Proceedings of GD'95, 1995.

Burkhard Monien, Friedhelm Ramme, and Helmut Salmen. A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs. In Proceedings of GD'95, 1995.

Helen C. Purchase, Robert F. Cohen, and Murray I. James. Validating graph drawing aesthetics. In Proceedings of GD'95, 1995.

S.P. Reiss. 3-D Visualization of Program Information. In R. Tamassia and I. Tollis, editors, Graph Drawing DIMACS International Workshop GD'94, number 894 in LNCS, pages 12-24. Springer Verlag, 1994.

George G. Robertson, J.D. Mackinlay, and S.K. Card. Cone trees: Animated 3-D visualizations of hierarchical information. In Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems. ACM, 1991.

Manojit Sarkar and Marc H. Brown. Graphical fisheye views of graphs. Comm. of the ACM, 37(12):73-84, December 1994.