2018/01/08 by Arthur van Goethem, van Goethem, Arthur, Kevin Verbeek +1
Computer Science · Engineering · #3D Shape Modeling and Analysis #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1801.02455
openalex publication_date 2018/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe an algorithm that morphs between two planar orthogonal drawings ΓI and ΓO of a connected graph G, while preserving planarity and orthogonality. Necessarily ΓI and Γ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. 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 ΓO. We can find corresponding wires in ΓI that share topological properties with the wires in ΓO. The structural difference between the two drawings can be captured by the spirality of the wires in ΓI, which guides our morph from ΓI to ΓO.