平面及球面嵌入图α-定向的flip-距离

Flip-distance between α-orientations of graphs embedded on the plane and sphere

为研究平面嵌入图的给定出度序列的定向问题,Felsner引入了α-定向及flip变换,并进一步证明了一个平面嵌入图的所有α-定向在flip变换下构成一个分配格.本文中给出平面嵌入图的一个α-定向可由另一个α-定向通过一系列flip变换而得到的一个充分必要条件.与之平行,证明了球面嵌入图的任意两个α-定向均可通过一系列flip变换而相互得到.最后,给出了所需最少flip变换的数目.

Felsner introduced a cycle reversal,namely the"flip"reversal,forα-orientations(i.e.,each vertex admits a prescribed out-degree)of a graph G embedded on the plane and further proved that the set of all theα-orientations of G carries a distributive lattice by flip reversals.In this paper,we give an explicit formula for the minimum number of flips needed to transform anα-orientation into another for graphs embedded on the plane and sphere,respectively.