Computing the Girth of a Planar Graph in Linear Time
Computing the Girth of a Planar Graph in Linear Time
The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an $n$-node unweighted undirected planar graph. The first nontrivial algorithm for the problem, given by Djidjev, runs in $O(n^{5/4}\log n)$ time. Chalermsook, Fakcharoenphol, and Nanongkai …