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.

Di Battista, G., Frati, F. (2021). From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-Line Drawings and Morphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.109-122). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-92931-2_8].

From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-Line Drawings and Morphs

Di Battista G.;Frati F.
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.
978-3-030-92930-5
Di Battista, G., Frati, F. (2021). From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-Line Drawings and Morphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.109-122). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-92931-2_8].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/400799
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact