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.

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
ID Code:774

Repository Staff Only: item control page

References

B. Aronov, M. de Berg, O. Cheong, J. Gudmundsson, H. Haverkort, and A. Vigneron. Sparse Geometric Graphs with Small Dilation. 16th International Symposium ISAAC 2005, Sanya. In X. Deng and D. Du (Eds.) Algorithms and Computation, Proceedings, pp. 50-59, LNCS 3827, Springer-Verlag, 2005.

U. Brandes and D. Handke. NP-Completeness Results for Minimum Planar Spanners. Discrete Mathematics and Theoretical Computer Science 3, pp. 1-10, 1998.

L. Cai. NP-Completeness of Minimum Spanner Problems. Discrete Applied Math. 48, pp. 187-194, 1994.

L. Cai and D. Corneil. Tree Spanners. SIAM J. of Discrete Math. 8, pp.359-387, 1995.

P. Callahan and S. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42(1), pp.67-90, 1995.

O. Cheong, H. Haverkort, and M. Lee. Computing a Minimum-Dilation Spanning Tree is NP-hard, Manuscript, 2006.

A. Ebbers-Baumann, A. Grüne, and R. Klein. On the Geometric Dilation of Finite Point Sets. 14th International Symposium ISAAC 2003, Kyoto. In T. Ibaraki, N.

Katoh, and H. Ono (Eds.) Algorithms and Computation, Proceedings, pp. 250-259, LNCS 2906, Springer-Verlag, 2003. Algorithmica 44, pp. 137-149, 2006.

D. Eppstein. Spanning Trees and Spanners. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, editors, pp. 425-461. Elsevier, 1999.

D. Eppstein and K. A. Wortman. Minimum Dilation Stars. Proc. 21st ACM Symp. Comp. Geom. (SoCG), Pisa, 2005, pp. 321-326.

S. Fekete and J. Kremer. Tree Spanners in Planar Graphs. Discrete Applied Mathematics 108(1-2), pp. 85-103, 2001.

J. Gudmundsson and M. Smid. On Spanners of Geometric Graphs. 10th Scandinavian Workshop on Algorithmic Theory (SWAT'06). In L. Arge and R. Freivalds (Eds.), pp. 388-399, LNCS 4059, Springer-Verlag, 2006.

W. Mulzer and G. Rote. Minimum weight triangulation is NP-hard. Proc. 22nd Annual ACM Symp. Comp. Geom. (SoCG), Sedona, 2006 pp. 1-10.

G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University Press, to appear.