Morphing Planar Graph Drawings Through 3D
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909515411095552 |
|---|---|
| author | Buchin, Kevin Evans, Will Frati, Fabrizio Kostitsyna, Irina Löffler, Maarten Ophelders, Tim Wolff, Alexander |
| author_facet | Buchin, Kevin Evans, Will Frati, Fabrizio Kostitsyna, Irina Löffler, Maarten Ophelders, Tim Wolff, Alexander |
| contents | In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-line drawings of an $n$-vertex planar graph, there exists a piecewise-linear crossing-free 3D morph with $O(n^2)$ steps that transforms one drawing into the other. We also give some evidence why it is difficult to obtain a linear lower bound (which exists in 2D) for the number of steps of a crossing-free 3D morph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_05384 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Morphing Planar Graph Drawings Through 3D Buchin, Kevin Evans, Will Frati, Fabrizio Kostitsyna, Irina Löffler, Maarten Ophelders, Tim Wolff, Alexander Computational Geometry Data Structures and Algorithms In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-line drawings of an $n$-vertex planar graph, there exists a piecewise-linear crossing-free 3D morph with $O(n^2)$ steps that transforms one drawing into the other. We also give some evidence why it is difficult to obtain a linear lower bound (which exists in 2D) for the number of steps of a crossing-free 3D morph. |
| title | Morphing Planar Graph Drawings Through 3D |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2210.05384 |