Face-width of Pfaffian Braces and Polyhex Graphs on Surfaces

Abstract

A graph \(G\) is Pfaffian if it has an orientation such that each central cycle \(C\) (i.e. \(C\) is even and \(G-V(C)\) has a perfect matching) has an odd number of edges directed in either direction of the cycle. The number of perfect matchings of Pfaffian graphs can be computed in polynomial time. In this paper, by applying the characterization of Pfaffian braces due to Robertson, Seymour and Thomas [Ann. Math. 150 (1999) 929-975], and independently McCuaig [Electorn. J. Combin. 11 (2004) #R79], we show that every embedding of a Pfaffian brace on a surface with positive genus has face-width at most 3. For a Pfaffian cubic brace, we obtain further structure properties which are useful in characterizing Pfaffian polyhex graphs. Combining with polyhex graphs with face-width 2, we show that a bipartite polyhex graph is Pfaffian if and only if it is isomorphic to the cube, the Heawood graph or \(C_k\times K_2\) for even integers \(k\ge 6\), and all non-bipartite polyhex graphs are Pfaffian.