Optimal morphs of planar orthogonal drawings II

Van Goethem and Verbeek recently described an algorithm that morphs between two planar orthogonal drawings $\Gamma_I$ and $\Gamma_O$ of a connected graph $G$ of complexity $n$, while preserving planarity, orthogonality, and linear complexity of the drawing during the morph. Necessarily drawings $\Gamma_I$ and $\Gamma_O$ must be equivalent; there exists a homeomorphism of the plane that transforms $\Gamma_I$ into $\Gamma_O$. The algorithm of van Goethem and Verbeek uses a linear number of linear morphs, however, if the graph $G$ is disconnected, then their method requires $O(n^{1.5})$ linear morphs. In this paper we present a refined version of their approach that allows us to also morph between two planar orthogonal drawings of a disconnected graph with a linear number of linear morphs while preserving planarity, orthogonality, and linear complexity.

Van Goethem and Verbeek measure the structural difference between the two drawings in terms of the so-called \emph{spirality} $s = O(n)$ of $\Gamma_I$ relative to $\Gamma_O$ and describe a morph from $\Gamma_I$ to $\Gamma_O$ using $O(s)$ linear morphs. We show how to combine all intermittent morphs that act on links of spirality $s$ into one single linear morph and prove that $s+1$ linear morphs are always sufficient to morph between two planar orthogonal drawings, even for a disconnected graph. The resulting morphs are quite natural and visually pleasing.