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 , label its neighbors with 1, and the neighbors' neighbors as 2, and so on. The last labeled vertex has a label of which is its distance from . Assign this vertex as and repeat the process. When the distance does not increase any more, is taken as the root and the diameter of the graph. In practice this procedure converges quickly in a few iterations.

The graph bisection algorithm has a complexity of . 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.