2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

Given a planar graph, one can always compute a combinatorial embedding for it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.