From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917950245568512 |
|---|---|
| author | Di Battista, Giuseppe Frati, Fabrizio |
| author_facet | Di Battista, Giuseppe Frati, Fabrizio |
| contents | The algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the most popular graph drawing algorithms. In this paper, focusing on maximal plane graphs, we prove upper and lower bounds on the resolution of the planar straight-line drawings produced by Floater's algorithm, which is a broad generalization of Tutte's algorithm. Further, we use such results in order to prove a lower bound on the resolution of the drawings of maximal plane graphs produced by Floater and Gotsman's morphing algorithm. Finally, we show that such a morphing algorithm might produce drawings with exponentially-small resolution, even when transforming drawings with polynomial resolution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_09483 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs Di Battista, Giuseppe Frati, Fabrizio Computational Geometry Discrete Mathematics Data Structures and Algorithms The algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the most popular graph drawing algorithms. In this paper, focusing on maximal plane graphs, we prove upper and lower bounds on the resolution of the planar straight-line drawings produced by Floater's algorithm, which is a broad generalization of Tutte's algorithm. Further, we use such results in order to prove a lower bound on the resolution of the drawings of maximal plane graphs produced by Floater and Gotsman's morphing algorithm. Finally, we show that such a morphing algorithm might produce drawings with exponentially-small resolution, even when transforming drawings with polynomial resolution. |
| title | From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs |
| topic | Computational Geometry Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2108.09483 |