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

Heping Zhang*, Peter Che Bor Lam, Wai Chee SHIU

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)469-485
Number of pages17
JournalDiscrete Applied Mathematics
Volume130
Issue number3
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Cell rotation graphs of strongly connected orientations of plane graphs with an application'. Together they form a unique fingerprint.

Cite this