2019/08/22 by Arthur van Goethem, van Goethem, Arthur, Bettina Speckmann +3
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1908.08365
openalex publication_date 2019/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Van Goethem and Verbeek recently showed how to morph between two planar orthogonal drawings ΓI and ΓO of a connected graph G while preserving planarity, orthogonality, and the complexity of the drawing during the morph. Necessarily drawings ΓI and ΓO must be equivalent, that is, there exists a homeomorphism of the plane that transforms ΓI into ΓO. Van Goethem and Verbeek use O(n) linear morphs, where n is the maximum complexity of the input drawings. However, if the graph is disconnected their method requires O(n1.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 O(n) linear morphs while preserving planarity, orthogonality, and linear complexity of the intermediate drawings. Van Goethem and Verbeek measure the structural difference between the two drawings in terms of the so-called spirality s = O(n) of ΓI relative to ΓO and describe a morph from ΓI to ΓO using O(s) linear morphs. We prove that s+1 linear morphs are always sufficient to morph between two planar orthogonal drawings, even for disconnected graphs. The resulting morphs are quite natural and visually pleasing.