Computing Geometric Minimum-Dilation Graphs is NP-Hard

Klein, Rolf and Kutz, Martin (2007) Computing Geometric Minimum-Dilation Graphs is NP-Hard. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 196-207(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_20
Classifications: Z Theory > Z.001 General

Actions (login required)

View Item View Item