2026-07-25T12:39:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21324 2024-10-28T09:51:06Z ddc:004 open_access

Morphing Planar Graph Drawings via Orthogonal Box Drawings Biedl, Therese Lubiw, Anna Spalding-Jamieson, Jack morphing graph morphing linear morph planar graph drawing orthogonal box drawing orthogonal drawing algorithm 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) × O(n) grid. The planarity-preserving morph is composed of O(n) linear morphs between successive pairs of drawings, each on an O(n) × O(n) grid with a constant number of bends per edge. The algorithm to compute the morph runs in O(n²) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Therese Biedl and Anna Lubiw and Jack Spalding-Jamieson 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.40 urn:nbn:de:0030-drops-213242 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.40 eng https://creativecommons.org/licenses/by/4.0/legalcode