From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2025-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/12439/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849316443206713344 |
|---|---|
| author | Giuseppe Di Battista Fabrizio Frati |
| author_facet | Giuseppe Di Battista Fabrizio Frati |
| author_sort | Giuseppe Di Battista |
| collection | DOAJ |
| description | 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 | Article |
| id | doaj-art-e5d2bbdef217426c8b4cb9c6cd433e73 |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-e5d2bbdef217426c8b4cb9c6cd433e732025-08-20T03:51:44ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502025-03-01vol. 27:2Combinatorics10.46298/dmtcs.1243912439From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and MorphsGiuseppe Di BattistaFabrizio FratiThe 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.http://dmtcs.episciences.org/12439/pdfcomputer science - computational geometrycomputer science - discrete mathematicscomputer science - data structures and algorithms |
| spellingShingle | Giuseppe Di Battista Fabrizio Frati From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs Discrete Mathematics & Theoretical Computer Science computer science - computational geometry computer science - discrete mathematics computer science - data structures and algorithms |
| title | From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs |
| title_full | From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs |
| title_fullStr | From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs |
| title_full_unstemmed | From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs |
| title_short | From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs |
| title_sort | from tutte to floater and gotsman on the resolution of planar straight line drawings and morphs |
| topic | computer science - computational geometry computer science - discrete mathematics computer science - data structures and algorithms |
| url | http://dmtcs.episciences.org/12439/pdf |
| work_keys_str_mv | AT giuseppedibattista fromtuttetofloaterandgotsmanontheresolutionofplanarstraightlinedrawingsandmorphs AT fabriziofrati fromtuttetofloaterandgotsmanontheresolutionofplanarstraightlinedrawingsandmorphs |