-1
$\begingroup$

I want to prove that this problem to find whether the crossing number of any given graph is K or not, is NP-Hard. I don't know how to do this. Can someone help me with this ?

$\endgroup$
2
  • $\begingroup$ Are you familiar with reductions? Yes: please specify where exactly you are stuck or state your doubt. No: please go through a standard textbook/material on proving NP-completeness first. $\endgroup$
    – codeR
    Commented Apr 24 at 8:19
  • $\begingroup$ The crossing number problem is well studied; a simple web search would have revealed that. Here's one (probably original) proof: doi.org/10.1137/0604033 $\endgroup$
    – codeR
    Commented Apr 24 at 8:22

1 Answer 1

0
$\begingroup$

The crossing number problem has been well studied. From wiki:

In general, determining the crossing number of a graph is hard; Garey and Johnson showed in 1983 that it is an NP-hard problem [ref].

In fact the problem remains NP-hard even when restricted to cubic graphs [ref2] and to near-planar graphs (graphs that become planar after removal of a single edge) [ref3].

Also see this stackexchange discussion.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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