Skip to Main content Skip to Navigation
Conference papers

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 $\epsilon > 0$ there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than $2 - \epsilon$. We also show that every bipartite outerplanar graph has a planar straight-line drawing with edge-length ratio $1$, and that, for any $k \geq 1$, there exists an outerplanar graph with a given combinatorial embedding such that any planar straight-line drawing has edge-length ratio greater than~$k$.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Thursday, September 21, 2017 - 6:29:47 PM
Last modification on : Wednesday, November 3, 2021 - 7:09:01 AM


Files produced by the author(s)


  • HAL Id : hal-01591699, version 1



Sylvain Lazard, William Lenhart, Giuseppe Liotta. On the Edge-length Ratio of Outerplanar Graphs. International Symposium on Graph Drawing and Network Visualization, 2017, Boston, United States. ⟨hal-01591699⟩



Record views


Files downloads