On the geometric dilation of curves and point sets
Adrian Dumitrescu, Ansgar Grüne, Günter Rote · 2004
Let G be an embedded planar graph whose edges are curves. The detour between two points u and v (on edges or vertices) of G is the ratio between the shortest path in G between u and v and their Euclidean distance. The maximum detour over all pairs of points is called the geometric dilation δ(G). Ebbers-Baumann, Grüne and Klein have recently shown that every finite point set is contained in a planar graph whose geometric dilation is at most 1.678, and some point sets require graphs with dilation δ ≥ π/2 ≈ 1.57. We prove a stronger lower bound δ ≥ (1 + 10 −11)π/2 by relating graphs with small dilation to a problem of packing and covering the plane by circular disks. 1