On the edge-length ratio of outerplanar graphs (Q1740698)

The paper approaches the problem of computing a planar straight-line drawing of a planar graph with prescribed edge lengths constraints. Depending on the planar graph class and the specific edge constraints, multiple NP-hardness results are known: 3-connected planar graphs with prescribed edge lengths, 2-connected planar graphs with uniform lengths, degree-4 trees with vertices at integer points and edges of equal length etc. The authors hence focus on the natural variant of the problem asking to compute planar straight-line drawings where the variance of the lengths of the edges is minimized. Let us define the planar edge-length ratio of a planar graph \(G\) as the smallest ratio between the longest and the shortest edge lengths over all planar straight-line drawings of \(G\). The principal result of the paper is the proof that that 2 is a tight bound for the planar edge-length ratio of outerplanar graphs. The authors 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 and that this result is tight in the sense that for any \(\varepsilon > 0\) there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than \(2-\varepsilon\). Finally they also prove that this ratio cannot be bounded if the topological embeddings of the outerplanar graphs are given.