Computing the Girth of a Planar Graph in O(n \logn) Time

2010/01/01 by Oren Weimann, Raphael Yuster · 10 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Planar graph #Girth (graph theory) #Butterfly graph #Discrete mathematics #Graph #Bounded function #Outerplanar graph #Undirected graph #Vertex (graph theory) #Line graph #Voltage graph

paper · doi:10.1137/090767868

published in SIAM Journal on Discrete Mathematics 24(2), 609-616 (Society for Industrial and Applied Mathematics)

openalex publication_date 2010/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/11

Abstract

We give an O(nlog n) algorithm for computing the girth (shortest cycle) of an undirected n-vertex planar graph. Our solution extends to any graph of bounded genus. This improves upon the best previously known algorithms for this problem.

Citations

• Finding a Minimum Circuit in a Graph
• Graph minors. III. Planar tree-width
• A Separator Theorem for Planar Graphs
• Diameter and Treewidth in Minor-Closed Graph Families
• A separator theorem for graphs of bounded genus
• A partial k-arboretum of graphs with bounded treewidth
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The clique problem for planar graphs
• Color-coding
• Faster Shortest-Path Algorithms for Planar Graphs
• Graph Theory and Probability

Cited by

• Planar separator theorem [wikipedia]