# On the Edge-length Ratio of Outerplanar Graphs

1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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$.
Type de document :
Communication dans un congrès
International Symposium on Graph Drawing and Network Visualization, 2017, Boston, United States. Graph Drawing and Network Visualization, 〈http://www.graphdrawing.org/〉

Littérature citée [13 références]

https://hal.inria.fr/hal-01591699
Contributeur : Sylvain Lazard <>
Soumis le : jeudi 21 septembre 2017 - 18:29:47
Dernière modification le : jeudi 11 janvier 2018 - 06:28:11

### Fichier

Edge-length-ratio-v4-camera-re...
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01591699, version 1

### Citation

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. Graph Drawing and Network Visualization, 〈http://www.graphdrawing.org/〉. 〈hal-01591699〉

### Métriques

Consultations de la notice

## 92

Téléchargements de fichiers