2
$\begingroup$

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

$\endgroup$
9
$\begingroup$

Did you try doing a search for "planar unit disk graphs"? According to this paper the problem of finding the largest possible induced matching is NP-complete for planar unit disk graphs, according to this paper so is the minimum connected dominating set, and according to this paper so is the maximum number of disjoint dominating sets.

$\endgroup$
0
$\begingroup$

According to this paper, the dominating set problem and the minimum d-hops dominating set problem are NP-Complete for unit disk graphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.