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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download


https://hal.inria.fr/hal-01886947
Contributor : Sylvain Lazard <>
Submitted on : Wednesday, October 3, 2018 - 1:54:14 PM
Last modification on : Friday, April 12, 2019 - 10:18:10 AM
Long-term archiving on : Friday, January 4, 2019 - 3:31:09 PM

Files

Edge-length-ratio-TCS.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

110

Files downloads

114