  A matching is a set of edges without common endpoint. It was recently shown
that every 1-planar graph (i.e., a graph that can be drawn in the plane with at
most one crossing per edge) that has minimum degree 3 has a matching of size at
least $\frac{n+12}{7}$, and this is tight for some graphs. The proof did not
come with an algorithm to find the matching more efficiently than a
general-purpose maximum-matching algorithm. In this paper, we give such an
algorithm. More generally, we show that any matching that has no augmenting
paths of length 9 or less has size at least $\frac{n+12}{7}$ in a 1-planar
graph with minimum degree 3.
