Morphing Planar Graph Drawings via Orthogonal Box Drawings
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910592836567040 |
|---|---|
| author | Biedl, Therese Lubiw, Anna Spalding-Jamieson, Jack |
| author_facet | Biedl, Therese Lubiw, Anna Spalding-Jamieson, Jack |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04074 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Morphing Planar Graph Drawings via Orthogonal Box Drawings Biedl, Therese Lubiw, Anna Spalding-Jamieson, Jack Computational Geometry 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. |
| title | Morphing Planar Graph Drawings via Orthogonal Box Drawings |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2409.04074 |