Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was reading these lecture notes and I'm trying to understand how one would formally describe reducing 3-colouring to planar 3-colouring. The link pretty much describes the process but understanding the mathematical formalism is a bit over my head. In short, it seems that every edge crossing is replaced with some new graph. How does this work?

share|cite|improve this question
up vote 4 down vote accepted

The idea is simple. Given an arbitrary graph embedded in the plane, what might make it non-planar is that edges could cross. By slightly perturbing the planar embedding (where we put the vertices), we can ensure that no more than two edges meet at a point.

The idea is to replace each crossing with a certain planar gadget $W$, which functions as a cloverleaf. The four vertices on the outside of the gadget consist of a horizontal pair $x_1,x_2$ and a vertical pair $v_1,v_2$. The gadget has the property that in any valid 3-coloring $c$, $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$, and vice versa, for each choice of $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$ there is such a coloring.

How do we use this gadget? Suppose that the graph has exactly one crossing, the edge $(a,b)$ crossing the edge $(r,s)$, we put a copy of the gadget with $x_1 = a$ and $v_1 = r$. The gadget ensures that $c(x_2) = c(a)$ and $c(v_2) = c(r)$, so if we connect $x_2$ to $b$ and $v_2$ to $s$, the new graph is 3-colorable iff the original one is (I encourage you to draw this, consulting the lecture notes). Plus, the crossing has been replaced by the gadget, which is itself planar.

The general case is more complicated but of the same spirit, and you can read about it in the proof. The idea is to replace each crossing with a copy of the gadget; two adjacent crossings on the same edge share vertices, as illustrated on page 124 of the lecture notes.

The difficult part in coming up with this reduction is constructing the gadget. The idea itself is pretty natural, and it is somewhat surprising that it can be made to work.

share|cite|improve this answer
Wow. This helped a lot. Thank you! – user119264 May 15 '14 at 4:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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