patternMinor
An efficient algorithm to decide if a triangulation is 3-colourable
Viewed 0 times
efficienttriangulationalgorithmcolourabledecide
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#86792, answer score: 7
Revisions (0)
No revisions yet.