Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time

2011/04/26 by Jakub Łącki, Łącki, Jakub, Piotr Sankowski +1 · 1 citation
Computer Science · #05C10 #05C85 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2

paper · pdf · doi:10.48550/arxiv.1104.4890

openalex publication_date 2011/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorithm by Italiano et al. in STOC'11 by a factor of log n. This speedup is obtained through the use of dense distance graphs combined with a divide-and-conquer approach.

Cited by

• A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies

Related

• Minimum Cut of Directed Planar Graphs in O(nloglogn) Time
• Min st-Cut of a Planar Graph in O(n loglog n) Time
• Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time
• Faster Shortest Paths in Dense Distance Graphs, with Applications
• Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time