On the Edge-length Ratio of Outerplanar Graphs
Résumé
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.
Domaines
Géométrie algorithmique [cs.CG]
Fichier principal
Edge-length-ratio-TCS.pdf (953.1 Ko)
Télécharger le fichier
vignette.png (60.54 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...