Computing large matchings in planar graphs with fixed minimum degree

AbstractIn this paper, we present algorithms that compute large matchings in planar graphs with fixed minimum degree. The algorithms give a guarantee on the size of the computed matching and run in linear time. Thus they are faster than the best known algorithm for computing maximum matchings in general graphs and in planar graphs, which run in O(nm) and O(n1.188) time, respectively. For the class of planar graphs with minimum degree 3, the bounds we achieve are known to be the best possible. Further, we discuss how minimum degree 5 can be used to obtain stronger bounds on the matching size