### Short and Simple Cycle Separators in Planar GraphsShort and Simple Cycle Separators in Planar Graphs

Access Restriction
Subscribed

 Author Fox-Epstein, Eli ♦ Mozes, Shay ♦ Phothilimthana, Phitchaya Mangpo ♦ Sommer, Christian Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Design ♦ Algorithms ♦ Cycle separator ♦ Performance ♦ Planar graphs Abstract We provide an implementation of an algorithm that, given a triangulated planar graph with $\textit{m}$ edges, returns a simple cycle that is a 3/4-balanced separator consisting of at most $&sqrt;8\textit{m}$ edges. An efficient construction of a short and balanced separator that forms a simple cycle is essential in numerous planar graph algorithms, for example, 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. [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 (1) our algorithm is competitive across all test cases in terms of running time, balance, and cycle length; (2) it provides worst-case guarantees on the cycle length, significantly outperforming FCS on some instances; and (3) it scales to large graphs. Description Author Affiliation: MIT (Mozes, Shay); Tufts University (Fox-Epstein, Eli); UC Berkeley (Phothilimthana, Phitchaya Mangpo) ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-09-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 21 Page Count 24 Starting Page 1 Ending Page 24

#### Open content in new tab

Source: ACM Digital Library