On the Edge-length Ratio of Outerplanar Graphs - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2019

On the Edge-length Ratio of Outerplanar Graphs

(1) , (2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
Edge-length-ratio-TCS.pdf (953.1 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (60.54 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

hal-01886947 , version 1 (03-10-2018)

Identifiers

Cite

Sylvain Lazard, William Lenhart, Giuseppe Liotta. On the Edge-length Ratio of Outerplanar Graphs. Theoretical Computer Science, 2019, 770, pp.88--94. ⟨10.1016/j.tcs.2018.10.002⟩. ⟨hal-01886947⟩
202 View
165 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More