Graph bisection

The recursive graph bisection (RGB) algorithm [87] attempts to remedy this. Assume that the graph is connected. The RGB algorithm first finds the two vertices that are the furthest apart (their distance is called the diameter of the graph). Then, starting from one of them (the root), the half of the vertices that are closer to the root form one subdomain, the rest form the other. This process is then recursively executed on each of the subdomains.

To find the two vertices that are the furthest apart, a heuristic procedure can be employed. Starting from any vertex as the potential root $R$, label its neighbors with 1, and the neighbors' neighbors as 2, and so on. The last labeled vertex has a label of $m$ which is its distance from $R$. Assign this vertex as $R$ and repeat the process. When the distance $m$ does not increase any more, $R$ is taken as the root and $m$ the diameter of the graph. In practice this procedure converges quickly in a few iterations.

The graph bisection algorithm has a complexity of $O(n)$. Figure 4 shows the result of applying the RGB algorithm to the dual graph of the mesh of 788 elements, resulting in 142 shared edges, the same as RCB by coincidence.

Figure 4: Partitioning a mesh into 16 subdomains using RGB