Research Talk: Speedy, Safely Small, Simple, Simple Cycle Separators

Abstract

We designed, implemented, and tested an algorithm that, given a triangulated 2-connected planar graph, returns a small, balanced simple cycle separator in linear time. Efficient construction of such separators that form simple cycles are essential in numerous planar graph algorithms, e.g., for computing shortest paths, minimum cuts, or maximum flows. To the best of our knowledge, this is the first implementation of such a cycle separator algorithm with a worst-case guarantee on the cycle length. We evaluate the performance of our algorithm and compare it to other planar separator algorithms to demonstrate that (i) our algorithm is competitive across all test cases in terms of running time, balance and cycle-length, (ii) it provides worst-case guarantees on the cycle length, significantly outperforming FCS on some instances, and (iii) it scales to large graphs.