Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I was reading this and I'm trying to understand how one would formally describe reducing planar 3 colouring to 3 colouring. The link pretty much describes the process but understanding the mathematical formalism is a bit over my head.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

Reducing planar 3-coloring to 3-coloring is easy since the former is a special case of the latter, so you can use the identity mapping.

What you probably meant was reducing 3-coloring to planar 3-coloring. 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|improve this answer
    
Wow. This helped a lot. Thank you! –  user119264 May 15 at 4:42
add comment

Your Answer

 
discard

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.