## 4 Quality-Aware Routing and Channel Assignment in Multi-Channel Multi-Gateway WOBAN
### Our Proposed Algorithm for Coloring the Planar Subgraph  
Let us denote the planar subgraph by \(\tilde{G}\) which consists of vertices in the FCL and their corresponding edges. According to the _Four Color Theorem_, \(\tilde{G}\) can be colored with 4 colors. Thus, we first color \(\tilde{G}\) with four colors by using a _backtracking_ algorithm (line 4-line 23 in Algorithm 2). Figure 5 shows the example of graph coloring using backtracking. Let us denote the available four colors as RED, BLUE, GREEN and BLACK which are indexed as 1, 2, 3, 4, respectively, in Algorithm 2. The vertices in FCL are denoted as \(\{v_{1},v_{2},\ldots,v_{n}\}\). Initially, all of the vertices can use any of the four colors. Without loss of generality, we start with vertex A and color it RED. Because of this assignment, all the adjacent vertices of A cannot use RED. Thus, B and F can only use BLUE, GREEN and BLACK. Assume that we proceed in this way and colors B, C, D, E and F are colored with BLUE, RED, BLUE, GREEN and BLACK, respectively. Now, there is no color left for G. Thus, we need to backtrack and then finally color D, E and F with GREEN, black and GREEN, respectively, and then color G with BLACK. This process guarantees a valid 4-coloring of \(\tilde{G}\). This vertex coloring of the conflict graph is then translated to color the links in the connectivity graph. Assume that the number of channels used by a node and its number of interfaces are \(C_{u}\) and \(I\), respectively. If \(C_{u}>I\) at any node, then the interface constraint is violated. In that case, we select \(C_{u}-I\) links (which are vertices in the conflict graph) randomly around that node and add them to GCL (line 24). The GCL is next passed to the _genetic algorithm_ (line 25). The worst case complexity of backtracking grows exponentially with the number of vertices in the conflict graph. With four colors, the backtracking tree contains \(1+4+4^{2}+\ldots+4^{n-1}=\frac{4^{n}-1}{3}\) vertices. However, the number of solutions for a vertex coloring problem is significantly large, thus we do not need to explore the entire backtracking tree to get one valid solution. As studied in [45], a tree with \(n\) vertices can be colored in \(t(t-1)^{n-1}\) ways, whereas a cycle of \(n\) ver  
Figure 5: Illustration of (**a**) a seven node planar graph and (**b**) its corresponding backtracking tree for graph coloring. \((t-1)^{n}+(-1)^{n}(t-1)\) ways, where \(t\) is the number of colors. As a conflict graph is composed of tree and cycles, searching a small fraction of the entire tree is sufficient to obtain a valid solution. ```
1:INPUT : Simple undirected graph \(G\) and the set of channels;
2:OUTPUT : Color assignment of \(G\);
3:Vertex Deletion (\(G\)); \(\triangleright\) To obtain the planar subgraph
4:All_nodes_colored = false;
5:\(v_{i}=v_{1}\);
6:Color(\(v_{1}\)) = 0;
7:while All_nodes_colored == false do
8:whileColor(\(v_{i}\)) \(<\) 4 do
9:if All_nodes_colored == true then
10: break;
11:endif
12:Color(\(v_{i}\)) = Color(\(v_{i}\)) + 1; \(\triangleright\) Color all vertices in \(G\) with at most 4 colors
13:if ValidColor(Color(\(v_{i}\)), \(v_{i}\)) == true then
14:if\(v_{i}==v_{n}\)then
15: All_nodes_colored = true;
16:else
17:\(v_{i}=v_{i+1}\);
18:Color(\(v_{i}\)) = 0;
19:endif
20:endif
21:endwhile
22:\(v_{i}=v_{i-1}\); \(\triangleright\) Backtrack if the vertex cannot be colored with 4 colors
23:endwhile
24:GCL = GCL \(\cup\) (vertices violating interface-constraint) ; \(\triangleright\) Vertices violating the interface-constraint are added to the GCL
25:Perform Genetic-Algorithm(GCL);
26:return \(G\) with vertex coloring;
```  
**Algorithm 2** Algorithm for finding the color/channel assignment. The primary purpose of applying a backtracking strategy is to ensure that the genetic algorithm (which is computationally expensive) is performed on a lesser number of vertices.