I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.
I thought about some modification on Tarjan's algorithm for undirected graphs, but I didn't find good results. Actually I thought that if I could find a 2-connected components in $O(|V|)$, then I can find the girth, by some sort of induction which can be achieved from the first part. I may be on the wrong track, though. Any algorithm asymptotically better than $\Theta(|V|^2)$ (i.e. $o(|V|^2)$) is welcome.