Planar subgraphs without low-degree nodes

Conference paper

Authors:	Evangelos Kranakis, Oscar Morales Ponce, and Jukka Suomela
Title:	Planar subgraphs without low-degree nodes
Conference:	12th Algorithms and Data Structures Symposium (WADS), New York, NY, USA, August 2011
Proceedings:	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
	Lecture Notes in Computer Science, volume 6844 Springer, Berlin, Germany, 2011 ISBN: 978-3-642-22299-3 pages 583–594 doi:10.1007/978-3-642-22300-6_49
Links:	publisher’s version · authors’ version © Springer 2011 — The original publication is available at www.springerlink.com.
	extended version
	conference · proceedings · series · DBLP
Abstract:	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.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.