| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Non-Euclidean Spring Embedders
November/December 2005 (vol. 11 no. 6)
pp. 757-767
We present a conceptually simple approach to generalizing force-directed methods for graph layout from Euclidean geometry to Riemannian geometries. Unlike previous work on non-Euclidean force-directed methods, ours is not limited to special classes of graphs, but can be applied to arbitrary graphs. The method relies on extending the Euclidean notions of distance, angle, and force-interactions to smooth non-Euclidean geometries via projections to and from appropriately chosen tangent spaces. In particular, we formally describe the calculations needed to extend such algorithms to hyperbolic and spherical geometries. We also study the theoretical and practical considerations that arise when working with non-Euclidean geometries.
[1] 757 J.W. Anderson, Hyperbolic Geometry. Springer-Verlag, 1999.[2] G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs. Englewood Cliffs, N.J.: Prentice Hall, 1999.[3] P. Eades, “A Heuristic for Graph Drawing,” Congressus Numerantium, vol. 42, pp. 149-160, 1984.[4] D. Eppstein, “Hyperbolic Geometry, Möbius Transformations, and Geometric Optimization,” Proc. MSRI Introductory Workshop Discrete and Computational Geometry, 2003.[5] C. Erten, P.J. Harding, S.G. Kobourov, K. Wampler, and G. Yee, “GraphAEL: Graph Animations with Evolving Layouts,” Proc. 11th Symp. Graph Drawing, pp. 98-110, 2003.[6] T.M.J. Fruchterman and E.M. Reingold, “Graph Drawing by Force-Directed Placement,” Software— Practice and Experience, vol. 21, no. 11, pp. 1129-1164, 1991.[7] P. Gajer, M.T. Goodrich, and S.G. Kobourov, “A Multi-Dimensional Approach to Force-Directed Layouts of Large Graphs,” Computational Geometry: Theory and Applications, vol. 29, no. 1, pp. 3-18, 2004.[8] C. Gotsman, X. Gu, and A. Sheffer, “Fundamentals of Spherical Parameterization for 3D Meshes,” ACM Trans. Graphics, vol. 22, pp. 358-363, 2003.[9] D. Harel and Y. Koren, “A Fast Multi-Scale Method for Drawing Large Graphs,” J. Graph Algorithms and Applications, vol. 6, pp. 179-202, 2002.[10] I. Herman, G. Melançon, and M.S. Marshall, “Graph Visualization and Navigation in Information Visualization: A Survey,” IEEE Trans. Visualization and Computer Graphics, vol. 6, no. 1, pp. 24-43, Jan.-Mar. 2000.[11] T. Kamada and S. Kawai, “An Algorithm for Drawing General Undirected Graphs,” Information Processing Letters, vol. 31, no. 1, pp. 7-15, Apr. 1989.[12] M. Kaufmann and D. Wagner, Drawing Graphs: Methods and Models. Springer-Verlag, 2001.[13] S.G. Kobourov and K. Wampler, “Non-Euclidean Spring Embedders,” Proc. 10th Ann. IEEE Symp. Information Visualization (InfoVis), pp. 207-214, 2004.[14] Y. Koren, L. Carmel, and D. Harel, “ACE: A Fast Multiscale Eigenvector Computation for Drawing Huge Graphs,” Proc. IEEE Symp. Information Visualization, pp. 123-144, 2002.[15] Proc. Seventh Int'l Symp. Graph Drawing, J. Kratochvil, ed., 1999.[16] J. Lamping, R. Rao, and P. Pirolli, “A focus+context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies,” Proc. Computer Human Interaction, pp. 401-408, 1995.[17] T. Munzner, “H3: Laying Out Large Directed Graphs in 3D Hyperbolic Space,” Proc. IEEE Symp. Information Visualization, L. Lavagno and W. Reisig, eds., pp. 2-10, 1997.[18] T. Munzner, “Drawing Large Graphs with h3viewer and Site Manager,” Proc. Sixth Symp. Graph Drawing, pp. 384-393, 1998.[19] T. Munzner and P. Burchard, “Visualizing the Structure of the World Wide Web in 3D Hyperbolic Space,” Proc. Symp. Virtual Reality Modeling Language, pp. 33-38, 1996.[20] J. Ontrup and H. Ritter, “Hyperbolic Self-Organizing Maps for Semantic Navigation,” Proc. Advances in Neural Information Processing Systems 14, pp. 1417-1424, 2001.[21] D.I. Ostry, “Some Three-Dimensional Graph Drawing Algorithms,” master's thesis, Univ. of Newcastle, Australia, 1996.[22] H. Ritter, “Self-Organizing Maps on Non-Euclidean Spaces,” Kohonen Maps, S. Oja and E. Kaski, eds., pp. 97-110, 1999.[23] K. Sugiyama and K. Misue, “Graph Drawing by the Magnetic Spring Model,” J. Visual Languages and Computing, vol. 6, no. 3, pp. 217-231, 1995.[24] W.T. Tutte, “How to Draw a Graph,” Proc. London Math. Soc., vol. 13, no. 52, pp. 743-768, 1963.[25] J.J. van Wijk and W.A.A. Nuij, “A Model for Smooth Viewing and Navigation of Large 2D Information Spaces,” IEEE Trans. Visualization and Computer Graphics, vol. 10, no. 4, pp. 447-458, July/Aug. 2004.
Index Terms:
Index Terms- Force-directed algorithms, spring embedders, non-Euclidean geometry, hyperbolic space, spherical space, graph drawing, information visualization.
Citation:
Stephen G. Kobourov, Kevin Wampler, "Non-Euclidean Spring Embedders," IEEE Transactions on Visualization and Computer Graphics, vol. 11, no. 6, pp. 757-767, Nov./Dec. 2005, doi:10.1109/TVCG.2005.103
