Abstract
Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of planar graphs. Our algorithm uses a combination of different techniques to achieve smooth transformations: rigid morphing, compatible triangulations, as well as morphing based on interpolation of the convex representations of the graphs. Our algorithm can morph between drawings with straight-line segments, bends, and curves. Our system is implemented in Java and available as an applet at http://gmorph.cs.arizona.edu.
This work is partially supported by the NSF under grant ACR-0222920.
Chapter PDF
Similar content being viewed by others
References
Aronov, B., Seidel, R., Souvaine, D.: On compatible triangulations of simple polygons. CGTA: Computational Geometry: Theory and Applications 3, 27–35 (1993)
Beier, T., Neely, S.: Feature-based image metamorphosis. In: Catmull, E.E. (ed.) Computer Graphics (SIGGRAPH 1992 Proceedings), July 1992, vol. 27, pp. 35–42 (1992)
Bespamyatnikh, S.: An optimal morphing between polylines. IJCGA: International Journal of Computational Geometry and Applications 12(3), 217–228 (2002)
Cairns, S.S.: Deformations of plane rectilinear complexes. American Math. Monthly 51, 247–252 (1944)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)
Floater, M.: Mean value coordinates. Comp. Aided Geom. Design 20, 19–27 (2003)
Floater, M., Gotsman, C.: How to morph tilings injectively. Journal of Computational and Applied Mathematics 101, 117–129 (1999)
Friedrich, C.: The ffgraph library. Technical Report 9520, Universität Passau (1995)
Friedrich, C., Eades, P.: The Marey graph animation tool demo. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 396–406. Springer, Heidelberg (2001)
Friedrich, C., Eades, P.: Graph drawing in motion. Journal of Graph Algorithms and Applications 6(3), 353–370 (2002)
Friedrich, C., Houle, M.E.: Graph drawing in motion II. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 220–231. Springer, Heidelberg (2002)
Goldstein, E., Gotsman, C.: Polygon morphing using a multiresolution representation. In: Graphics Interface 1995, pp. 247–254 (1995)
Gomes, J., Darsa, L., Costa, B., Vello, D.M.: Warping and Morphing of Graphical Objects. Morgan Kaufmann, San Francisco (1999)
Gotsman, C., Surazhsky, V.: Guaranteed intersection-free polygon morphing. Computers and Graphics 25(1), 67–75 (2001)
He, T., Wang, S., Kaufman, A.: Wavelet-based volume morphing. In: Proceedings of the Conference on Visualization, pp. 85–92 (1994)
Huang, M.L., Eades, P.: A fully animated interactive system for clustering and navigating huge graphs. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 374–383. Springer, Heidelberg (1999)
Hughes, J.F.: Scheduled Fourier volume morphing. Computer Graphics 26(2), 43–46 (1992)
Kaufmann, M., Wagner, D.: Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)
Samoilov, T., Elber, G.: Self-intersection elimination in metamorphosis of twodimensional curves. The Visual Computer 14, 415–428 (1998)
Sederberg, T.W., Gao, P., Wang, G., Mu, H.: 2D shape blending: An intrinsic solution to the vertex path problem. In: Computer Graphics (SIGGRAPH 1993 Proceedings), vol. 27, pp. 15–18 (1993)
Sederberg, T.W., Greenwood, E.: A physically based approach to 2-D shape blending. In: Catmull, E.E. (ed.) Computer Graphics (SIGGRAPH 1992 Proceedings), July 1992, vol. 26, pp. 25–34 (1992)
Shapira, M., Rappoport, A.: Shape blending using the star-skeleton representation. IEEE Computer Graphics and Applications 15(2), 44–50 (1995)
Shoemake, K., Duff, T.: Matrix animation and polar decomposition. In: Proceedings of Graphics Interface 1992, May 1992, pp. 258–264 (1992)
Surazhsky, V., Gotsman, C.: Controllable morphing of compatible planar triangulations. ACM Transactions on Graphics 20(4), 203–231 (2001)
Tal, A., Elber, G.: Image morphing with feature preserving texture. Computer Graphics Forum 18(3), 339–348 (1999) ISSN 1067-7055
Thomassen, C.: Deformations of plane graphs. J. Combin. Theory Ser. B 34, 244–257 (1983)
Tutte, W.T.: How to draw a graph. Proc. London Math. Society 13(52), 743–768 (1963)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Erten, C., Kobourov, S.G., Pitta, C. (2004). Intersection-Free Morphing of Planar Graphs. In: Liotta, G. (eds) Graph Drawing. GD 2003. Lecture Notes in Computer Science, vol 2912. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24595-7_30
Download citation
DOI: https://doi.org/10.1007/978-3-540-24595-7_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20831-0
Online ISBN: 978-3-540-24595-7
eBook Packages: Springer Book Archive