# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Computing Geometric Minimum-Dilation Graphs Is NP-Hard

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Klein, R., & Kutz, M. (2007). Computing Geometric Minimum-Dilation Graphs Is NP-Hard.
In M. Kaufmann, & D. Wagner (*Graph Drawing*
(pp. 196-207). Berlin: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1EAA-3

##### 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.