Efficient Algorithms For Petersen's Theorem
Therese C. Biedl, McGill University

A well-known theorem of Petersen states that every 3-regular bridgeless graph contains a perfect matching. In this talk, we present efficient algorithms for finding such perfect matchings. Our results are $\Oh(n \log^4 n)$ time for general graphs and $\Oh(n)$ time for planar graphs (that is, duals of triangulations). This is significantly faster than the competition of $\Oh(n^{3/2})$. In addition, we believe that our algorithms are simpler and more practical than this competition.

(joint work with P. Bose, E. Demaine and A. Lubiw)