On the Edge-Length Ratio of Outerplanar Graphs

Lazard, Sylvain and Lenhart, Wiliam J. and Liotta, Giuseppe (2017) On the Edge-Length Ratio of Outerplanar Graphs. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 17-23(Official URL: https://doi.org/10.1007/978-3-319-73915-1_2).

Full text not available from this repository.


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 every bipartite outerplanar graph has a planar straight-line drawing with edge-length ratio 1, and that, for any k≥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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1588

Actions (login required)

View Item View Item