# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 4 Two-Approximation Algorithm for Irregular Data Redistribution Scheduling
With the help of Theorem 2 and Corollary 1, we have found that \(G\) contains a set of caterpillars, which are useful to show that \(L(G)\) is an interval graph. The next theorem becomes essential for us to design an approximation algorithm for the MECP latter. Theorem 3.3: _The line graph of the communication graph of GEN-BLOCK data redistribution is an interval graph._  
Proof: When a connected communication graph \(G=(S,T,E)\) of GEN-BLOCK data redistribution is given as an input, we only need to find out an interval model of \(L(G)\). In view of the fact that \(G\) is biplanar (by Theorem 1), we can construct a biplanar embedding of \(G\) on two lines. Without changing the sequences of the biplanar embedding, we need to show that these sequences are able to be rescaled to satisfy the next four properties:  
1. Every vertex \(v\) in \(S\cap T\) can be assigned and labeled with a distinct integer \(\chi(v)\) from left to right where \(1\leq\chi(v)\leq|S|+|T|\). Moreover, the x-coordinate of vertex \(v\) on two horizontal lines is exactly \(\chi(v)\). 2. Vertex set \(S\cap T\) can be grouped into two disjoint subsets: spine set \(B\) and leaf set \(L\). Here \(B\) contains all vertices in the spine, and \(L\) contains the rest of vertices (that is, all vertices with degree one in \(G\)); that is, \(L\) contains all leaf nodes in \(G\). Since every vertex \(v\) in \(L\) is a leaf, there is a unique edge (\(v\), \(b_{k}\)) connecting \(v\) to another vertex in \(B\) by Theorem 2. 3. Suppose \(B\)={\(v_{b0}\), \(v_{b1}\),..., \(v_{b|B|-1}\)} is sorted ascending by \(x\)-coordinate. Every vertex \(v\) in \(B\) is assigned with a unique integer \(\chi(v)\) in interval \([1,\,|S|+|T|]\). Due to biplanar graph properties, the space between the two parallel lines is partitioned into \(|B|+1\) closure subspaces. Similarly, interval \([1,|S|+|T|]\) can be partitioned into at most \(|B|+1\) subintervals \([1,\,\chi(v_{b0})]\), \([\chi(v_{b0}),\,\chi(v_{b1})]\),..., \([\chi(|B|-1),|S|+|T|]\) with respect to the \(x\) coordinates of vertices in \(B\). Since \(G\) is a connected graph, there is an edge connecting every pair of neighboring vertices in spine set \(B\). 4. Due to the properties of bipartite planar graphs, \(L\) is able to be divided into \(R\leq|B|\) disjoint leaf sets \(L_{1}\), \(L_{2}\),..., \(L_{|B|}\) such that each vertex in the same leaf set is adjacent to the same vertex in \(B\)We can rescale the biplanar drawing properly so that every vertex \(v\) in the same leaf set is allocated with a \(x\)-coordinate \(x(v)\) contained in a same subintervals selected from \([1,\chi(v_{b0})-1]\), \([x(v_{b0})+1\), \(\chi(v_{b1})-1]\),..., \([x(|_{|B|-1})+1,|S|+|T|]\). Moreover, when two leaf nodes are in different leaf sets, their \(x\)-coordinates contained in different subintervals selected from \([1,\chi(v_{b0})-1]\), \([x(v_{b0})+1\), \(\chi(v_{b1})-1]\),..., \([x(|_{|B|-1})+1,|S|+|T|]\) (e.g., blue dash rectangles in Figure 9). Also notice that for each edge \((u,v)\) in this sequence, their corresponding \(x\)-coordinates \(\chi(u)\) and \(\chi(v)\) are located in the same subintervals selected from \([1,\chi(v_{b0})]\), \([\chi(v_{b0}),\chi(v_{b1})]\),..., \([\chi(|_{|B|-1}),|S|+|T|]\). To show that \(L(G)\) is an interval graph, we need to find out its interval model. According to the above rescaled planar drawing, we first label each vertex of \(G\) with its \(x\)-coordinate, and then an interval \([x(v_{1})-0.1,\chi(v_{2})+0.1]\) is constructed for every \((v_{1},v_{2})\) in edge set (Figure 9). The rest shows that the intervals obtained represent \(L(G)\). Assume there are two vertices adjacent in \(L(G)\) and its corresponding edges in \(G\) are \(e_{1}=(u,\,v_{1})\) and \(e_{2}=(u,\,v_{2})\). Without loss of generality, let \(\chi(v_{1})<\chi(v_{2})\). When \(\chi(u)<\chi(v_{1})<\chi(v_{2})\), the interval \([\chi(u)-0.1,\chi(v_{1})+0.1]\) (representing \(e_{1}\)) intersects the interval \([\chi(u)-0.1,\chi(v_{2})+0.1]\) (representing \(e_{2}\)).