Name
Abstract | ||
|---|---|---|
We describe an algorithm that morphs between two planar orthogonal drawings ΓiΓiGamma_i and ΓoΓoGamma_o of a graph GGG, while preserving planarity and orthogonality. Necessarily ΓiΓiGamma_i and ΓoΓoGamma_o share the same combinatorial embedding. Our morph uses a linear number of horizontal and vertical 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ΓoGamma_o. These wires define homotopy classes with respect to the vertices of GGG (for the combinatorial embedding of GGG shared by ΓiΓiGamma_i and ΓoΓoGamma_o). These homotopy classes can be represented by orthogonal polylines in ΓiΓiGamma_i. We argue that the structural difference between the two drawings can be captured by the emph{spirality} of the wires in ΓiΓiGamma_i, which guides our morph from ΓiΓiGamma_i to ΓoΓoGamma_o. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.SoCG.2018.42 | Symposium on Computational Geometry |
DocType | Volume | Citations |
Conference | abs/1801.02455 | 1 |
PageRank | References | Authors |
0.36 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arthur van Goethem | 1 | 12 | 3.59 |
| Kevin Verbeek | 2 | 74 | 13.18 |