Computing the Girth of a Planar Graph in Linear Time

Details Computing the Girth of a Planar Graph in Linear Time Computing the Girth of a Planar Graph in Linear Time

2011-04-26

arxiv.org/abs/1104.4892v1

Computer Science

Data Structures and Algorithms

19 pages, 7 figures, full version. The conference version of the paper will appear in COCOON 2011

Scientific paper

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 non-trivial algorithm for the problem, given by Djidjev, runs in O(n^{5/4} log n) time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to O(n log^2 n). Weimann and Yuster further reduced the running time to O(n log n). In this paper, we solve the problem in O(n) time.

Affiliated with

Also associated with

No associations

Rating

Computing the Girth of a Planar Graph in Linear Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the Girth of a Planar Graph in Linear Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Girth of a Planar Graph in Linear Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-296088