Morphing Planar Graph Drawings via Orthogonal Box Drawings
<|reference_start|>Morphing Planar Graph Drawings via Orthogonal Box Drawings: We give an algorithm to morph planar graph drawings that achieves small grid size at the expense of allowing a constant number of bends on each edge. The input is an $n$-vertex planar graph and two planar straight-line drawings of the graph on an $O(n) \times O(n)$ grid. The planarity-preserving morph is composed of $O(n)$ linear morphs between successive pairs of drawings, each on an $O(n) \times O(n)$ grid with a constant number of bends per edge. The algorithm to compute the morph runs in $O(n^2)$ time on a word RAM model with standard arithmetic operations -- in particular no square roots or cube roots are required.   The first step of the algorithm is to morph each input drawing to a planar orthogonal box drawing where vertices are represented by boxes and each edge is drawn as a horizontal or vertical segment. The second step is to morph between planar orthogonal box drawings. This is done by extending known techniques for morphing planar orthogonal drawings with point vertices.<|reference_end|>
@article{biedl2024morphing,
    title={Morphing Planar Graph Drawings via Orthogonal Box Drawings},
    author={Therese Biedl, Anna Lubiw, Jack Spalding-Jamieson},
    journal={arXiv preprint arXiv:2409.04074},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.04074},
    primaryClass={cs.CG}
}