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, Karlsruhe, Germany , pp. 196-207 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_20).
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.
Repository Staff Only: item control page