Access Restriction

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

   Open content in new tab
Source: ACM Digital Library