Unlike conventional matching algorithms based on the combinatorial approach, we present an algebraically randomized algorithm for finding maximum (perfect) matchings in planar graphs. Our algorithms are, in part, based on an O(n^ω) Gaussian elimination approach induced in [18], and furthermore, combined with the separator theorem of planar graphs and the nest dissection algorithm, where the framework of separator tree has been utilized.

The running time of this algorithm is only O(n^ω/2), where ! is the matrix multipli- cation constant. Since ! now is somewhere between 2 and 2.373, this algorithm not only provides the first result of this kind of general planar graph to break through the O(n^1.5) barrier for the matching problem, but also might lead to a new practical approach to solving the maximum matching problem in planar graphs.