  \noindent By a seminal result of Valiant, computing the permanent of
$(0,1)$-matrices is, in general, $\#\mathsf{P}$-hard. In 1913 P\'olya asked for
which $(0,1)$-matrices $A$ it is possible to change some signs such that the
permanent of $A$ equals the determinant of the resulting matrix. In 1975,
Little showed these matrices to be exactly the biadjacency matrices of
bipartite graphs excluding $K_{3,3}$ as a \{matching minor}. This was turned
into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in
1999. However, the relation between the exclusion of some matching minor in a
bipartite graph and the tractability of the permanent extends beyond $K_{3,3}.$
Recently it was shown that the exclusion of any planar bipartite graph as a
matching minor yields a class of bipartite graphs on which the {permanent} of
the corresponding $(0,1)$-matrices can be computed efficiently. In this paper
we unify the two results above into a single, more general result in the style
of the celebrated structure theorem for single-crossing-minor-free graphs. We
identify a class of bipartite graphs strictly generalising planar bipartite
graphs and $K_{3,3}$ which includes infinitely many non-Pfaffian graphs. The
exclusion of any member of this class as a matching minor yields a structure
that allows for the efficient evaluation of the permanent. Moreover, we show
that the evaluation of the permanent remains $\#\mathsf{P}$-hard on bipartite
graphs which exclude $K_{5,5}$ as a matching minor. This establishes a first
computational lower bound for the problem of counting perfect matchings on
matching minor closed classes.
