Morphing Planar Graph Drawings EfficientlyAngelini, Patrizio and Frati, Fabrizio and Patrignani, Maurizio and Roselli, Vincenzo (2013) Morphing Planar Graph Drawings Efficiently. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 4960(Official URL: http://dx.doi.org/10.1007/9783319038414_5). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_5
AbstractA morph between two straightline 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 straightline drawings. Namely, at SODA 2013, Alamdari et al. [1] proved that any two planar straightline 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 straightline 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 straightline drawings of a seriesparallel graph.
Actions (login required)
