Morphing Planar Graph Drawings Optimally

2014/02/18 by Angelini, Patrizio, Da Lozzo, Giordano, Di Battista, Giuseppe +3
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1402.4364

Abstract

We provide an algorithm for computing a planar morph between any two planar straight-line drawings of any n-vertex plane graph in O(n) morphing steps, thus improving upon the previously best known O(n²) upper bound. Further, we prove that our algorithm is optimal, that is, we show that there exist two planar straight-line drawings Γ_s and Γ_t of an n-vertex plane graph G such that any planar morph between Γ_s and Γ_t requires Ω(n) morphing steps.

Related

• Morphing Planar Graphs Drawings Efficiently
• How to morph planar graph drawings
• Optimal Morphs of Planar Orthogonal Drawings II
• Morphing Schnyder drawings of planar triangulations
• Morphing Planar Graph Drawings via Orthogonal Box Drawings