On the Edge-length Ratio of Outerplanar Graphs

Abstract : We show that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any ε > 0 there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than 2 −ε. We also show that this ratio cannot be bounded if the embeddings of the outerplanar graphs are given.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2018, 〈10.1016/j.tcs.2018.10.002〉
Liste complète des métadonnées


https://hal.inria.fr/hal-01886947
Contributeur : Sylvain Lazard <>
Soumis le : mercredi 3 octobre 2018 - 13:54:14
Dernière modification le : lundi 29 octobre 2018 - 10:13:01

Fichiers

Edge-length-ratio-TCS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sylvain Lazard, William Lenhart, Giuseppe Liotta. On the Edge-length Ratio of Outerplanar Graphs. Theoretical Computer Science, Elsevier, 2018, 〈10.1016/j.tcs.2018.10.002〉. 〈hal-01886947〉

Partager

Métriques

Consultations de la notice

70

Téléchargements de fichiers

22