Planar Independent Set Problem

computation graph-theory

Definition

Planar Independent Set Problem

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

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

Question: Does $G$ have an independent set $S\subseteq V$ with $|S|\ge k$?