Building graph separators with the recursive rotation algorithm for nested dissections method

The recursive rotation algorithm is built and investigated. This algorithm is one of versions of the nested dissections algorithm. The Liu algorithm builds a matrix graph separator by the rotation of an elimination tree. The rotation of the elimination tree decreases its height. In this case, the nodes of a matrix graph are previously re-ordered by one of the well-known Cuthill–McKee algorithms, reverse to the Cuthill–McKee algorithm, or King algorithm. Then this procedure is recursively repeated. Comparison between the recursive rotation algorithm and the multilevel and spectral methods of graph separation for the 2D finite elements grids is made.