**Reference**:- Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, and Anna Lubiw, “Efficient Algorithms for Petersen's Matching Theorem”, in
*Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99)*, Baltimore, Maryland, January 17–19, 1999, pages 130–139. **Abstract**:-
Petersen's theorem is a classic result in matching theory from 1891, stating
that every 3-regular bridgeless graph has a perfect matching. Our work
explores efficient algorithms for finding perfect matchings in such graphs.
Previously, the only relevant matching algorithms were for general graphs, and
the fastest algorithm ran in
*O*(*n*^{3/2}) time. We have developed an*O*(*n*log^{4}*n*)-time algorithm for matching in a 3-regular bridgeless graph. When the graph is also planar, we have as the main result of our paper an optimal*O*(*n*)-time algorithm. We present three applications of this result, terrain guarding, adaptive mesh refinement, and quadrangulation. **Length**:- The paper is 10 pages and the talk is 20 minutes.
**Availability**:- The paper is available in PostScript (632k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- MatchingJAlgorithms (Efficient Algorithms for Petersen's Matching Theorem)

See also other papers by Erik Demaine.

Last updated December 29, 2018 by Erik Demaine.