Morphing Planar Graphs While Preserving Edge Directions

Biedl, Therese and Lubiw, Anna and Spriggs, Michael (2006) Morphing Planar Graphs While Preserving Edge Directions. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/11618058_2).

Full text not available from this repository.

Abstract

Two straight-line drawings P,Q of a graph (V,E) are called parallel if, for every edge (u,v) in E, the vector from u to v has the same direction in both P and Q. We study problems of the form: given simple, parallel drawings P,Q does there exist a continuous transformation between them such that intermediate drawings of the transformation remain simple and parallel with P (and Q)? We prove that a transformation can always be found in the case of orthogonal drawings; however, when edges are allowed to be in one of three or more slopes the problem becomes NP-hard.

Item Type:Conference Paper
Additional Information:10.1007/11618058_2
Classifications:P Styles > P.600 Poly-line
P Styles > P.540 Planar
ID Code:676

Repository Staff Only: item control page

References

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

G. Barequet and M. Sharir.: Piecewise-linear interpolation between polygonal slices. Comput. Vis. Image Underst., 63(2):251--272, 1996.

T. Biedl, A. Lubiw, and M. Spriggs.: Parallel morphing of trees and cycles. 15th Canadian Conference on Computational Geometry (CCCG), pages 29--32, 2003.

T. Biedl, A. Lubiw, and M. J. Spriggs.: Angles and lengths in reconfigurations of polygons and polyhedra. Proc. Mathematical Foundations of Computer Science (MFCS'04), pages 748--759, 2004.

T. Biedl, A. Lubiw, and Michael J. Spriggs.: Angles and lengths in reconfigurations of polygons and polyhedra, 2005. http://arxiv.org/

J.~Branke.: Dynamic graph drawing. D. Kaufmann and D. Wagner, editors, Drawing Graphs -- Methods and Models, Lecture Notes in Computer Science 2025, pages 228--246. Springer, 2001.

S. Bridgeman and R. Tamassia.: Difference metrics for interactive orthogonal graph drawing algorithms. Journal of Graph Algorithms and Applications, 4 (3):47--74, 2000.

S. Bridgeman, G. Di Battista, W. Didimo, G. Liotta, R. Tamassia, and L. Vismara.: Turn-regularity and optimal area drawings of orthogonal representations. Computational Geometry, 16(1):53--93, 2000.

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

J. Cantarella, E.D. Demaine, H. Iben, and J. O'Brien.: An energy-driven approach to linkage unfolding. 20th Annual ACM Symposium on Computational Geometry, pages 134--143, 2004.

C. Erten, S. Kobourov, and C. Pitta.: Intersection-free morphing of planar graphs. G. Liotta, editor, Graph Drawing 2003, Lecture Notes in Computer Science 2912, pages 320--331. Springer, 2004.

C. Erten, S. Kobourov, and C.Pitta.: Morphing planar graphs. 20th Annual ACM Symposium on Computational Geometry, pages 451--452, 2004.

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

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. P. Mutzel, M. Jünger, and S. Leipert, editors, Graph Drawing 2001, Lecture Notes in Computer Science 2265, pages 220--231. Springer, 2002.

J. Gomes, L. Darsa, B. Costa, and L. Velho.: Warping and Morphing of Graphical Objects. Morgan Kaufmann, 1999.

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

U. Grenander, Y. Chow, and D. M. Keenan.: Hands: A Pattern Theoretic Study of Biological Shapes (Appendix D). Springer-Verlag, 1991.

L. Guibas, J. Hershberger, and S. Suri.: Morphing simple polygons. Discrete and Computational Geometry, 24(1):1--34, 2000.

T. Lengauer.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990.

A. Lubiw, M. Petrick, and Michael J. Spriggs.: Morphing orthogonal planar graph drawings. Proceedings ACM-SIAM Symposium on Discrete Algorithms, 2006. To appear.

K. Misue, P. Eades, W. Lai, and K. Sugiyama.: Layout adjustment and the mental map. J. Visual Lang. Comput., 6 (2):183--210, 1995.

C. Thomassen.: Deformations of plane graphs. Journal of Combinatorial Theory, Series B: 34:244--257, 1983.