Back to Search
Start Over
From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-Line Drawings and Morphs
- Source :
- Lecture Notes in Computer Science ISBN: 9783030929305, Lecture Notes in Computer Science, Lecture Notes in Computer Science-Graph Drawing and Network Visualization, 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media Deutschland GmbH, 2021.
-
Abstract
- 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. Surprisingly, little is known about the resolution of the drawings they produce. In this paper, focusing on maximal plane graphs, we prove tight 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 a result 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 an algorithm might produce drawings with exponentially-small resolution, even when morphing drawings with polynomial resolution.
- Subjects :
- MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-030-92930-5
978-3-030-92931-2 - ISSN :
- 03029743 and 16113349
- ISBNs :
- 9783030929305 and 9783030929312
- Database :
- OpenAIRE
- Journal :
- Lecture Notes in Computer Science ISBN: 9783030929305, Lecture Notes in Computer Science, Lecture Notes in Computer Science-Graph Drawing and Network Visualization, 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)
- Accession number :
- edsair.doi.dedup.....86195971f7cdf0684dc6efe6d8c5565a