Optimal Morphs of Planar Orthogonal Drawings

Abstract

We describe an algorithm that morphs between two planar orthogonal drawings Gamma_I and Gamma_O of a connected graph G, while preserving planarity and orthogonality. Necessarily Gamma_I and Gamma_O share the same combinatorial embedding. Our morph uses a linear number of linear morphs (linear interpolations between two drawings) and preserves linear complexity throughout the process, thereby answering an open question from Biedl et al. [Biedl et al., 2013].
Our algorithm first unifies the two drawings to ensure an equal number of (virtual) bends on each edge. We then interpret bends as vertices which form obstacles for so-called wires: horizontal and vertical lines separating the vertices of Gamma_O. We can find corresponding wires in Gamma_I that share topological properties with the wires in Gamma_O. The structural difference between the two drawings can be captured by the spirality of the wires in Gamma_I, which guides our morph from Gamma_I to Gamma_O.