The minimum vertex cover problem is NP-hard for the planar graph of degree at most 3. However, the minimum vertex cover can be easily found in some certain types of planar graph, given the planar representation. For example, the planar graph that every face boundary is a cycle of even length. Is there any proof that shows the NP-hardness of the minimum vertex cover of the (general) planar graph, given its planar representation as an auxiliary input?
Finding the minimum vertex cover of planar graph given the planar representation
complexity theory;graph theory;np complete;np hard