Flips on homologous orientations of surface graphs with prescribed forbidden facial circuits

Abstract

Let $G$ be a graph embedded on an orientable surface. Given a class $\mathcal{C}$ of facial circuits of $G$ as a forbidden class, we give a sufficient-necessary condition for that an $\alpha$-orientation (orientation with prescribed out-degrees) of $G$ can be transformed into another by a sequence of flips on non-forbidden circuits and further give an explicit formula for the minimum number of such flips. We also consider the connection among all $\alpha$-orientations by defining a directed graph $\mathbf{D}(\mathcal{C})$, namely the $\mathcal{C}$-forbidden flip graph. We show that if $\mathcal{C}\ne \varnothing$, then $\mathbf{D}(\mathcal{C})$ has exactly $|O(G,\mathcal{C})|$ components, each of which is the cover graph of a distributive lattice, where $|O(G,\mathcal{C})|$ is the number of the $\alpha$-orientations that has no counterclockwise facial circuit other than that in $\mathcal{C}$. If $\mathcal{C}=\varnothing$, then every component of $\mathbf{D}(\mathcal{C})$ is strongly connected. This generalizes the corresponding results of Felsner and Propp for the case that $\mathcal{C}$ consists of a single facial circuit.

16 pages, 4 figures