Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time

2011/01/01 by Jakub Łącki, Piotr Sankowski · 9 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Graph #Mathematics #Parallel computing #Planar #Planar graph #Running time #Speedup #Time complexity

paper · doi:10.1007/978-3-642-23719-5_14

published in Lecture Notes in Computer Science, 155-166 (Springer Berlin Heidelberg)

crossref issued 2011/01/01 · crossref published 2011/01/01 · crossref published-print 2011/01/01 · openalex publication_date 2011/01/01 · crossref created 2011/08/30 · crossref deposited 2019/04/01 · openalex created_date 2025/10/10 · crossref indexed 2026/06/04 · openalex updated_date 2026/08/04

Citations

• Finding a Minimum Circuit in a Graph
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Faster Shortest-Path Algorithms for Planar Graphs
• Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

Cited by

• Planar separator theorem [wikipedia]