Computing the Girth of a Planar Graph in $O(n \logn)$ Time
Oren Weimann, Raphael Yuster · SIAM Journal on Discrete Mathematics · 2010
We give an $O(n\log 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.