A survey of Pfaffian orientations of graphs
Robin Thomas
Georgia Institute of Technology, Atlanta,USA
A subscription is required to access this book chapter.
Abstract
An orientation of a graph G is Pfaffian 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 significance of Pfaffian 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 Pfaffian 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 efficiently test if a general graph is Pfaffian, but there are some interesting connections with crossing numbers and signs of edgecolorings of regular graphs.