On the Edge-length Ratio of Outerplanar Graphs - Archive ouverte HAL Access content directly
Conference Papers Year :

## On the Edge-length Ratio of Outerplanar Graphs

(1) , (2) , (3)
1
2
3
Sylvain Lazard
William Lenhart
• Function : Author
• PersonId : 1017155
Giuseppe Liotta
• Function : Author
• PersonId : 988937

#### 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$.

### Dates and versions

hal-01591699 , version 1 (21-09-2017)

### Identifiers

• HAL Id : hal-01591699 , version 1

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

111 View