Intersection-Free Morphing of Planar Graphs

Erten, Cesim and Kobourov, Stephen G. and Pitta, Chandan (2004) Intersection-Free Morphing of Planar Graphs. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 320-331 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_30).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_30
Classifications:J Applications > J.999 Others
M Methods > M.200 Animation
ID Code:462

Repository Staff Only: item control page

References

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

T. Beier and S. Neely. Feature-based image metamorphosis. In E.E. Catmull, editor, Computer Graphics (SIGGRAPH '92 Proceedings), volime 27, pages 35-42, July 1992.

S. Bespamyatnikh. An optimal morphing between polylines. IJCGA: International Journal of Computational Geometry and Applications, 12(3):217-228, 2002.

S. S. Cairns. Deformations of plane rectilinear complexes. American Math. Monthly, 51:247-252, 1944.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs, NJ, 1999.

M. Floater. Mean value coordinates. Comp. Aided Geom. Design, 20:19-27, 1003.

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

C. Friedrich. The ffgraph library. Technical Report 9520, Universität Passau, 1995.

C. Friedrich and P. Eades. The Marey graph animation tool demo. In Proceedings of the 8th Symposium on Graph Drawing (GD), pages 396-406, 2000.

C. Friedrich and P. Eades. Graph drawing in motion. Journal of Graph Algorithms and Applications, 6(3):353-370, 2002.

C. Friedrich and M. E. Houle. Graph drawing in motion II. In Proceedings of the 9th Symposium on Graph Drawing (GD), pages 220-231, 2001.

E. Goldstein and C. Gotsman. Polygon morphing using a multiresolution representation. In Graphics Interface '95, pages 247-254, 1995.

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

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

T. He, S. Wang, and A. Kaufman. Wavelet-based volume morphing. In Proceedings of the Conference on Visualization, pages 85-92, 1994.

M. L. Huang and P. Eades. A fully animated interactive system for clustering and navigating huge graphs. In Proceedings of the 6th Symposium on Graph Drawing (GD), pages 374-383, 1998.

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

M. Kaufmann and D. Wagner. Drawing graphs: methods and models, volume 2025 of Lecture Notes in Computer Science. Springer-Verlag, 2001.

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

T. W. Sederberg, P. Gao, G. Wang, and H. Mu. 2D shape blending: An intrinsic solution to the vertex path problem. In Computer Graphics (SIGGRAPH '93 Proceedings), volume 27, pages 15-18, 1993.

T. W. Sederberg and E. Greenwood. A physically based approach to 2-D shape blending. In E. E. Catmull, editor, Computer Graphics (SIGGRAPH '92 Proceedings), volume 26, pages 25-34, July 1992.

M. Shapira and A. Rappoport. Shape blending using the star-skeleton representation. IEEE Computer Graphics and Applications, 15(2):44-50, Mar. 1995.

K. Shoemake and T. Duff. Matrix animation and polar decomposition. In Proceedings of Graphics Interface '92, pages 258-264, May 1992.

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

A. Tal and G. Elber. Image morphing with feature preserving texture. Computer Graphics Forum, 18(3):339-348, Sept. 1999. ISSN 1067-7055.

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.