Computing Geometric Minimum-Dilation Graphs Is NP-Hard

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