@techreport{TR-IC-04-03,
  number = {IC-04-03},
  author = {Alberto Alexandre Assis Miranda and
            Cláudio Leonardo Lucchesi},
  title = {Pfaffian Graphs},
  month = {April},
  year = {2004}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 25 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       It is well known that, in general, the problem of determining
       the number of perfect matchings of a graph is NP-hard.  Some
       graphs, called Pfaffian, have a special type of orientation
       that is also called Pfaffian.  Given a Pfaffian orientation of
       a graph G, the number of perfect matchings of G may be
       evaluated in polynomial time.  Two (not necessarily Pfaffian)
       orientations are similar if they differ by a cut.  Similarity
       is an equivalence relation on the collection of orientations of
       a graph.  If an orientation is Pfaffian then every similar
       orientation is also Pfaffian.
       \par
       For any Pfaffian matching covered graph G, the number of
       similarity classes of Pfaffian orientations of G is equal to
       $2^b$, where b denotes the number of bricks of the tight cut
       decomposition of G.
       \par
       The following four problems are polynomially equivalent, that
       is, given a polynomial algorithm for any of the four problems
       it is then possible to find polynomial algorithms for the other
       three problems: (i) determine whether or not a graph is
       Pfaffian, (ii) determine whether or not a given orientation of
       a graph is Pfaffian, (iii) determine whether or not a graph is
       Pfaffian, in case it is Pfaffian, find a Pfaffian orientation
       for the graph, and (iv) determine the number of similarity
       classes of Pfaffian orientations of a graph.
  }
}