## Abstract

The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. 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.

Original language | English |
---|---|

Pages (from-to) | 469-485 |

Number of pages | 17 |

Journal | Discrete Applied Mathematics |

Volume | 130 |

Issue number | 3 |

DOIs | |

Publication status | Published - 23 Aug 2003 |

## Scopus Subject Areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## User-Defined Keywords

- Ear decomposition
- Eulerian orientation
- In-tree
- Perfect matching
- Plane graph
- Rotation graph
- Strongly connected orientation