Engineering planar separator algorithms

We consider classical linear-time planar separator
algorithms, determining for a given planar graph a
small subset of the nodes whose removal separates the
graph into two components of similar size. These algorithms
are based upon Planar Separator Theorems, which
guarantee separators of size asymptotically in the
square root of the number of nodes n and remaining
components of size less than 2n/3. In this work, we
present a comprehensive experimental study of the
algorithms applied to a large variety of graphs, where
the main goal is to find separators that do not only
satisfy upper bounds but also possess other desirable
qualities with respect to separator size and component
balance. We propose the usage of fundamental cycles,
whose size is at most twice the diameter of the graph, as planar
separators: For graphs of small diameter the
guaranteed bound is better than the bounds of the classical
algorithms, and it turns out that this simple strategy almost
always outperforms the other algorithms, even for graphs with
large diameter.