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

Graph orientation with certain degree-constraints on vertices is a natural focus in graph theory and has close connection with many combinatorial structures in graphs, such as the spanning trees [2], primal-dual orientations [1], bipolar orientations [4], transversal structures [5], Schnyder woods [6], bipartite perfect matchings (or more generally, bipartite $f$-factors) [8, 10, 12] and $c$-orientations of the dual of a plane graph [9, 12]. In general, all these constraints could be encoded in terms of $\alpha$-orientations [2], that is, the orientations with prescribed out-degrees.

To deal with the relation among orientations, circuit (or cycle) reversal has been shown as a useful method since it preserves the out-degree of each vertex and the connectivity of the orientations. Various types of cycle reversals were introduced subject to certain requirements. Circuit reversal for the orientations of plane graphs or, more generally, surface graphs (graphs embedded on an orientable surface) received particular attention [2, 6, 9, 10, 11]. For example, Nakamoto [11] considered the 3-cycle reversal to deal with those orientations in plane triangulations where each vertex on the outer facial cycle has out-degree 1 while each of the other vertices has out-degree 3. In [13], Zhang et al. introduced the Z-transformation to study the connection among perfect matchings in hexagonal systems, which was later extended to general plane bipartite graphs [14].

A natural considering of circuit reversal for orientations of a surface graph is to reverse a directed facial circuit (the circuit that bounds a face). However, an orientation of a surface graph does not always have such a directed facial circuit, even if it has many directed circuits. In [2], Felsner introduced a type of circuit reversals, namely the flip, defined on the essential cycles in plane graphs which reverses a counterclockwise essential cycle to be clockwise. In a strongly connected $\alpha$-orientation of a plane graph, every essential cycle is exactly an inner facial circuit. In this sense, the notion of essential cycle is a very nice generalization of that of facial circuit. Further, Felsner proved that any $\alpha$-orientation of a plane graph can be transformed into a particular $\alpha$-orientation by a flip sequence, and the set of all $\alpha$-orientations of the graph carries a distributive lattice by flips.

The notion of flip has been also extended to general surface graphs [6, 12] and oriented matroids [9]. Moreover, Propp proved the following result (where the notion of homology will be given in the next section).

We note that the above theorem is an extension of the one given by Felsner for plane graphs since a plane graph can be regarded as a sphere graph where the outer facial circuit is treated as the forbidden circuit.

In this paper, in stead of a prescribed forbidden facial circuit, we consider the flips on surface graph with a class of prescribed forbidden facial circuits ${\cal C}$, and call such flips the ${\cal C}$-forbidden flips. In the third section, we give a sufficient and necessary condition for that an $\alpha$-orientation can be transformed into another by a sequence of ${\cal C}$-forbidden flips and, further, give an explicit formula for the minimum number of the flips needed in such a sequence. In particular, if ${\cal C}$ is empty then an $\alpha$-orientation can be transformed into another by flips if and only if they are homologous. In our study, the idea of potential function [2], or depth function [11], plays an important role.

In the last section, we focus on the relationship among all $\alpha$-orientations in a surface graph $G$. To this end, given a class ${\cal C}$ of forbidden facial circuits, we define a directed graph, namely the ${\cal C}$-forbidden flip graph, whose vertex set is the class of all $\alpha$-orientations of $G$ and two orientations $D$ and $D^{\prime}$ are joined by an edge with direction from $D^{\prime}$ to $D$ provided $D$ can be transformed from $D^{\prime}$ by a ${\cal C}$-forbidden flip. We apply the technique of U-coloring and L-coloring introduced by Felsner and Knauer in [3], and show that the ${\cal C}$-forbidden flip graph admits both a U- and L-coloring for any class ${\cal C}$. This yields a generalization of Theorem 1.1. More specifically, if ${\cal C}$ is not empty, then the flip graph has exactly $|O(G,{\cal C})|$ components, each of which is the cover graph of a distributive lattice, where $|O(G,{\cal C})|$ is the number of the $\alpha$-orientations that has no counterclockwise facial circuit other than that in ${\cal C}$. And if ${\cal C}$ is empty, then every non-trivial component of the flip graph is strongly connected, and hence cyclic.

In this section we introduce some elementary concepts involving graphs and graph embeddings on surfaces. For a graph $G$ (directed or undirected), we denote by $V(G)$ and $E(G)$ the vertex set and edge set of $G$, respectively. A closed walk in a graph is a sequence $v_{1}v_{2}\dotsc v_{k}$ such that $v_{1}$ and $v_{k}$ are adjacent and, for every $i\in\{1,2,\dotsc,k-1\}$, $v_{i}$ and $v_{i+1}$ are adjacent. A closed walk is called a cycle if it is edge disjoint and a circuit if it is vertex disjoint. The directed circuit and directed cycle are defined analogously. An orientation of a graph $G$ is an assignment of a direction to each edge of $G$. Given a graph $G$ with $n$ vertices $v_{1},v_{2},\dotsc,v_{n}$ and an out-degree sequence $\alpha=(\alpha(v_{1}),\alpha(v_{2}),\dotsc,\alpha(v_{n}))$, an orientation $D$ of $G$ is called an $\alpha$-orientation [2] if $d^{+}_{D}(v_{i})=\alpha(v_{i})$ for all $v_{i}\in V(G)$, where $d^{+}_{D}(v_{i})$ is the out-degree of $v_{i}$ in $D$. It is well known that if an $\alpha$-orientation of $G$ is strongly connected, then every $\alpha$-orientation of $G$ is strongly connected. In this case, we call $\alpha$ strongly connected. It is also known that each component obtained from an $\alpha$-orientation by deleting all those edges that have the same direction in every $\alpha$-orientation of $G$ (i.e., the rigid edges [2, 6]) is strongly connected [9]. So in this paper, we always assume that $\alpha$ is strongly connected and, hence, $G$ is 2-edge connected.

A surface graph is a graph $G$ embedded on an orientable surface $\Sigma$ without boundary. The connected components of $\Sigma\setminus G$, when viewed as subsets of $\Sigma$, are called the faces of $G$. A closed walk that bounds a face is called a facial walk. A surface graph is called a 2-cell embedding [7] or map [6] if all its faces are homeomorphic to open disks. A cycle $C$ on a surface $\Sigma$ is separating if $\Sigma\setminus C$ is disconnected and is contractible [7] if $C$ can be continuously transformed into a single point. We note that if a cycle is contractible, then it is separating and, moreover, one component of $\Sigma\setminus C$ is homeomorphic to an open disc. In this paper, except where otherwise stated, we always assume that all the surface graphs are 2-cell embedded and every edge is on the boundary of two distinct faces. We note that, in such an embedding, a facial walk is exactly a facial circuit and, therefore, every edge is shared by two distinct facial circuits. Thus, our embedding is stronger than 2-cell embedding, but weaker than the one in which each facial circuit is contractible.

A directed facial circuit $F$ is called counterclockwise (resp., clockwise), or ccw (resp., cw) for short, if when we trace along with the orientation of $F$, the face bounded by $F$ lies to the left (resp., right) side of $F$. A flip taking on a ccw facial circuit $F$ is the reorientation of $F$ that reverses $F$ from ccw to cw [2]. The notion of flip was introduced initially for the essential circuits. As mentioned earlier, in a strongly connected $\alpha$-orientation of $G$, every essential circuit is a facial circuit [9].

Let $G$ be a surface graph with edge set $E$ of $m$ edges and let $D_{0}$ be a fixed orientation of $G$. Consider the $m$-dimensional edge space $\mathbb{Z}^{|E|}$ of $G$. It is clear that any oriented subgraph $D$ of $G$ can be represented as an $m$-dimensional vector $\phi(D)\in\mathbb{Z}^{|E|}$ whose coordinate indexed by an edge $e$ is defined by

Moreover, all oriented even subgraphs (the in-degree of each vertex equals its out-degree) of $G$ form an $(m-n+1)$-dimensional subspace of $\mathbb{Z}^{|E|}$, called the (directed) cycle space of $G$, where $n$ is the number of vertices in $G$.

For a simple graph $G$, a basis of the cycle space can be created by the elementary cycles associated with a given spanning tree of $G$. For a graph (not necessarily simple) embedded on a surface, it would be more convenient to create a basis of the cycle space by the facial circuits in ${\cal F}\setminus\{F_{0}\}$ and a so-called basis for the homology, where and herein after, ${\cal F}$ denotes the set of all facial circuits of $G$ and $F_{0}$ is an arbitrary facial circuit in ${\cal F}$. A common approach to create a basis for the homology is to choose a spanning tree $T$ in $G$ and a spanning tree $T^{*}$ in the dual graph $G^{*}$ of $G$ that contains no edge dual to $T$. By Euler’s formula, there are exactly $2g$ edges in $G$ that are neither in $T$ nor dual to the edges in $T^{*}$, where $g$ is the genus of the surface. Each of these $2g$ edges forms a unique circuit with $T$ and all these $2g$ circuits form a basis for the homology [6], denoted by ${\cal H}$. In a word, any oriented even subgraph $D$ of $G$ can be uniquely represented as a linear combination of the facial circuits in ${\cal F}\setminus\{F_{0}\}$ and circuits in ${\cal H}$, i.e.,

In the following we always choose the orientation of each facial circuit in ${\cal F}$ to be ccw. Let $\mathbb{F}$ be the subspace of $\mathbb{Z}^{|E|}$ generated by ${\cal F}$. An oriented even subgraph $D$ is called null-homologous or 0-homologous [6] if $\phi(D)\in\mathbb{F}$, i.e.,

For two $\alpha$-orientations $D$ and $D^{\prime}$, we denote by $D^{\prime}-D$ the directed subgraph obtained from $D^{\prime}$ by removing those edges that has the same direction as that in $D$. It is clear that $D^{\prime}-D$ is oriented even graph. Further, if $\phi(D^{\prime}-D)\in\mathbb{F}$ then $D$ and $D^{\prime}$ are called homologous [6]. Equivalently, $D$ and $D^{\prime}$ are homologous if and only if their corresponding coefficients $\mu_{H}$ in (1) are the same for every $H\in{\cal H}$. It is clear that homology is an equivalence relation on $\alpha$-orientations.

Let $D$ and $D^{\prime}$ be two homologous $\alpha$-orientations of a surface graph $G$. Following the idea of potential function [2] (or depth function [11]), we introduce an intuitive representation of $\phi(D^{\prime}-D)$ as follows: define

to be the function which assigns an integer to each facial circuit $F$ of $G$ according to the following rule, see Figure 1:
1. $z_{D^{\prime}-D}(F_{0})=0$;
2. if $F$ and $F^{\prime}$ share a common edge $e$ then

where, by ‘$F$ lies to the left of $e$’ we mean that $F$ lies to the left side of $e$ when we trace along with the direction of $e$.

Let

and let $F_{\min}$ be a facial circuit for which $z_{D^{\prime}-D}(F_{\min})=z_{\min}$.

We now give an extension of Lemma 3.3 as follows.

For a class ${\cal C}$ of forbidden facial circuits of a surface graph $G$, we define the ${\cal C}$-forbidden flip graph of $G$ as a directed graph, denoted by ${\bf D}({\cal C})$, whose vertex set is the class of all $\alpha$-orientations of $G$, and two orientations $D$ and $D^{\prime}$ are joined by a directed edge from $D^{\prime}$ to $D$ provided $D$ can be transformed from $D^{\prime}$ by a ${\cal C}$-forbidden flip, or equivalently, $D^{\prime}-D$ is a ccw facial circuit and $D^{\prime}-D\notin{\cal C}$. Since the homology is an equivalence relation, the $\alpha$-orientations of $G$ can be partitioned into several equivalence classes, say $\Omega_{1},\Omega_{2},\dotsc,\Omega_{q}$. For $k\in\{1,2,\dotsc,q\}$, let ${\bf D}_{k}({\cal C})$ be the subgraph of ${\bf D}({\cal C})$ induced by $\Omega_{k}$. If ${\cal C}$ consists of exactly one facial circuit, then by Theorem 1.1, ${\bf D}_{k}({\cal C})$ is the cover graph of a distributive lattice.

In this section we consider the general case, in which the forbidden class ${\cal C}$ consists of any number of facial circuits (in particular, ${\cal C}$ may be empty). To this end, we apply the technique of U-coloring and L-coloring, which was introduced by Felsner and Knauer to characterize the cover graph of distributive lattices.

For a directed graph $D=(V,E)$ and two vertices $u,v\in V$, we use $(u,v)$ to denote the directed edge joining $u$ and $v$ with direction from $u$ to $v$. An edge coloring $c$ of $D$ is called a U-coloring if for every $u,v,w\in V$ with $u\not=w$ and $(v,u),(v,w)\in E$, the following two rules hold [3]:
(U₁). $c(v,u)\not=c(v,w)$;
(U₂). There is a vertex $z\in V$ and edges $(u,z),(w,z)$ such that $c(v,u)=c(w,z)$ and $c(v,w)=c(u,z)$.

An L-coloring is defined as the dual, in the sense of edge direction reversal, to a U-coloring, that is, every directed edge $(i,j)$ in the definition of U-coloring is replaced by $(j,i)$.

We now turn to our flip graph. Let ${\cal F}=\{F_{1},F_{2},\dotsc,F_{|{\cal F}|}\}$ be the class of all facial circuits of $G$. An edge of ${\bf D}(\emptyset)$ is called of type $F_{i}$ if it corresponds to a flip taking on $F_{i}$. Let ${\bf E}_{i}$ be the set of the edges of type $F_{i}$ and let ${\bf c}:E({\bf D}(\emptyset))\rightarrow\{1,2,\dotsc,|{\cal F}|\}$ be the edge coloring of ${\bf D}(\emptyset)$ such that ${\bf c}({\bf e})=i$ for each ${\bf e}\in{\bf E}_{i},i=1,2,\dotsc,|{\cal F}|$.

For a set E of edges in ${\bf D}(\emptyset)$, we denote by ${\bf D}(\emptyset)-{\bf E}$ the directed graph obtained from ${\bf D}(\emptyset)$ by deleting all the edges in E. By the definition of the edge coloring ${\bf c}$, the following proposition is obvious.

In contrast to the U- and L-colorings for the cover graph of a lattice, we will see that ${\bf D}({\cal C})$ may be cyclic if ${\cal C}=\emptyset$, which gives a non-trivial example of cyclic directed graph that admits a U- and an L-coloring. As an example, let us consider the surface graph $G$ in Example 1. Recall that the equivalence classes, i.e., the homologous classes, of the $(2,2,2,2)$-orientations of $G$ are

This means that the flip graph ${\bf D}(\emptyset)$ of $G$ consists of 12 isolated vertices $D_{1},D_{2},\dotsc,D_{12}$ and the subgraph ${\bf D}_{13}(\emptyset)$ induced by $\Omega_{13}$, where ${\bf D}_{13}(\emptyset)$ is illustrated as in Figure 4 and is cyclic. Further, by Proposition 4.4, we have ${\bf D}_{13}(\{F_{4}\})={\bf D}_{13}(\emptyset)-{\bf E}_{4}$ and ${\bf D}_{13}(\{F_{1},F_{4}\})={\bf D}_{13}(\emptyset)-({\bf E}_{1}\cup{\bf E}_{4})$. Moreover, ${\bf D}_{13}(\{F_{4}\})$ has one component and ${\bf D}_{13}(\{F_{1},F_{4}\})$ has three components, each of which is the cover graph of a distributive lattice, see Figure 4.

Recall that a directed graph $D$ is strongly connected if for any two vertices $u$ and $v$, there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$. The maximum integer $s$ for which $D\setminus H$ is strongly connected for any set $H$ of at most $s-1$ edges is called the strong edge-connectivity of $D$ and is denoted by $\kappa^{\prime}(D)$.

For $k\in\{1,2,\ldots,q\}$, let $O_{k}(G,{\cal C})$ be the class of all the $\alpha$-orientations in $\Omega_{k}$ that has no ccw facial circuit other than that in ${\cal C}$ and let $O(G,{\cal C})=\bigcup_{k=1}^{q}O_{k}(G,{\cal C})$. Similarly, let $O^{*}_{k}(G,{\cal C})$ be the class of all the $\alpha$-orientations in $\Omega_{k}$ that has no cw facial circuit other than that in ${\cal C}$. We can see that, for any $D\in O_{k}(G,{\cal C})$, the orientation obtained from $D$ by reversing the directions of all edges of $D$ is in $O^{*}_{k}(G,{\cal C})$, and vise versa. This means that $|O_{k}(G,{\cal C})|=|O^{*}_{k}(G,{\cal C})|$. For instance, in the example above we have $O_{13}(G,\{F_{1},F_{4}\})=\{D_{13},D_{15},D_{18}\}$ and $O^{*}_{13}(G,\{F_{1},F_{4}\})=\{D_{14},D_{15},D_{18}\}$, see Figure 2. Further, we can see that $D_{13},D_{15},D_{18}$ and $D_{14},D_{15},D_{18}$ are exactly the three sinks and three sources of ${\bf D}_{13}(\{F_{1},F_{4}\})$, respectively, see Figure 4.