Planar Vertex Cover Problem

computation graph-theory

Definition

Planar Vertex Cover Problem

The planar vertex cover problem is the restriction of the vertex cover problem to planar graphs.

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

Question: Does $G$ have a vertex cover $C\subseteq V$ with $|C|\le k$?