WADS 2011 · 12th Algorithms and Data Structures Symposium, New York, NY, USA, August 2011 · doi:10.1007/978-3-642-22300-6_49
We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.
Frank Dehne, John Iacono, and Jörg-Rüdiger Sack (Eds.): Algorithms and Data Structures, 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011, Proceedings, volume 6844 of Lecture Notes in Computer Science, pages 583–594, Springer, Berlin, 2011