# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 4 Two-Approximation Algorithm for Irregular Data Redistribution Scheduling  
In Theorem 1, we are going to formally prove that the corresponding graphs of GEN_BLOCK redistribution are biplanar graphs, which are a subclass of special bipartite graphs, called doubly convex-bipartite graphs [17]. Theorem 1: _The corresponding redistribution graph of GEN-BLOCK data redistribution is biplanar._  
Proof: Clearly the corresponding graph \(G_{GB(P,Q)}=(S,T,E)\) is bipartite. The rest is to prove that it is planar. We can try to find out a biplanar embedding for \(G_{GB(P,Q)}\) (see Figures 3 and 4 for example) by placing all processors on two lines and numbering them from left to right (i.e., \(\{P_{0},P_{1},\ldots,P_{|P|-1}\}\) and \(\{Q_{0},Q_{1},\ldots,Q_{|Q|-1}\}\)). In the GEN-BLOCK format \(GB\) (\(P,Q\)), any set of consecutive array elements are originally allocated to consecutive source processors with respect to \(\{P_{0},P_{1},\ldots,P_{|P|-1}\}\). Moreover, any set of consecutive array elements needs to be reallocated to consecutive destination processors with respect to \(\{Q_{j},Q_{i+1},\ldots,Q_{k}\}\). As a result, when there is a message sent and reallocated from \(P_{i}\) to \(Q_{o(i)}\), then for any \(j\) such that \(i\leq j\leq_{|P|-1}\) and any message sent from \(P_{j}\) to \(Q_{o(j)}\), we have \(o(j)\geq o(i)\). Suppose the corresponding redistribution graph is not biplanar, there is at least a pair of crossing edges such that (\(P_{j}\), \(Q_{o(j)}\)) and (\(P_{j+\Delta}\), \(Q_{o(j+\Delta)}\)) where \(\Delta>0\) and \(o(j+\Delta)<o(j)\). A contradiction occurs. Therefore, the corresponding redistribution bipartite graph is a biplanar graph. Theorem 2 presents extra properties of biplanar graphs, which will be used in this work. Theorem 2: _The following statements are equivalent [16; 32; 33]:_  
1. _A graph_ \(G\) _is a biplanar graph._
2. _After removing all leaves in_ \(G\)_, the remainder is an acyclic graph and contains no vertices with a degree more than two._
3. _A graph_ \(G\) _contains a set of caterpillars which are disjoint graphs._  
In Theorem 2, a caterpillar is a tree in which a single path (the spine) is incident to (or contains) every edge. When \(n\) denotes the number of vertices (i.e., \(|V|\)) in \(G\), the edge set of a bipartite graph contains at most \(O(n^{2})\) edges. Yet, if the input is planar, the number of edges in \(G\) would be reduced to \(3n-6\)[18]. Moreover, because biplanar graphs are essentially a subclass of planar graph, the number of edges in biplanar graphs is evidently less than \(3n-6\). Additionally, by combining Theorem 1 with Theorem 2, we conclude that the graph generated from the GEN-BLOCK method is a forest in the following corollary. The next corollary further indicates that the number of edges in \(G\) is less than or equal to \(n-1\). Corollary 1: _The graph \(G\) generated from GEN-BLOCK data redistribution is a forest._  
Theorem 3.2: _For a redistribution graph \(G=(X,Y,E)\) of GEN-BLOCK data redistribution, we have that \(|E|=|X|+|Y|-\omega(G)\), where \(\omega(G)\) represents the number of components of \(G\)._  
Proof: Suppose that \(G\) consists of \(\omega(G)\) trees \(T_{1}\), \(T_{2}\),..., \(T_{\omega(G)}\) (by Corollary 1). Since the size of edge set of a tree is one less than the size of its vertex set and \(G\) consists of \(\omega(G)\) trees, we have \(|E|=|X|+|Y|-\omega(G)\). Although we know that the redistribution graph constructed from GEN-BLOCK data redistribution is a biplanar graph by Theorem 1, so far there exists no polynomial time algorithm for MECP even when the input belongs to such graph. On the other hand, it becomes crucial to design an efficient approximation algorithm for MECP when the input is restricted to biplanar graphs. In order to devise such algorithm, we need to investigate the properties of the line graph \(L(G)\) of a biplanar graph \(G\), because it is easy to see that the max-coloring problem on \(L(G)\) is equivalent to MECP on \(G\).