Plane elementary bipartite graphs (Q1582086)

A connected graph is elementary if the union of all perfect matchings induces a connected subgraph. It is well known that a connected bipartite graph is elementary if and only if it is \(1\)-extendable, i.e., each edge is contained in a perfect matching. In this paper the authors mainly study properties of plane elementary bipartite graphs. Firstly, they show that a plane bipartite graph \(G\) is elementary if and only if the boundary of each face is an alternating cycle with respect to some perfect matching of \(G\). Secondly, the concept of the so-called \(Z\)-transformation graph \(Z(G)\) of a hexagonal system \(G\) (whose vertices represent the perfect matchings of \(G\)) is extended to an arbitrary plane bipartite graph \(G\), and some results analogous to those for hexagonal systems are presented. Thirdly, they obtain the reducible face decomposition for plane elementary bipartite graphs, where a peripheral face \(f\) is called reducible if the removal of the internal vertices and edges of the path that is the intersection of \(f\) and the exterior face results in a plane elementary bipartite graph. Using the well-known bipartite ear decomposition, it follows that a plane bipartite graph different from \(K_2\) is elementary if and only if it has a reducible face decomposition. Furthermore, sharp upper and lower bounds for the number of reducible faces are derived.