A faster algorithm for computing the girth of planar and bounded genus graphs

摘要

The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n~(5/4) log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n~2) algorithm for this problem. We also extend our results for the class of graphs embedded into an orientable surface of small genus. Our approach uses several techniques such as graph partitioning, hammock decomposition, graph covering, and dynamic shortest-path computation. We discuss extensions and generalizations of our result.