[comp.theory] minimum vertex-cover for 3-connected planar graphs

dey@cs.purdue.EDU (Tamal Krishna Dey) (11/14/89)

Is the minimum vertex-cover problem for 3-connected
planar graphs  NP-complete? It is known that the
above problem is NP-complete for the planar graph
with no vertex degree exceeding 4. Any help regarding
this will be appreciated.