Is the maximum independent set in cubic planar graphs NP-complete? In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation from vertex cover and for vertex cover (I suppose in cubic planar graphs) they cite the paper of Garey, Johnson and Stockmeyer 1976.

When I looked at their DBLP entry, there is a single paper that matches the description of the mentioned paper:

Some Simplified NP-complete Graph Problems.

Having checked the paper, the reduction for vertex cover in graphs of maximum degree 3 is for general graphs, not planar graphs. For planar graphs, they only have a reduction that shows hardness on planar graphs of maximum degree 6, not 3 (already the gadget has vertices of degree 6).

I'm wondering if I'm missing something here since there are consequent papers building upon the aforementioned comment of the book.
A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper.


  Bojan Mohar:
  "Face Covers and the Genus Problem for Apex Graphs"
  Journal of Combinatorial Theory, Series B 82, 102-117 (2001)