Cell rotation graphs of strongly connected orientations of plane graphs with an application

✍ Scribed by Heping Zhang; Peter Che Bor Lam; Wai Chee Shiu

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 345 KB
• Volume: 130
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00184-7

✦ Synopsis

The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is deÿned. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T -, thus (T; T -) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T -, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height.