Listing Spanning Trees of Outerplanar Graphs
by Pivot-Exchanges

We introduce some more notation. For a graph $G$, we write $V(G)$ and $E(G)$ for set of vertices and edges of $G$, respectively. For a subgraph $H\subseteq G$ and edges $e\in E(H)$ and $f\in E(G)\setminus E(H)$, we write $H-e$ and $H+f$ for the graphs obtained from $H$ by removing and adding the edges $e$ and $f$, respectively. We will think of a subgraph $H$ as a subset of edges from $E(G)$, so the operations $H-e$ and $H+f$ remove and add an element from the set, respectively. Formally, an edge exchange for a spanning tree $T\in 𝒯(G)$ is a pair $\{e,f\}$ of edges such that $e\in E(T)$ and $f\in E(G)\setminus E(T)$ with $T-e+f=T\mathrm{△}\{e,f\}\in 𝒯(G)$.

Cameron, Grubb, and Sawada [3] introduced the stronger notion of a pivot-exchange, which is an exchange $\{e,f\}$ with the additional property that $e$ and $f$ have a common end vertex. For example, in the graph $G$ shown in Figure 1, all exchanges except $\{1,5\}$ and $\{2,4\}$ are pivot-exchanges. They raised the following problem.

Additionally, they asked if such a listing can be computed using a greedy strategy, and possibly by an efficient algorithm. Problem 1 is a special case of a more general question raised by Knuth in Vol. 4A of his seminal series “The Art of Computer Programming” [14], stated as problem 102 in Section 7.2.1.6 with a difficulty rating of 46/50: ¹¹1A flawed attempt at settling this problem was published in [5] (see [22]).

Note that for any exchange $\{e,f\}$ in this directed setting, in order to preserve the arborescence property, the arcs $e$ and $f$ must point to the same vertex, i.e., it must be a pivot-exchange. Furthermore, a positive answer to Problem 2 would imply an affirmative answer to Problem 1: Indeed, given an undirected graph $G$, construct the directed graph $G^{\leftrightarrows }$ by replacing each undirected edge of $G$ by two oppositely oriented arcs, and pick an arbitrary vertex as root $r$. Listing the oriented spanning trees of $G^{\leftrightarrows }$ by arc exchanges produces every spanning tree of $G$ exactly once, namely in the orientation forced by the choice of $r$.

As a first step towards Problem 1, Cameron, Grubb, and Sawada [3] provided a pivot-exchange Gray code for listing the spanning trees of fan graphs $F_n$, which are obtained by joining an extra vertex to all vertices of a path on $n-1$ vertices; see Figure 3.

The output of their algorithm for the case $n=5$ is shown in Figure 2 (b). The algorithm uses a greedy strategy that prioritizes exchanges based on vertex labels.

Merino, Mütze and Williams [17] discovered a simple greedy algorithm for listing the spanning trees of a graph $G$ by (arbitrary) edge exchanges. The algorithm operates based on a total ordering of the edges of $G$, which is captured by labeling the edges by integers. Specifically, if $m$ denotes the number of edges of $G$, then an edge labeling is a bijection $\mathrm{\ell }:E(G)\to \{1,\mathrm{\dots },m\}$. For an edge $e\in E(G)$, we refer to $\mathrm{\ell }(e)$ as the label of the edge $e$. In the following examples, we will often identify edges by their labels. In particular, edge exchanges $\{e,f\}$ will be denoted by the pairs of labels $\{\mathrm{\ell }(e),\mathrm{\ell }(f)\}$. We will also use the abbreviation $[m]:=\{1,\mathrm{\dots },m\}$.

The output of Algorithm G when applied to the fan graph $F_5$ is shown in Figure 2 (c), using the edge labeling displayed on the left. To illustrate the greedy rule in step G2, when reaching the sixth spanning tree $T_6=\{1,2,5,6\}$, there are seven possible edge exchanges to obtain another spanning tree in $𝒯(F_5)$, namely $\{1,3\}$, $\{2,3\}$, $\{1,4\}$, $\{2,4\}$, $\{4,5\}$, $\{5,7\}$ and $\{6,7\}$; see Figure 4. Only $\{1,4\}$, $\{2,4\}$, $\{5,7\}$ and $\{6,7\}$ give an unvisited spanning tree, and among those, $\{1,4\}$ and $\{2,4\}$, minimize the larger label, which is 4. In this case, the exchange $\{2,4\}$ is applied, but $\{1,4\}$ would be a valid alternative for the algorithm.

In general, in step G2 there may be several edge exchanges

applicable to the current spanning tree to give an unvisited spanning tree, which all have $\mathrm{\ell }(f)$ as the larger label, differing only in the smaller label $\mathrm{\ell }(e_i)$, $i\in [t]$. We refer to such a situation as a tie. A tie-breaking rule is a procedure that determines which exchange to apply in case of a tie.

By definition of the step G2, Algorithm G only selects edge exchanges that result in a previously unvisited spanning tree of $G$, i.e., the produced listing of spanning trees will not contain repetitions. However, it could be that the algorithm terminates before having visited the entire set $𝒯(G)$, a situation that is ruled out by the next theorem.

A listing of bitstrings is called genlex if all strings with the same suffix appear consecutively. In particular, all strings ending with 0 appear before all strings ending with 1, or vice versa. A genlex listing of bitstrings is also sometimes referred to as suffix-partitioned in the literature. Note that genlex order generalizes colexicographic order. In the context of spanning trees, the genlex property refers to the corresponding characteristic vectors $\chi (T)$ of spanning trees $T\in 𝒯(G)$; see the right-hand side of Figure 2 (c). In other words, all spanning trees not containing the highest-labeled edge appear before all spanning trees containing this edge, or vice versa, and this property is true recursively within the blocks.

As evidenced by this theorem, the greedy Algorithm G is very powerful and versatile. In fact, the algorithm can be generalized for listing the bases of any matroid by base exchanges, and even more generally, for traversing a Hamilton path on the skeleton of any 0/1-polytope [16].

The paper [17] also introduced another closeness condition for edge exchanges, which is well-defined only for plane graphs. Specifically, a face-exchange between two spanning trees of a plane graph is an exchange of two edges that lie on a common face. If an edge exchange is both a pivot-exchange and face-exchange, then we refer to it as a pivot$\wedge$face-exchange. A weaker requirement is that it is a pivot-exchange or a face-exchange, and then we refer to it as a pivot$\vee$face-exchange. These notions give rise to the following question.

Pivot- and face-exchanges are connected through the well-known concept of the dual graph; see Figure 5 (a). For a plane graph $G$, we write $F(G)$ for the set of faces of $G$. The dual graph $G^{\prime }$ is the plane graph obtained from $G$ as follows: For every face $\alpha \in F(G)$, the dual graph $G^{\prime }$ has a vertex ${\alpha }^{\prime }\in V(G^{\prime })$, and for every edge $e$ of $G$ between faces $\alpha$ and $\beta$ of $G$, the dual graph $G^{\prime }$ has the edge $e^{\prime }=({\alpha }^{\prime },{\beta }^{\prime })$. For every vertex $v\in V(G)$, we write $v^{\prime }\in F(G^{\prime })$ for the corresponding face of $G^{\prime }$ dual to it. For a spanning tree $T\in 𝒯(G)$, the dual spanning tree $T^{\prime }\in 𝒯(G^{\prime })$ has the dual edge $e^{\prime }\in E(T^{\prime })$ for every non-edge $e\in E(G)\setminus E(T)$ and a dual non-edge $e^{\prime }\notin E(T^{\prime })$ for every edge $e\in E(T)$; see Figure 5 (b). Observe that a pivot-exchange $\{e,f\}$ in $T$ is a face-exchange $\{e^{\prime },f^{\prime }\}$ in the dual spanning tree $T^{\prime }$; see Figure 5 (c). Symmetrically, a face-exchange $\{e,f\}$ in $T$ is a pivot-exchange $\{e^{\prime },f^{\prime }\}$ in $T^{\prime }$.

Merino, Mütze and Williams [17] strengthened Theorem 3, by showing that for a suitable edge labeling of the fan graph $F_n$ and a suitable tie-breaking rule, Algorithm G yields a pivot$\wedge$face-exchange Gray code. Specifically, the edges of $F_n$ are labeled from left-to-right, as shown in Figure 2 (c), and ties are broken according to the closest tie-breaking rule, which in case of a tie as in (1) selects the exchange $\{e_t,f\}$, i.e., the exchange that maximizes the smaller of the edge labels $\mathrm{\ell }(e_t)$ (equivalently, the one for which the smaller label is closest to the larger label $\mathrm{\ell }(f)$).

In fact, the Gray code from Theorem 3 also has the stronger pivot$\wedge$face-exchange property.

In this work, we solve Problems 1 and 5 for certain families of plane graphs that generalize fan graphs, thus generalizing Theorems 3 and 6.

An outerplane graph is a plane graph in which all vertices are incident to the outer face. An outerplane graph is a triangulation if all of its faces, except possibly the outer face, are triangles. Note that fan graphs are a very special case of outerplane triangulations.

These theorems directly yield efficient algorithms. Specifically, using the techniques described in [16, Sec. 7.2+Cor. 32], Algorithm G can be implemented to output each spanning tree in time $𝒪(n\log n)$, where $n$ is the number of vertices of $G$. The required space for the algorithm is $𝒪(n)$. In particular, this implementation is history-free in the sense that no previously computed spanning trees apart from the current spanning tree need to be stored, plus some simple data structures for bookkeeping.

Two examples of Gray code listings of spanning trees obtained from these theorems are shown in Figure 6.

The weak dual graph of a plane graph $G$, denoted $G^{-}$ is the graph obtained from the dual graph $G^{\prime }$ by removing the vertex corresponding to the outer face of $G$; see Figure 7 (a).

Note that $G$ is a 2-connected outerplane graph if and only if the weak dual $G^{-}$ is a tree; see Figure 7 (b). Also note that $G^{-}$ is a path if and only if $G$ is 2-connected and all but at most two sides of every inner face are incident with the outer face; see Figure 7 (c). In particular, for a triangulation $G$, we have that $G^{-}$ is a path if and only if $G$ is 2-connected and at least one side of every triangle touches the outer face. This is true in particular for fan graphs $F_n$.

We show that fan graphs, and more generally outerplane triangulations for which the weak dual is a path, are exactly the outerplane graphs that have the maximum number of spanning trees for a fixed number of edges. Moreover, the counts are the Fibonacci numbers, defined as $f_0:=0$, $f_1:=1$ and

for all $m\ge 1$. We write $t(G):=|𝒯(G)|$ for the number of spanning trees of $G$.

The identity $t(G)=f_{m+1}$ when $G$ is a triangulation for which $G^{-}$ is a path was already noticed by Slater [29, Prop. 1].

There has been an extensive amount of work [23, 9, 15, 12, 27, 28] on efficiently generating the set $𝒯(G)$ of all spanning trees of $G$, without the requirement that any two consecutive trees differ in an edge exchange, i.e., the computed listings are not Hamilton paths or cycles in the flip graph $ℱ(G)$. The algorithms in the last three of the aforementioned papers achieve this in time $𝒪(1)$ on average per generated tree. See the survey [4] for a comparison of the different algorithms.

If instead of listing all spanning trees of $G$, we want to count them, then this can be achieved by Kirchhoff’s Matrix-Tree Theorem, which reduces the problem to computing a determinant, which can be done efficiently. This problem is closely connected to finding the so-called most vital edge of $G$, which is the edge contained in the most spanning trees from $𝒯(G)$. Random sampling [1, 2] and ranking/unranking [6, 7] of spanning trees have also been considered.

In Section 2 we prove Theorems 7 and 8. In Section 3 we prove Theorem 10. We conclude with some open questions in Section 4, and there we also report on some experimental evidence.

To define the edge labeling, we need another definition. Let $v$ be the vertex of $G^{\prime }$ corresponding to the outer face of $G$, and let $d$ be the degree of $v$. The split dual graph, denoted $G^{\ast }$, is obtained from $G^{\prime }$ by splitting $v$ into $d$ many degree-1 vertices, one adjacent to each neighbor of $v$; see Figure 8 (a).

Note that the weak dual graph $G^{-}$ is a tree if and only if the split dual graph $G^{\ast }$ is a tree; see Figures 7 (b) and 8 (b). Furthermore, $G^{-}$ is a path if and only if $G^{\ast }$ is a caterpillar, i.e., a tree in which all vertices are in distance $\le 1$ from a central path; see Figures 7 (c) and 8 (c).

Let $G$ be a 2-connected outerplane graph with $m$ edges. We consider the split dual tree $G^{\ast }$, we pick a leaf $r$ of this tree as root, and we orient all of its edges away from $r$, giving an oriented tree  , referred to as oriented split dual. We label the edges of  in a depth-first-search manner with integers $1,\mathrm{\dots },m$, starting at the root $r$ and processing subtrees in counterclockwise (ccw) order; see Figure 9. The labeling of the edges of  induces a labeling of the corresponding dual edges of $G$ with integers from $[m]$. We refer to this labeling of the edges of $G$ as dual-tree labeling. Note that there is freedom in the choice of the root in the tree $G^{\ast }$, and different choices yield different oriented split dual trees  and hence different edge labelings of the same graph $G$. Note that the left-to-right labeling of the fan graph $G=F_n$ shown in Figure 2 (c) is one particular dual-tree labeling.

Throughout this section, we let $G$ be a 2-connected outerplane graph with $m$ edges, an oriented split dual tree, and $\mathrm{\ell }:E(G)\to [m]$ the corresponding dual-tree labeling of the edges of $G$. Before proving Theorems 7 and 8, we first derive two properties of the edge labelings defined in the previous section, stated in Lemmas 13 and 14 below.

The following definitions are illustrated in Figure 10. We denote a face $\alpha$ of $G$ of length $t$ by the sequence of edges $(e_1,\mathrm{\dots },e_t)$ bounding this face in ccw order, starting with the edge $e_1$ whose dual edge in  is oriented towards ${\alpha }^{\prime }$ (all other edges of  are oriented away from ${\alpha }^{\prime }$). For a face $\alpha =(e_1,\mathrm{\dots },e_t)$ and an index $i\in [t]$, the $(\alpha ,e_i)$-lobe $L_{\alpha ,e_i}$ is the set of edges of $G$ that are dual to the edges in the maximal subtree of $G^{\ast }$ that contains the edge $e_i^{\prime }$, but none of the other edges $e_j^{\prime }$, $j\in [t]\setminus \{i\}$.