Planar Dominating Set Problem

computation graph-theory

Definition

Planar Dominating Set Problem

The planar dominating set problem is the restriction of the dominating set problem to planar graphs.

Instance: a planar graph $G=(V,E)$ and an integer $k$.

Question: Does $G$ have a dominating set $D\subseteq V$ with $|D|\le k$?