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: http://dx.doi.org/10.1007/978-3-540-70904-6_20).

Full text not available from this repository.

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.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-540-70904-6_20
Classifications:	Z Theory > Z.001 General
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/774

Actions (login required)

View Item