Abstract
We consider the problem of morphing between two planar drawings of the same triangulated graph, maintaining straight-line planarity. A paper in SODA 2013 gave a morph that consists of O(n 2) steps where each step is a linear morph that moves each of the n vertices in a straight line at uniform speed [1]. However, their method imitates edge contractions so the grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes. Using Schnyder embeddings, we are able to morph in O(n 2) linear morphing steps and improve the grid size to O(n)×O(n) for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. The morphs are visually attractive. Our method involves implementing the basic “flip” operations of Schnyder woods as linear morphs.
Chapter PDF
Similar content being viewed by others
References
Alamdari, S., Angelini, P., Chan, T.M., Di Battista, G., Frati, F., Lubiw, A., Patrignani, M., Roselli, V., Singla, S., Wilkinson, B.T.: Morphing planar graph drawings with a polynomial number of steps. In: Proc. of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1656–1667. SIAM (2013)
Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Roselli, V.: Morphing planar graph drawings optimally. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 126–137. Springer, Heidelberg (2014)
Barrera-Cruz, F.: Morphing planar triangulations. Ph.D. thesis, University of Waterloo (2014)
Bonichon, N., Gavoille, C., Hanusse, N., Ilcinkas, D.: Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 266–278. Springer, Heidelberg (2010)
Brehm, E.: 3-orientations and Schnyder 3-tree-decompositions. Master’s thesis, FB Mathematik und Informatik, Freie Universität Berlin (2000)
Cairns, S.S.: Deformations of plane rectilinear complexes. The American Mathematical Monthly 51(5), 247–252 (1944)
Dhandapani, R.: Greedy drawings of triangulations. Discrete & Computational Geometry 43(2), 375–392 (2010)
Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order 18(1), 19–37 (2001)
Felsner, S.: Geodesic embeddings and planar graphs. Order 20(2), 135–150 (2003)
Felsner, S., Zickfeld, F.: Schnyder woods and orthogonal surfaces. Discrete & Computational Geometry 40(1), 103–126 (2008)
Felsner, S.: Lattice structures from planar graphs. The Electronic Journal of Combinatorics 11(1), 15 (2004)
Felsner, S., Zickfeld, F.: On the number of α-orientations. In: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, vol. 4769, pp. 190–201. Springer, Heidelberg (2007)
Floater, M.S., Gotsman, C.: How to morph tilings injectively. Journal of Computational and Applied Mathematics 101(1), 117–129 (1999)
Ossona de Mendez, P.: Orientations bipolaires. Ph.D. thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris (1994)
Schnyder, W.: Planar graphs and poset dimension. Order 5, 323–343 (1989)
Schnyder, W.: Embedding planar graphs on the grid. In: Proc. of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 138–148. SIAM, Philadelphia (1990)
Surazhsky, V., Gotsman, C.: Controllable morphing of compatible planar triangulations. ACM Trans. Graph. 20(4), 203–231 (2001)
Thomassen, C.: Deformations of plane graphs. Journal of Combinatorial Theory, Series B 34(3), 244–257 (1983)
Tutte, W.T.: How to draw a graph. Proc. London Math. Soc. 13(3), 743–768 (1963)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barrera-Cruz, F., Haxell, P., Lubiw, A. (2014). Morphing Schnyder Drawings of Planar Triangulations. In: Duncan, C., Symvonis, A. (eds) Graph Drawing. GD 2014. Lecture Notes in Computer Science, vol 8871. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45803-7_25
Download citation
DOI: https://doi.org/10.1007/978-3-662-45803-7_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45802-0
Online ISBN: 978-3-662-45803-7
eBook Packages: Computer ScienceComputer Science (R0)