I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle) It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle. 

Is there a nice gadget that will, given a graph G, replace all of the crossings
with some planar gadget so that you have a planar graph G' such that


  G has a Ham cycle iff G' has a Ham cycle.


(I'll be happy with variants- like Ham path or directed Ham Cycle or
Directed Ham Path.)
No.  At least, no "nice" gadget for one crossover.

Let $(a, b)$ and $(x,y)$ be a cross we want to replace.

There are many cases for our graph, $G$, but we have to satisfy at least the following four.  Case 1: there is at least one hamiltonian cycle, but none use either of the edges.  Case 2: there is at least one cycle, and all cycles use exactly one of the two edges.  Case 3: there is at least one cycle, and all cycles use both edges.  Case 4: there is no hamiltonian cycle.

If our gadget has two (or more) vertices for each of $a, b, x, y$ adjacent to all the same neighbors (so that $a_0$ and $a_1$ retain $a$'s neighbors) then $G'$ will not necessarily still be planar.  In order to satisfy the first of our cases above, we then cannot have any new vertices in the gadget.  

In order to satisfy case 3 above, we must have at least two edges in the gadget.  Neither planar and covering pair, $(a, x), (y, b)$ nor $(a, y), (x, b)$ satisfies case 2, so we need a third edge.  Without loss of generality, let those three be $(a, y), (y, b), (x,b)$.

However, that replacement breaks the fourth case, because $G'$ could contain a hamiltonian cycle when $G$ does not.  Take, for example, $G = (V, E)$ where $V = \{a, b, x, y, p, q, r, s, t\},$ and
$E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$.  $G$ is not planar and does not have a hamiltonian cycle.

Then $G' = (V, E')$ where $E' = \{(a, y), (y, b), (x, b)\} \cup$
$\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$.  $G'$ is planar, and has a hamiltonian cycle ($a, q, x, t, p, s, b, y, r, a$).

Note that if $(b, y)$ was the edge not added instead of $(a, x)$, then $G'$ would not have a hamiltonian cycle.  It seems that you'd have to have knowledge of the possible cycle to choose the edge correctly, though.

A similar problem exists for having the gadget include one of the diagonal edges, such as: $(a, b), (a, y), (x, b)$.

Since adding three edges breaks case 4, adding more won't help.

Thus, no "nice" gadget exists.  It could be that a gadget exists that pays more attention to the neighbors of each of $a, b, x$ and $y$, but that doesn't seem very "nice".

(Note: please let me know if I made any errors above!)

(Note 2: I had some nice figures, but can't post them.  Posted.)