Planar subgraphs without low-degree nodes
| Contribuinte(s) |
University of Helsinki, Helsinki Institute for Information Technology HIIT |
|---|---|
| Data(s) |
2011
|
| Resumo |
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. |
| Formato |
12 |
| Identificador | |
| Idioma(s) |
eng |
| Relação |
Algorithms and Data Structures 12th International Symposium, WADS 2011. New York, NY, USA, August 15-17, 2011. Proceedings Lecture Notes in Computer Science |
| Direitos |
The original publication is available at www.springerlink.com. |
| Fonte |
Kranakis , E , Morales Ponce , O & Suomela , J 2011 , ' Planar subgraphs without low-degree nodes ' in Algorithms and Data Structures : 12th International Symposium, WADS 2011. New York, NY, USA, August 15-17, 2011. Proceedings , pp. 583–594 Lecture Notes in Computer Science , vol. 6844 . , 10.1007/978-3-642-22300-6_49 |
| Palavras-Chave | #113 Computer and information sciences |
| Tipo |
A4 Article in conference publication (refereed) info:eu-repo/semantics/conferencePaper info:eu-repo/semantics/acceptedVersion |
