Abstract
A morph between two straight-line planar drawings of the same graph is a continuous transformation from the first to the second drawing such that planarity is preserved at all times. Each step of the morph moves each vertex at constant speed along a straight line. Although the existence of a morph between any two drawings was established several decades ago, only recently it has been proved that a polynomial number of steps suffices to morph any two planar straight-line drawings. Namely, at SODA 2013, Alamdari et al. [1] proved that any two planar straight-line drawings of a planar graph can be morphed in O(n 4) steps, while O(n 2) steps suffice if we restrict to maximal planar graphs.
In this paper, we improve upon such results, by showing an algorithm to morph any two planar straight-line drawings of a planar graph in O(n 2) steps; further, we show that a morph with O(n) steps exists between any two planar straight-line drawings of a series-parallel graph.
Part of the research was conducted in the framework of ESF project 10-EuroGIGA-OP-003 GraDR “Graph Drawings and Representations”.
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: SODA 2013, pp. 1656–1667 (2013)
Angelini, P., Cortese, P.F., Di Battista, G., Patrignani, M.: Topological morphing of planar graphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 145–156. Springer, Heidelberg (2009)
Angelini, P., Didimo, W., Kobourov, S., Mchedlidze, T., Roselli, V., Symvonis, A., Wismath, S.: Monotone drawings of graphs with fixed embedding. Algorithmica, 1–25 (2013)
Angelini, P., Frati, F., Patrignani, M., Roselli, V.: Morphing planar graph drawings efficiently. CoRR cs.CG (2013), http://arxiv.org/abs/1308.4291
Angelini, P., Colasante, E., Di Battista, G., Frati, F., Patrignani, M.: Monotone drawings of graphs. J. of Graph Algorithms and Appl. 16(1), 5–35 (2012); In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 13–24. Springer, Heidelberg (2011)
Biedl, T.C., Lubiw, A., Spriggs, M.J.: Morphing planar graphs while preserving edge directions. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 13–24. Springer, Heidelberg (2006)
Cairns, S.S.: Deformations of plane rectilinear complexes. American Math. Monthly 51, 247–252 (1944)
Chazelle, B.: Triangulating a simple polygon in linear time. Discrete & Computational Geometry 6(5), 485–524 (1991)
Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229–233 (1948)
Grunbaum, B., Shephard, G.: The geometry of planar graphs. Cambridge University Press (1981), http://dx.doi.org/10.1017/CBO9780511662157.008
Lubiw, A., Petrick, M.: Morphing planar graph drawings with bent edges. Electronic Notes in Discrete Mathematics 31, 45–48 (2008)
Lubiw, A., Petrick, M., Spriggs, M.: Morphing orthogonal planar graph drawings. In: SODA 2006, pp. 222–230. ACM (2006)
Thomassen, C.: Deformations of plane graphs. J. Comb. Th., Series B 34, 244–257 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Angelini, P., Frati, F., Patrignani, M., Roselli, V. (2013). Morphing Planar Graph Drawings Efficiently. In: Wismath, S., Wolff, A. (eds) Graph Drawing. GD 2013. Lecture Notes in Computer Science, vol 8242. Springer, Cham. https://doi.org/10.1007/978-3-319-03841-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-03841-4_5
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03840-7
Online ISBN: 978-3-319-03841-4
eBook Packages: Computer ScienceComputer Science (R0)