23
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 7
    $\begingroup$ 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$. $\endgroup$ – Marek Chrobak Jan 3 '12 at 20:13
  • 4
    $\begingroup$ What is Ham Cycle? Please do not assume everyone understands your abbreviations. $\endgroup$ – Tsuyoshi Ito Jan 4 '12 at 2:55
  • 2
    $\begingroup$ @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$. $\endgroup$ – Bruno Jan 4 '12 at 18:14
  • 12
    $\begingroup$ @Tsuyoshi: It means Hamiltonian cycle. I think it is reasonable to assume that everyone can figure it out. $\endgroup$ – domotorp Jan 5 '12 at 4:32
  • 3
    $\begingroup$ @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... $\endgroup$ – Sariel Har-Peled Jan 8 '12 at 22:49
13
$\begingroup$

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

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

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think you should be able to post figures now. $\endgroup$ – Jukka Suomela Jan 11 '12 at 12:14

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.