Flip-Flop Reversal In α-orientation Of Plane Graph

Research in graph orientation has a long history that revealed many interesting structural insights and applications.A classical example would be the one given by Robbins in 1939,which states that a graph is 2-edge connected if and only if it has a strongly connected orientation.This result was then generalized by Nash-Williams to 2k-edge connected graphs.In the study of graph orientation,a particularly well-concerned problem is to orient a graph with prescribed degree-constraints on its ver-tices.Felsner introduced an orientation,namely the a-orientation,in which each ver-tex is assigned a prescribed outdegree.The α-orientation was widely applied in deal-ing with various types of combinatorial structures in plane graphs,such as the Eulerian orientations,spanning trees,bipartite perfect matchings(or more generally bipartite f-factors),Schnyder woods,bipolar orientations and 2-orientations of quadrangula-tions,primal-dual orientations,transversal structures and c-orientations of the dual of plane graph.Cycle reversal has been shown as a powerful method since it preserves the out-degree of each vertex and the connectivity of the orientations.Felsner introduced two types of cycle reversals for α-orientations,namely the flip and flop,defined on the so called essential cycles and further proved that the set of all α-orientations of a plane graph carries a distributive lattice with respect to the flip reversals.In this thesis,we focus on studying the relations among all the α-orientations of plane graphs and sphere graphs by flip-flop reversals.The thesis is organized as six chapters.In the first chapter,we give a brief introduction on α-orientation,some necessary terminology and notations involved in our study.In Chapter 2,we give a characterization for two strongly connected orientations to be comparable in the lattice carried by a-orientations,and further give an explicit formula of flip distance from one to the other.Consequently,for a 2-connected plane graph and a given strongly con-nected outdegree function α,we establish a recursive relation of the distance between the maximal and minimal α-orientations.In Chapter 3,we give an explicit formula of the distance between strongly connected α-orientations of plane graphs with respect to flip-flop reversals.Chapter 4 is an application of the previous two chapters to the square ice model and the spanning trees on plane graph.In chapter 5,we consider the flip distance for a graph embedded on a sphere and give a specific formula of the flip distance between two strongly connected α-orientations of the sphere graph.In the last chapter,we introduce the α-transformation graph of the square ice model,where two orientations are adjacent provided they can be transformed from each other by a flip or a flop.We show that the connectivity of the α-transformation graph equals its minimum degree of the vertices,with only two exceptions.