Evangelos Kranakis · Oscar Morales Ponce · Jukka Suomela

Planar subgraphs without low-degree nodes

WADS 2011 · 12th Algorithms and Data Structures Symposium, New York, NY, USA, August 2011 · doi:10.1007/978-3-642-22300-6_49

authors’ version publisher’s version extended version

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.

Publication

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

ISBN 978-3-642-22299-3

© Springer 2011 — The original publication is available at www.springerlink.com.

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.