Is the feedback vertex set problem on planar bounded degree graphs hard?

Question

Is it known whether the feedback vertex set problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?

Answer 1

According to Garey and Johnson's book Vertex Cover is NP-complete on planar graphs of maximum degree four. Using a simple reduction from Vertex Cover to Feedback Vertex Set should give maximum degree eight and preserve planarity.

VC to FVS: Replace each edge by a triangle (or a double edge).

One note: Garey and Johnson also state that directed FVS is NP-complete on planar digraphs with no in- or out-degree exceeding two. They do not specifically mention undirected FVS under such restrictions.

Answer 2

The answer is: FVS is NP-complete on undirected planar graphs of maximum degree $4$; proved by Speckenmeyer, see here. By subdividing each edge by one new vertex, it easily follows that

FVS is NP-complete even on undirected bipartite planar graphs of maximum degree $4$.

The degree constraint is best possibe, as FVS is polynomial for graphs of maximum degree at most three; see here.

Edit: Ernst de Ridder's graphclasses.org now contains all available information about FVS; including circa 550 polynomially solvable and circa 250 NP-c cases.

Answer 3

According to Wikipedia Garey & Johnson also showed that " Vertex cover remains NP-complete ... even in planar graphs of degree at most 3."

Thus FVS is hard on planar graphs with maximum degree 6.

Answer 4

Apparently, in Speckenmeyer's PhD thesis, he demonstrates that the feedback vertex set problem is NP-hard for graphs of maximum degree 4. This claim appears here, for example.

For cubic graphs, the problem seems to be solvable in polynomial time. First, Speckenmeyer demonstrates that for cubic graphs, the minimum-size feedback vertex set is equal to $n/2-z(G)+1$, where $n$ is the number of vertices and $z$ is the size of the largest nonseparating independent set. Huang and Liu demonstrate that for cubic graphs, $z(G)$ is equal to the maximum genus of $G$, which can be calculated in polynomial time using the algorithm of Furst, Gross, and McGeoch.

Edit: didn't examine vb le's edit carefully enough...