Plane Elementary Bipartite Graphs with Forcing or Anti-forcing Edges

• Published in: Graphs and combinatorics 2019-07, Vol.35 (4), p.959-971
• Main Authors: Che, Zhongyuan, Chen, Zhibo
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Combinatorics; Construction planning; Engineering Design; Graph theory; Graphs; Handles; Mathematics; Mathematics and Statistics; Original Paper
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-019-02051-0

Let G be a plane elementary bipartite graph with more than one finite face. We first characterize forcing edges and anti-forcing edges of G in terms of handles and forcing faces. We then introduce the concept of a nice pair of faces of G , which allows us to provide efficient algorithms to construct plane minimal elementary bipartite graphs from G . We show that if G ′ is a minimal elementary spanning subgraph of G , then all vertices of a forcing face of G are contained in a forcing face of G ′ , and any forcing face of G is a forcing face of G ′ if it is still a face of G ′ . Furthermore, any forcing edge (resp., anti-forcing edge) of G is still a forcing edge (resp., an anti-forcing edge) of G ′ if it is still an edge of G ′ . We conclude the paper with the co-existence property of forcing edges and anti-forcing edges for those plane minimal elementary bipartite graphs that remain 2-connected when any handle of length one (if exists) is deleted.