4
$\begingroup$

It is well known that counting perfect matchings is tractable in planar graphs (due to Kastelyn).

I am interested in classes of (for lack of a better word) "near" planar graphs (1-planar, bounded genus etc.) where counting perfect matchings is also tractable.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This is probably not exactly what you're looking for, but for certain graphs embedded on a cylinder there are formulas as nice as the famous formulas for grid graphs: see, e.g., arxiv.org/abs/2102.07229 $\endgroup$
    – Sam Hopkins
    Commented Mar 21 at 0:34
  • 1
    $\begingroup$ Ciucu's paper, Enumeration of Perfect Matchings in Graphs with Reflective Symmetry, has a factorization theorem that applies to symmetric bipartite graphs that are not necessarily planar. In the paper, he shows how to apply the factorization theorem to enumerate perfect matchings of a variety of graphs. I think his examples are all planar, but they don't have to be. In particular if you have a non-planar graph with bilateral symmetry that reduces to a planar graph after applying the factorization theorem, then you can count the perfect matchings. $\endgroup$
    – Timothy Chow
    Commented Mar 22 at 12:02

1 Answer 1

Reset to default
5
$\begingroup$

Graphs of bounded genus (both orientable or non-orientable):

G. Tesler, Matchings in Graphs on Non-orientable Surfaces, Journal of Combinatorial Theory, Series B, Volume 78, Issue 2 (2000), 198-231. https://doi.org/10.1006/jctb.1999.1941

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .