Bounds on the edge-length ratio of 2-outerplanar graphs
Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani, Stephen Wismath · Computational Geometry · 2025
The edge-length ratio of a planar straight-line drawing Γ of a graph G is the largest ratio between the lengths of every pair of edges of Γ. If the ratio is measured by considering only pairs of edges that are incident to a common vertex, we talk about local edge-length ratio. The (local) edge-length ratio of a planar graph is the infimum over all (local) edge-length ratios of its planar straight-line drawings. It is known that the edge-length ratio of outerplanar graphs is upper bounded by a constant, while there exist graph families with non-constant outerplanarity that have non-constant lower bounds on their edge-length ratios. In this paper we prove an Ω ( n ) lower bound on the local edge-length ratio (and hence on the edge-length ratio) of the n -vertex 2-outerplanar graphs. We also prove a constant upper bound on the edge-length ratio of Halin graphs, pseudo-Halin graphs, and their generalizations.