Pfaffian orientation

In graph theory, a Pfaffian orientation of an undirected graph assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction.

This is the main idea behind the FKT algorithm for counting perfect matchings in planar graphs, which always have Pfaffian orientations.

The terms of this definition have the following meanings: Pfaffian orientations have been studied in connection with the FKT algorithm for counting the number of perfect matchings in a given graph.

Then, the Pfaffian of this matrix (the square root of its determinant) gives the number of perfect matchings.

This result stands in contrast to the much higher computational complexity of counting matchings in arbitrary graphs.

[3] An orientation in which each face of a planar graph has an odd number of clockwise-oriented edges is automatically Pfaffian.

The remaining edges, not in this tree, form a spanning tree of the dual graph, and their orientations can be chosen according to a bottom-up traversal of the dual spanning tree in order to ensure that each face of the original graph has an odd number of clockwise edges.

The same gluing structure can be used to obtain a Pfaffian orientation for these graphs.

[1] For bipartite graphs, it is possible to determine whether a Pfaffian orientation exists, and if so find one, in polynomial time.

Left: The 3 cycles of the graph, shown red, along with a matching of the remaining graph after removing the cycle. The cycles are "even" because they have an even number of edges, and are "central" because a perfect matching is able to be created with the remaining graph (cycle 3 leaves no vertices, automatically filling this criteria).

Right: A Pfaffian Orientation of the graph on the left, where the edges of the 3 cycles from the right have an odd number going in each direction around the cycle. The red and blue arrows are clockwise and counter-clockwise respectively for all cycles, and the black arrow is counter-clockwise relative to cycle 1 and clockwise relative to cycle 2.