<p>According to <a href="http://www.utdallas.edu/~ravip/papers/infocom2000.pdf" rel="nofollow">this paper</a>, the dominating set problem and the minimum d-hops dominating set problem are NP-Complete for unit disk graphs.</p>

CC BY-SA 3.0
2012-01-09T07:49:55.087Z
2012-01-09T07:49:55.087Z
Lamine
<p>Did you try doing a search for "planar unit disk graphs"? According to <a href="http://www.mpi-inf.mpg.de/~nikolam/downloads/scheduling-adhocnow11.pdf">this paper</a> the problem of finding the largest possible induced matching is NP-complete for planar unit disk graphs, according to <a href="http://books.google.com/books?hl=en&amp;lr=&amp;id=bn0Zub_NpM8C&amp;oi=fnd&amp;pg=PA61">this paper</a> so is the minimum connected dominating set, and according to <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4288232&amp;tag=1">this paper</a> so is the maximum number of disjoint dominating sets.</p>

CC BY-SA 3.0
2012-01-06T21:35:21.680Z
2012-01-06T21:35:21.680Z
David Eppstein
<p>I am curious to know whether there are problems which are np-hard even on planar unit disk graphs.</p>

<p>A unit disk graph is the intersection graph of a collection of unit disks in the plane, where we draw a vertex for each unit disk. </p>

<p>Maybe some problem on a accordingly restricted grid graph?</p>

<p>alex</p>

<np-hardness><cg.comp-geom>
NP-hard problem on planar unit disk graph
alex
# NP-hard problem on planar unit disk graph

(Asked by: username_0 on 2012-01-06)

I am curious to know whether there are problems which are np-hard even on planar unit disk graphs.

A unit disk graph is the intersection graph of a collection of unit disks in the plane, where we draw a vertex for each unit disk.

Maybe some problem on a accordingly restricted grid graph?

alex

**Tags:** np-hardness, cg.comp-geom

---

## 2 answers

### Answer by username_2 on 2012-01-06. Score: 9 | Accepted answer

Did you try doing a search for "planar unit disk graphs"? According to [this paper](http://www.mpi-inf.mpg.de/~nikolam/downloads/scheduling-adhocnow11.pdf) the problem of finding the largest possible induced matching is NP-complete for planar unit disk graphs, according to [this paper](http://books.google.com/books?hl=en&lr=&id=bn0Zub_NpM8C&oi=fnd&pg=PA61) so is the minimum connected dominating set, and according to [this paper](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4288232&tag=1) so is the maximum number of disjoint dominating sets.


---

### Answer by username_1 on 2012-01-09. Score: 0

According to [this paper](http://www.utdallas.edu/~ravip/papers/infocom2000.pdf), the dominating set problem and the minimum d-hops dominating set problem are NP-Complete for unit disk graphs.


---

