A Simple Algorithm for Computing a Cycle Separator

2017/09/23 by Sariel Har-Peled, Har-Peled, Sariel, Amir Nayyeri +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.CG #cs.DM

paper · pdf · doi:10.48550/arxiv.1709.08122

openalex publication_date 2017/09/23 · arxiv created 2018/01/17 · arxiv updated 2018/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a linear time algorithm for computing a cycle separator in a planar graph that is (arguably) simpler than previously known algorithms. Our algorithm builds on, and is somewhat similar to, previous algorithms for computing separators. The main new ingredient is a specific layered decomposition of the planar graph constructed differently from previous BFS-based layerings.

Related

• Separator Theorem for Minor-Free Graphs in Linear Time
• Deterministic Distributed DFS and Other Problems via Cycle Separators in Planar Graphs
• Separators for Planar Graphs that are Almost Trees
• Structured Recursive Separator Decompositions for Planar Graphs in Linear Time
• A Simple Proof of the Existence of a Planar Separator