3
$\begingroup$

I don't know how to start with the following exercise:

Design an efficient algorithm to decide whether a given triangulation with $n $ points is $3$-colourable. The triangulation is given by a sorted edge list, where every edge is given by the indices of its two end points. Further, for every edge there are given the indices of the points with which the edge forms a triangle in the triangulation (two indices for interior edges and one index for edges on the boundary of the convex hull). Give proof for the correctnesss of your algortihm.

Below is an example.

I've heard about the BFS and DFS algorithms in lecture, but I don't see how I could apply this here. I'd be thankful for any help.enter image description here

$\endgroup$
  • $\begingroup$ @YuvalFilmus Not necessarily, every triangle must be colored with at least 3 different colours and it doesn't seem so far-fetched that 3 colours suffice unless we can find some obvious counter-example (such as in the picture). Plus, the exercise implies that it lies in P, so I'd bet there's some trick here. $\endgroup$ – Discrete lizard Jan 15 '18 at 17:39
  • $\begingroup$ Deciding whether a planar graph is 3-colorable is NP-hard. This is quite close to the problem at hand. $\endgroup$ – Yuval Filmus Jan 15 '18 at 17:40
  • $\begingroup$ Is this a homework problem? Academia.SE has had a bunch of questions about that recently. $\endgroup$ – dalearn Jan 16 '18 at 0:38
  • $\begingroup$ Yes it is, but I couldn't find anything similiar to this exercise. $\endgroup$ – 3nondatur Jan 16 '18 at 6:47
7
$\begingroup$

Let us assume that the dual graph is connected, which means that if you connect any two faces which share an edge, then you get a connected graph on the triangular faces.

Pick an arbitrary triangular face $F$ and color its 3 vertices with 3 distinct colors. If $F'$ shares an edge with $F$, then there is only one choice for the color of the remaining vertex of $F'$. Continuing in this way, attempt to color all vertices. If you're successful, the graph can be 3-colored. Otherwise, the graph cannot be 3-colored.

This algorithm is very similar to the one for deciding whether a given graph can be 2-colored.

$\endgroup$
  • $\begingroup$ Thanks for your answer, but there is one point I don't get: How do you obtain the dual graph beforehand from the given list of edges? $\endgroup$ – 3nondatur Jan 16 '18 at 7:36
  • $\begingroup$ You don't. You start with an arbitrary triangle (which you can find by picking a vertex and going over all pairs of neighbors), and then you repeatedly locate a vertex which forms a triangle with two of the vertices of the current triangle. This algorithm runs in time $O(n^2)$. Using more sophisticated approaches you can probably go down to $\tilde{O}(n)$. $\endgroup$ – Yuval Filmus Jan 16 '18 at 7:58

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.