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(n5/4log n) time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to O(nlog² n). Weimann and Yuster further reduced the running time to O(nlog n). In this paper, we solve the problem in $O(n)$ time.