Short and Simple Cycle Separators in Planar Graphs

Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, and Christian Sommer
ACM Journal of Experimental Algorithmics, Special Issue for the 14th Meeting on Algorithm Engineering and Experiments (ALENEX), Volume 21, Issue 2 (pp. 2:1-24), 2016

We provide an implementation of an algorithm that, given a planar graph with \(m\) edges, returns a simple cycle that is a \(2/3\)-balanced separator consisting of at most \(\sqrt{8m}\) edges. An efficient construction of a short and balanced separator that forms a simple cycle is 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 the planar separator algorithms recently studied by Holzer et al. [ESA 2005, ACM Journal of Experimental Algorithms 2009]. Out of these algorithms, only the Fundamental Cycle Separator (FCS) produces a simple cycle separator. However, FCS does not provide a worst-case size guarantee. We 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.

@article{FMPS16,
 author    = {Eli Fox-Epstein 
              and Shay Mozes
              and Phitchaya Mangpo Phothilimthana
              and Christian Sommer},
 title     = {Short and Simple Cycle Separators in Planar Graphs},
 year      = {2016},
 journal   = {{ACM} Journal of Experimental Algorithmics},
 volume    = {21},
 issue     = {2},
 pages     = {2:1--24}
 url       = {http://dx.doi.org/10.1145/2957318},
 doi       = {10.1145/2957318},
 note      = {Announced at ALENEX 2013},
}

Official version
Local version (516.1 KB)

See also Structured Recursive Separator Decompositions for Planar Graphs in Linear Time and On Balanced Separators in Road Networks

Home → Publications → Short and Simple Cycle Separators in Planar Graphs