(I have already posted this question on CS Theory Stack Exchange.)
If you know that 3-COL is NPC then you can prove that PLANAR 3-COL
is NPC by a NICE gadget that removes crossings
for some lecture notes on it. They are not mine. The original link
but I can't figure out the real author, though it is likely whoever taught Algorithms at CMU in Spring of 2004.)
Lets say we know that HAM CYCLE is NPC (we do!).
Is there a gadget to
remove crossings so you can show that PLANAR HAM CYCLE is NPC?
The problem of PLANAR HAM CYCLE is NPC so there sort-of has to be a gadget;
but is there a NICE one? (The proof that PLANAR HAM Cycle is NPC
is from SAT and I find it rather complicated
for the original paper.)
I have tried to extract an uncrossing gadget
from it but have not been able to it.
SO- I ask you, do you know of a NICE gadget for removing crossings in
a graph so that we can easily go from HAM CYCLE NPC to PLANAR HAM CYCLE NPC.
I'll be happy with HAM PATH or HAM CYCLE or DIRECTED HAM PATH or DIRECTED HAM CYCLE.