<p>No.  At least, no "nice" gadget for one crossover.</p>

<p>Let $(a, b)$ and $(x,y)$ be a cross we want to replace.<img src="https://i.sstatic.net/oolsP.png" alt="enter image description here"></p>

<p>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.</p>

<p>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.  </p>

<p>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)$.</p>

<p>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.<img src="https://i.sstatic.net/kczJ5.png" alt="enter image description here"></p>

<p>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$).</p>

<p>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.</p>

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

<p>Since adding three edges breaks case 4, adding more won't help.</p>

<p>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".</p>

<p>(Note: please let me know if I made any errors above!)</p>

<p>(<strike>Note 2: I had some nice figures, but can't post them.</strike>  Posted.)</p>

CC BY-SA 3.0
2012-01-11T12:14:50.323Z
I think you should be able to post figures now.
Jukka Suomela
CC BY-SA 3.0
2012-01-10T19:49:11.210Z
2012-01-11T15:57:43.763Z
2012-01-11T15:57:43.763Z
Kyle
<p>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. </p>

<p>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</p>

<blockquote>
  <p>G has a Ham cycle iff G' has a Ham cycle.</p>
</blockquote>

<p>(I'll be happy with variants- like Ham path or directed Ham Cycle or
Directed Ham Path.)</p>

CC BY-SA 3.0
2012-01-03T20:13:45.600Z
A somewhat trivial observation. Suppose you embed $G$ and edges $(x,y)$ and $(u,v)$ cross, with $x,v,y,u$ appearing clockwise around the crossing point. Replace it by a gadget $P_{xvyu}$ that has four entrance points $x',v',y',u'$ corresponding to $x,v,y,u$. If a hamiltonian cycle in $G$ uses both edges $(x,y)$ and $(u,v)$ then in $G'$ the corresponding cycle would have to self-cross. This of course assumes the most naive interpretation of what a ``gadget" is and also that the hamiltonian cycle in $G'$ needs to follow the same edges as the corresponding cycle in $G$.
Marek Chrobak
CC BY-SA 3.0
2012-01-04T02:55:29.000Z
What is Ham Cycle?  Please do not assume everyone understands your abbreviations.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-04T18:14:23.083Z
@MarekChrobak: I agree with your remark. You give two ways to escape your argument. I think the most natural one is the second one: There is a Hamiltonian Cycle $x\to y\to\dotsb\to u\to v\to\dotsb\to x$ in $G$ iff there exists a Hamiltonian Cycle $x\to x'\to\dotsb \to u'\to u\to\dotsb\to y\to y'\to\dotsb\to v'\to v\to\dotsb\to x$.
Bruno
CC BY-SA 3.0
2012-01-05T04:32:35.410Z
@Tsuyoshi: It means Hamiltonian cycle. I think it is reasonable to assume that everyone can figure it out.
domotorp
CC BY-SA 3.0
2012-01-05T15:13:48.957Z
@MarekChrobak: (1) is P_{xvyu} a path that goes x-v-y-u ?
(2) By Planar Ham Cycle I mean that the original graph is planar.
Your solution might be helpful for the problem where you want
the Ham Cycle itself to be planar (not cross itself), which is not
my problem but is still interesting.
Bill GASARCH
CC BY-SA 3.0
2012-01-05T16:24:22.717Z
@Bill: you say: "... Your solution might be helpful for the problem where you want the Ham Cycle itself to be planar ...": but if $G'$ is planar (as you asked), then every Ham Cycle on it must be planar, too; so the Marek's note seems correct to me ?!?
Marzio De Biasi
CC BY-SA 3.0
2012-01-05T16:35:19.937Z
@Bruno: perhaps the (only) way you can achieve what you suggest, is to exand every edge of the original non-planar graph $G$ to a series of parallel edges that "carry" the information about the order of traversal of the edges $x \to x'$, $u \to u'$, $y \to y'$, $v'\to v$ of the planar gadget in $G'$ ... but I have no idea on how to do it :-)
Marzio De Biasi
CC BY-SA 3.0
2012-01-05T22:13:59.480Z
@Bill, I merged your new ID with the previous one so you should be able to comment. (ps: if you want you can register your user account to keep using the same user even when you remove the cookies from your browser.)
Kaveh
CC BY-SA 3.0
2012-01-08T22:49:08.557Z
@Bill: I am wondering why you think such a gadget should exist. The number of crossings when embedding an arbitrary graph into the plane can be very large ($\Theta(n^4)$ for the complete graph - see the crossing lemma). So, if you start with a graph with $n$ edges and many edges (say near quadratic) then the embedded graph with the crossings added as vertices has completely different structure...
Sariel Har-Peled
CC BY-SA 3.0
2012-01-11T19:37:51.353Z
maybe we can show that for any embedding of an explicit hamiltonian graph, any gadget used to construct a planar graph would violate Grinberg's theorem.
didest
<cc.complexity-theory><np-hardness><planar-graphs><hamiltonian-paths>
I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)
Bill GASARCH
# I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)

(Asked by: username_0 on 2012-01-03)

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.)

**Tags:** cc.complexity-theory, np-hardness, planar-graphs, hamiltonian-paths
> **Comments:**
> **username_1**: A somewhat trivial observation. Suppose you embed $G$ and edges $(x,y)$ and $(u,v)$ cross, with $x,v,y,u$ appearing clockwise around the crossing point. Replace it by a gadget $P_{xvyu}$ that has four entrance points $x',v',y',u'$ corresponding to $x,v,y,u$. If a hamiltonian cycle in $G$ uses both edges $(x,y)$ and $(u,v)$ then in $G'$ the corresponding cycle would have to self-cross. This of course assumes the most naive interpretation of what a ``gadget" is and also that the hamiltonian cycle in $G'$ needs to follow the same edges as the corresponding cycle in $G$.  
> **username_2**: What is Ham Cycle?  Please do not assume everyone understands your abbreviations.  
> **username_3**: @MarekChrobak: I agree with your remark. You give two ways to escape your argument. I think the most natural one is the second one: There is a Hamiltonian Cycle $x\to y\to\dotsb\to u\to v\to\dotsb\to x$ in $G$ iff there exists a Hamiltonian Cycle $x\to x'\to\dotsb \to u'\to u\to\dotsb\to y\to y'\to\dotsb\to v'\to v\to\dotsb\to x$.  
> **username_4**: @Tsuyoshi: It means Hamiltonian cycle. I think it is reasonable to assume that everyone can figure it out.  
> **username_0**: @MarekChrobak: (1) is P_{xvyu} a path that goes x-v-y-u ? (2) By Planar Ham Cycle I mean that the original graph is planar. Your solution might be helpful for the problem where you want the Ham Cycle itself to be planar (not cross itself), which is not my problem but is still interesting.  
> **username_5**: @Bill: you say: "... Your solution might be helpful for the problem where you want the Ham Cycle itself to be planar ...": but if $G'$ is planar (as you asked), then every Ham Cycle on it must be planar, too; so the Marek's note seems correct to me ?!?  
> **username_5**: @Bruno: perhaps the (only) way you can achieve what you suggest, is to exand every edge of the original non-planar graph $G$ to a series of parallel edges that "carry" the information about the order of traversal of the edges $x \to x'$, $u \to u'$, $y \to y'$, $v'\to v$ of the planar gadget in $G'$ ... but I have no idea on how to do it :-)  
> **username_6**: @Bill, I merged your new ID with the previous one so you should be able to comment. (ps: if you want you can register your user account to keep using the same user even when you remove the cookies from your browser.)  
> **username_7**: @Bill: I am wondering why you think such a gadget should exist. The number of crossings when embedding an arbitrary graph into the plane can be very large ($\Theta(n^4)$ for the complete graph - see the crossing lemma). So, if you start with a graph with $n$ edges and many edges (say near quadratic) then the embedded graph with the crossings added as vertices has completely different structure...  
> **username_8**: maybe we can show that for any embedding of an explicit hamiltonian graph, any gadget used to construct a planar graph would violate Grinberg's theorem.  

---

## 1 answers

### Answer by username_9 on 2012-01-10. Score: 13

No. At least, no "nice" gadget for one crossover.

Let $(a, b)$ and $(x,y)$ be a cross we want to replace.![enter image description here](https://i.sstatic.net/oolsP.png)

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.![enter image description here](https://i.sstatic.net/kczJ5.png)

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.)

> **Comments:**
> **username_10**: I think you should be able to post figures now.  

---

