Similarity of Orientations and Characteristic Orientations

In this section we introduce an equivalence relation on the set of all orientations of a graph. The study of equivalence classes with respect to this relation turns out to play an important role in developing algorithms for finding Pfaffian orientations of matching graphs which are known to be Pfaffian and in showing that the Pfaffian Recognition Problem (19.1) and the Pfaffian Orientation Problem (19.2) are both in co-NP and are polynomial-time equivalent.