Adrian Dumitrescu, Ansgar Grüne, and Günter Rote:
On the geometric dilation of curves and point sets
Manuscript, July 2004, 14 pages, submitted for publication.
The detour between two points u
and v (on edges or vertices)
of an embedded
planar graph whose edges are curves is the ratio between the shortest
path in in the graph between u
and v and their Euclidean
maximum detour over all pairs of points is called the geometric
Ebbers-Baumann, Grüne and Klein have shown that every finite point
contained in a planar graph whose geometric dilation is at most 1.678,
some point sets require graphs with dilation >=pi/2=1.57... We prove
stronger lower bound of (1+10-11)pi/2 by relating graphs
with small dilation to
a problem of packing and covering the plane by circular disks.
Last update: July 8, 2004.