Morphing Planar Graphs in Spherical Space

Kobourov, Stephen G. and Landis, Matthew (2007) Morphing Planar Graphs in Spherical Space. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 306-317 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_30).

Full text not available from this repository.

Abstract

We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and intersection-free morph between two sphere drawings of a maximally planar graph, provided that both sphere drawings have convex inscribed polytopes, where sphere drawings are the spherical equivalent of plane drawings: intersection-free geodesic-arc drawings. In addition, we describe a morphing algorithm along with its implementation. Movies of sample morphs can be found at http://www.cs.arizona.edu/~mlandis/smorph.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_30
Classifications:M Methods > M.999 Others
P Styles > P.060 3D
ID Code:785

Repository Staff Only: item control page

References

P. Alfeld, M. Neamtu, and L. L. Schumaker. Bernstein-Bezier polynomials on circle, spheres, and sphere-like surfaces. Computer Aided Geometric Design Journal, 13:333-349, 1996.

B. Aronov, R. Seidel, and D. Souvaine. On compatible triangulations of simple polygons. Computational Geometry: Theory and Applications, 3:27-35, 1993.

T. C. Biedl, A. Lubiw, and M. J. Spriggs. Morphing planar graphs while preserving edge directions. In 13th Symposium on Graph Drawing (GD), pages 13-24, 2005.S. S. Cairns. Deformations of plane rectilinear complexes. American Math. Monthly, 51:247-252, 1944.

H. Coxeter. Introduction to Geometry. Wiley, 1961.

C. Erten, S. G. Kobourov, and C. Pitta. Intersection-free morphing of planar graphs. In 11th Symposium on Graph Drawing, pages 320-331, 2003.

M. Floater and C. Gotsman. How to morph tilings injectively. Journal of Computational and Applied Mathematics, 101:117-129, 1999.

J. Gomes, L. Darsa, B. Costa, and D. M. Vello. Warping and Morphing of Graphical Objects. Morgan Kaufmann, 1999.

C. Gotsman, X. Gu, and A. Sheffer. Fundamentals of spherical parameterization for 3D meshes. In SIGGRAPH '03, pages 358-363, 2003.

C. Gotsman and V. Surazhsky. Guaranteed intersection-free polygon morphing. Computers and Graphics, 25(1):67-75, Feb. 2001.

J. F. Hughes. Scheduled Fourier volume morphing. Computer Graphics, 26(2):43-46, July 1992.

A. Lubiw, M. Petrick, and M. Spriggs. Morphing orthogonal planar graph drawings. In 17th Symposium on Discrete Algorithms (SODA), pages 222-230, 2006.

T. Samoilov and G. Elber. Self-intersection elimination in metamorphosis of two-dimensional curves. The Visual Computer, 14:415-428, 1998.

T. W. Sederberg and E. Greenwood. A physically based approach to 2-D shape blending. In SIGGRAPH, pages 25-34, July 1992.

V. Surazhsky and C. Gotsman. Controllable morphing of compatible planar triangulations. ACM Transactions on Graphics, 20(4):203-231, Oct. 2001.

C. Thomassen. Deformations of plane graphs. J. Combin. Theory Ser. B, 34:244-257, 1983.

W. T. Tutte. How to draw a graph. Proc. London Math. Society, 13(52):743-768, 1963.