Efficient algorithms for Petersen's matching theorem

Petersen's theorem is a classic result in matching theory from 1891, statin g that every 3-regular bridgeless graph has a perfect matching. Our work ex plores efficient algorithms for finding perfect matchings in such graphs. P reviously, the only relevant matching algorithms were for general graphs, a nd the fastest algorithm ran in O(n(3/2)) time fur 3-regular graphs. We hav e developed an O(n log(4) n)-time algorithm for perfect matching in a 3-reg ular bridgeless graph. When the graph is also planar, ne have as the main r esult of our paper an optimal O(n)-time algorithm. We present three applica tions of this result: terrain guarding, adaptive mesh refinement, and quadr angulation. (C) 2001 Academic Press.