Distance Between α-Orientations of Plane Graphs by Facial Cycle Reversals

Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reversal on an orientation of a plane graph is an operation that reverses all the directions of the edges of a directed facial cycle. An orientation of a graph is called an α-orientation if each vertex admits a prescribed out-degree. In this paper, we give an explicit formula for the minimum number of the facial cycle reversals needed to transform one α-orientation into another for plane graphs.