Face-width of Pfaffian braces and polyhex graphs on surfaces (Q490246)

Summary: A graph \(G\) with a perfect matching is Pfaffian if it admits an orientation \(D\) such that every central cycle \(C\) (i.e. \(C\) is of even size and \(G-V(C)\) has a perfect matching) has an odd number of edges oriented in either direction of the cycle. It is known that the number of perfect matchings of a Pfaffian graph can be computed in polynomial time. In this paper, we show that every embedding of a Pfaffian brace (i.e. 2-extendable bipartite graph) on a surface with a positive genus has face-width at most 3. Further, we study Pfaffian cubic braces and obtain a characterization of Pfaffian polyhex graphs: a polyhex graph is Pfaffian if and only if it is either non-bipartite or isomorphic to the cube, or the Heawood graph, or the Cartesian product \(C_k\times K_2\) for even integers \(k\geqslant 6\).