Pfaffian orientations for a type of bipartite graph

An even cycle C of a graph G   is nice if the graph G−V(C)G−V(C) has a perfect matching. An orientation of G is a Pfaffian orientation if every nice cycle of G   has an odd number of edges directed in either direction of the cycle. A graph is Pfaffian if it has a Pfaffian orientation. If a graph is Pfaffian, then the number of perfect matchings of it can be computed in polynomial time. In this paper, we focus on a special type of 1-extendable bipartite graph with maximum degree Δ(G)=|V(G)|/2Δ(G)=|V(G)|/2. We characterize some properties of Pfaffian graphs in this type. According to the properties, we find an algorithm in time O(|E(G)|2)O(|E(G)|2) to determine whether a graph G in this type is Pfaffian or not. Furthermore, if G is Pfaffian, this algorithm also constructs a Pfaffian orientation of it.