[Math] Algorithm to find all (up to isomorphism) perfect matchings of quartic plane graphs

Question

I need to find all (up to isomorphism) perfect matchings of some quartic plane graphs. I haven't found any specific algorithm to give me all the perfect matchings. Does anybody know about such an algorithm or any results that could be useful when implementing such an algorithm? At the moment I can only think of a branch-and-bound approach.

I don't really expect there to be an algorithm for this specific case, but I thought I'd mention all properties of the graphs. Maybe there are results for plane graphs, planar graphs or quartic graphs.

Answer 1

OK, here is a way which uses my other answer:

• Number the edges of your graph in some order.
• Check if your graph $G$ has a perfect matching.
• If no, return $\emptyset.$
• Add the lowest number edge to the matching, delete the edges incident to the endpoints. Call the resulting graph $G^\prime.$
• Recursively, return all the matchings in $G^\prime$ (union the first edge).
• Now, use the second lowest-numbered edge as the first edge.
• Halt when the total number of edges left is smaller than half the number of vertices.

Note that this algorithm (using the algorithms referenced in my other answer) will run in something like $n^{3/2}$ times the number of actual perfect matchings, which is pretty good. Those who care about such things will recognize the algorithm as a simple backtracking algorithm (as used in e.g. the $N$-queens problem).