Computing Geometric MinimumDilation Graphs is NPHardKlein, Rolf and Kutz, Martin (2007) Computing Geometric MinimumDilation Graphs is NPHard. In: Graph Drawing 14th International Symposium, GD 2006, September 1820, 2006 , pp. 196207(Official URL: http://dx.doi.org/10.1007/9783540709046_20). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540709046_20
AbstractConsider a geometric graph G, drawn with straight lines in the plane. For every pair a,b of vertices of G, we compare the shortestpath distance between a and b in G (with Euclidean edge lengths) to their actual Euclidean distance in the plane. The worstcase ratio of these two values, for all pairs of vertices, is called the vertextovertex dilation of G. We prove that computing a minimumdilation graph that connects a given npoint set in the plane, using not more than a given number m of edges, is an NPhard 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.
Actions (login required)
