A survey of Pfafﬁan orientations of graphs
Robin ThomasGeorgia Institute of Technology, Atlanta,USA
A subscription is required to access this book chapter.
An orientation of a graph G is Pfafﬁan if every even cycle C such that G\V(C) has a perfect matching has an odd number of edges directed in either direction of the cycle. The signiﬁcance of Pfafﬁan orientations is that if a graph has one, then the number of perfect matchings (a.k.a. the dimer problem) can be computed in polynomial time.
The question of which bipartite graphs have Pfafﬁan orientations is equivalent to many other problems of interest, such as a permanent problem of Pólya, the even directed cycle problem, or the sign-nonsingular matrix problem for square matrices. These problems are now reasonably well-understood. On the other hand, it is not known how to efﬁciently test if a general graph is Pfafﬁan, but there are some interesting connections with crossing numbers and signs of edgecolorings of regular graphs.