hide
Free keywords:
-
Abstract:
Consider a geometric graph $G$, drawn with straight lines in the plane. For
every pair $a$,$b$ of vertices of $G$, we compare the shortest-path distance
between $a$ and $b$ in $G$ (with Euclidean edge lengths) to their actual
Euclidean distance in the plane. The worst-case ratio of these two values, for
all pairs of vertices, is called the vertex-to-vertex dilation of $G$.
We prove that computing a minimum-dilation graph that connects a given
$n$-point set in the plane, using not more than a given number $m$ of edges, is
an $NP$-hard problem, no matter if edge crossings are allowed or forbidden. In
addition, we show that the minimum dilation tree over a given point set may in
fact contain edge crossings.
