Edge-Orders

Abstract

Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying link behind all these orders has been shown that links them to well-known graph decompositions into parts that have a prescribed vertex-connectivity. Despite extensive interest in canonical orderings, no analogue of this unifying concept is known for edge-connectivity. In this paper, we establish such a concept named edge-orders and show how to compute (1, 1)-edge-orders of 2-edge-connected graphs as well as (2, 1)-edge-orders of 3-edge-connected graphs in linear time, respectively. While the former can be seen as the edge-variants of st-numberings, the latter are the edge-variants of Mondshein sequences and non-separating ear decompositions. The methods that we use for obtaining such edge-orders differ considerably in almost all details from the ones used for their vertex-counterparts, as different graph-theoretic constructions are used in the inductive proof and standard reductions from edge- to vertex-connectivity are bound to fail. As a first application, we consider the famous Edge-Independent Spanning Tree Conjecture, which asserts that every k-edge-connected graph contains k rooted spanning trees that are pairwise edge-independent. We illustrate the impact of the above edge-orders by deducing algorithms that construct 2- and 3-edge independent spanning trees of 2- and 3-edge-connected graphs, the latter of which improves the best known running time from $O(n^2)$ to linear time.

1 Introduction

Canonical orderings serve as a fundamental tool in various fields of algorithmic graph theory, see [2, 30] for a wealth of applications. Under this name, canonical orderings were published in 1988 for maximal planar graphs [8] and soon after generalized to 3-connected planar graphs [18]. Interestingly, it turned out only recently [30] that the well-known non-separating ear decompositions [6] are in fact strict generalizations of canonical orderings to arbitrary 3-connected graphs, and that this generalization was, independently, already known as (2, 1)-sequences [23] in 1971 long before canonical orderings were even proposed (anticipating many of their later planar features).

Mondshein [23] characterized (2,1)-sequences, or (2, 1)-orders, as we will call them, by decomposing a graph into 2-connected and connected parts. Indeed, the unifying link above allows to describe any canonical ordering of a graph $G=(V,E)$ as a total order on V such that for certain i, the first i vertices induce a 2-connected graph and the remaining vertices induce a connected graph in G [30] (note that this does not use any reference to planarity). The general concept behind canonical orderings is thus connectivity, with all of its implications for planarity, instead of planarity itself.

Several publications [4, 7, 24] extended this approach by proving a $(k,\ell )$-order for specific pairs $(k,\ell ) \ne (2,1)$. Such $(k,\ell )$-orders may be described canonically as total orders on V such that for certain i, the first i vertices induce a k-connected graph and the remaining vertices induce an $\ell$-connected graph (a related description for planar triangulations is given in [4]). In order to make this precise, “certain i” has to be quantified for every particular pair $(k,\ell )$. For such $(k,\ell )$, this is usually done in dependence of a graph decomposition: e.g. for (2, 1)-orders, i ranges over every vertex that completes an ear (with the predecessors of that vertex) in a fixed open ear decomposition of G. Clearly, such decompositions tends to become more complex for higher k or $\ell$.

Several other well-known structures than canonical orderings fit into the context of $(k,\ell )$-orders: st-numberings and st-orientations are actually (1,1)-orders of 2-connected graphs (where i ranges over all vertices), the chain decompositions of [7] are (2,2)-orders of 4-connected graphs, and more orders on restricted graph classes such as planar graphs and triangulations are known (see Table 1 left).

The purpose of this paper is to extend this unifying view further to $(k,\ell )$-edge-orders, each of which can be described as a total order on E such that for certain i, the first i edges induce a k-edge-connected graph and the remaining edges induce a $\ell$-edge-connected graph. Despite the many known vertex-orders above, these natural edge-variants do not seem to be well-studied. In fact, we are only aware of one technical report by Annexstein et al. [1], which deals with (1,1)-edge-orders (under the name st-edge-orderings), but lacks proof details of their existence. For the (1, 1)-edge-order that we present, i ranges over all edges except st; for the (2, 1)-edge-order that we present, i ranges over all edges that, in a fixed ear decomposition of G, complete an ear with the predecessors of i.

Table 1 Left$(k,\ell )$-orders of $(k+\ell )$-connected graphs known so far and the best-known running times for constructing them. Right$(k,\ell )$-edge-orders of $(k+\ell )$-edge-connected graphs (this paper)

We show a simple algorithm that computes a (1,1)-edge-order of a 2-edge-connected graph and prove that it has running time O(m). Our main contribution is then an algorithm that computes a (2,1)-edge-order of a 3-edge-connected graph in time O(m) (see Table 1 right), of which the corresponding result for the vertex-counterpart took over 40 years.

Just like (2,1)-orders, which immediately led to improvements on the best-known running time for five applications [5, 30], (2,1)-edge-orders seem to be an important and useful tool for many graph algorithms. We give an application of them, which is related to the edge-independent spanning tree conjecture [17]: by using a (2,1)-edge-order, we show that three edge-independent spanning trees of 3-edge-connected graphs can be computed in time O(m), improving the best-known running time $O(n^2)$ by Gopalan et al. [14].

Using the approach presented in this paper, Hoyer and Thomas [15] could meanwhile show a (2,2)-edge-order of 4-edge-connected graphs, which implies that every 4-edge-connected graph has four edge-independent spanning trees.

After giving preliminary facts on ear decompositions, we explain the linear-time algorithms for computing (1,1)- and (2,1)-edge-orders in Sects. 3, 4 and 5. Section 6 then shows algorithms for computing two and three edge-independent spanning trees.

1.1 Vertex-Connectivity Versus Edge-Connectivity

In many cases, the vertex-variant of a connectivity problem is more challenging than its edge-variant, as the latter may be reduced to the former by taking its line-graph or by using the reduction from k-edge- to k-vertex-connectivity of Galil and Italiano [12]. From a top-level perspective, our (2,1)-edge-order algorithm follows the proof outline of its vertex-counterpart in [30]. Thus, it needs to be motivated that there is no obvious linear-time reduction to [30] that produces the results of this paper (of course there is a non-obvious reduction that just takes the algorithm of this paper and does not invoke [30] at all).

Clearly, a reduction to line-graphs is not possible, as this may involve a quadratic blow-up in the graph size and thus in the running time. Another reduction is the one of Galil and Italiano [12], which reduces a 3-edge-connected graph G to a 3-vertex-connected graph $G'$ in linear time. In short, the reduction works as follows. Every vertex v of degree i in G is transformed to a wheel graph with i spokes in $G'$, in which the hub represents v. Figure 1 gives an example of such a reduction, and shows a (2,1)-order of $G'$, which can be computed in linear time using [30]. The figure shows that there is no obvious way of transforming the (2,1)-order of $G'$ back to a (2,1)-edge-order of G.

Fig. 1

Reduction attempt to (2, 1)-orders of 3-connected graphs. a A 3-edge-connected graph G. b The 3-connected graph $G'$ obtained from G by applying [12], and a (2, 1)-order D of $G'$ through r3 and avoiding r1 (see [30] for notational details). Every short ear is depicted in gray and, in order to be able to distinguish between individual ears, every ear is drawn with small gaps to its endpoints. Here, the open ears $P_1,\ldots ,P_6$ of D do not correspond to ears of G

Another hint that such a reduction might be elusive is given by our application to edge-independent spanning trees. Despite extensive research, it is still not known how to reduce these to vertex-independent spanning trees (which may in turn be computed from a (2,1)-order [30]), not even for the corresponding existence results. In fact, an attempt trying to prove this turned out to be false [13]. If there was a reduction to (2,1)-orders, it would directly imply a reduction to vertex-independent spanning trees.

Hence, there is no obvious way of producing our results using old ones. Indeed, the different parts of our proof require substantially new ideas and non-trivial formalizations in comparison to [30]: Mader-sequences differ from the (BG)-sequences used in [30] (and, although they are not too far apart, it took a 27-page paper to show that the former can be computed in linear time as well [22]), the notions of non-separateness and $\overline{G_i}$ differ considerably, and, here, we need last-values in addition to just birth-values.

2 Preliminaries

We use standard graph-theoretic terminology and consider only graphs that are finite and undirected, but may contain parallel edges and self-loops. In particular, cycles may have length one or two. A separator of size one is called a cut-vertex. The 2-connected components of a graph are its inclusion-wise maximal connected subgraphs having no cut-vertex. For $k \ge 1$, let a graph G be k-edge-connected if $n := |V| \ge 2$ and G has no edge-cut of size less than k.

Definition 1

([19, 31]) An ear decomposition of a graph $G=(V,E)$ is a sequence $(P_0,P_1,\ldots ,P_k)$ of subgraphs of G that partition E such that (i) $P_0$ is a cycle that is no self-loop and (ii) every $P_i$, $1 \le i \le k$, is either a path that intersects $P_0 \cup \cdots \cup P_{i-1}$ in its endpoints or a cycle that intersects $P_0 \cup \cdots \cup P_{i-1}$ in a unique vertex $q_i$ (which we call endpoint as well). Each $P_i$ is called an ear. An ear is short if it is an edge and long otherwise.

Theorem 2

([26]) A graph is 2-edge-connected if and only if it has an ear decomposition.

According to Whitney [31], every ear decomposition has exactly $m-n+1$ ears ($m := |E|$). For any i, let $G_i = (V_i,E_i) := P_0 \cup \cdots \cup P_i$ and $\overline{E_i} := E-E_i$. We denote the subgraph of G that is induced by $\overline{E_i}$ as $\overline{G_i} = (\overline{V_i},\overline{E_i})$. Clearly, $\overline{G_j} \subset \overline{G_i}$ for every $i < j$. We note that this definition of $\overline{G_i}$ differs from the definition $\overline{G_i} := G-V_i$ that was used for (2,1)-vertex-orders [30], due to the weaker edge-connectivity assumption.

For any ear $P_i$, let inner$(P_i) := V(P_i)-V(G_{i-1})$ be the set of inner vertices of $P_i$ (for $P_0$, every vertex is an inner vertex). Hence, for a cycle $P_i \ne P_0$, inner$(P_i) = V(P_i)-q_i$. Every vertex of G is an inner vertex of exactly one long ear, which implies that, in an ear decomposition, the inner vertex sets of the long ears partition V.

Definition 3

Let $D = (P_0,P_1,\ldots ,P_{m-n})$ be an ear decomposition of G. For an edge e, let $\textit{birth}_D(e)$ be the index i such that $P_i$ contains e. For a vertex v, let $\textit{birth}_D(v)$ be the index i such that $P_i$ contains v as inner vertex and let $\textit{last}_D(v)$ be the maximal index $\textit{birth}_D(vw)$ over all neighbors w of v. Whenever D is clear from the context, we will omit the subscript D.

Thus, $P_{{ last}(v)}$ is the last ear that contains v and, seen from another perspective, the first ear $P_i$ such that $\overline{G_i}$ does not contain v. Clearly, a vertex v is contained in $\overline{G_i}$ if and only if $\textit{last}(v) > i$.

3 The (1,1)-Edge-Order

Although (1,1)-edge-orders can be seen as edge-counterparts of st-numberings, they do not seem to be well-known. Let two edges be neighbors if they share a common vertex. Annexstein et al. gave essentially the following definition.

Definition 4

([1]) Let $G=(V,E)$ be a graph with an edge st that is not a self-loop. A (1, 1)-edge-orderthroughst of G is a total order < on the edge set $E - st$ such that $m \ge 2$,

• every edge e, except for one incident to s, has a neighbor $e'$ with $e' < e$ and

• every edge e, except for one incident to t, has a neighbor $e'$ with $e < e'$.

Hence < is a total order on $E-st$ such that for all i, the first i edges and the remaining edges induce a connected graph. The two exceptional edges incident to s and t must therefore be the minimal and maximal edge of $E-st$ with respect to <. Clearly, if G has a (1,1)-edge-order through st, G is 2-edge-connected, as neither st nor any other edge can be a bridge of G (note that this requires $m \ge 2$). The converse statement was shown in [1, Proposition 4] using a special type of ear decompositions based on breadth-first-search (however, without giving details of the linear-time algorithm). Here, we aim for a simple, constructive and direct (unlike, e.g., reducing to (1,1)-orders via line-graphs) exposition of the underlying idea and show that any ear decomposition can be transformed to a (1,1)-edge-order in linear time.

We will use the incremental list order-maintenance problem, which maintains a total order subject to the operations of (i) inserting an element after a given element and (ii) comparing two distinct given elements by returning the one that is smaller in the order. Bender et al. [3] show a simple solution for an even more general problem with amortized constant time per operation; we will call this the order data structure.

Lemma 5

Let G be a 2-edge-connected graph with an edge st that is not a self-loop. Then a (1,1)-edge-order through st can be computed in time O(m).

Proof

We compute an ear decomposition D of G such that $st \in P_0$. This can be done in linear time by any text-book algorithm; see [28] for a simple one. Let $<_0$ be the total order that orders the edges in $P_0-st$ consecutively from s to t. Thus, every edge has a smaller and a larger neighbor, except for st and the two exceptional edges incident to s and t. Clearly, $<_0$ is a (1,1)-edge-order through st of the 2-edge-connected graph $G_0$. We extend $<_{i-1}$ iteratively to a (1,1)-edge-order $<_i$ of $G_i$ by adding the next ear $P_i$ of D; then $<_{m-n}$ gives the claim.

The order itself is stored in the order data structure. For every vertex x in $G_{i-1}$, let $\textit{min}(x)$ be the smaller of its two incident edges in $P_{{ {birth}}(x)}$ with respect to $<_{i-1}$ (for later arguments, define $\textit{max}(x)$ analogously as the larger such edge); clearly, $\textit{min}(x)$ and $\textit{max}(x)$ can be computed in constant time while adding $P_{{ {birth}}(x)}$. When adding the ear $P_i$ with (not necessarily distinct) endpoints x and y, let e be the smallest edge in $\{\textit{min}(x),\textit{min}(y)\}$ with respect to $<_{i-1}$ (this needs amortized constant time by using at most one comparison of the data structure). Consider all edges of $P_i$ in consecutive order starting with a neighbor of e. We obtain $<_i$ from $<_{i-1}$ by inserting these edges as one consecutive block immediately after the edge e (if $P_i$ is a cycle with endpoint s, the edges are inserted in front of the other edges); this takes amortized time proportional to the length of $P_i$. Then the first edge of $P_i$ has a smaller neighbor in $<_i$ while the last has a larger neighbor in $<_i$ (for cycles $P_i \ne P_0$, this exploits that $q_i$ has another incident edge in $G_{i-1}$ or the exceptional edge incident to s (or t) might change), which implies that $<_i$ is a (1,1)-edge-order. $\square$

This (special) (1,1)-edge-order will allow for a very easy computation of two edge-independent spanning trees in Sect. 6 and serve as a building block for the computation of three such trees. If one wants to keep the root-paths in two edge-independent spanning trees short, a different (1,1)-edge-order [1] may be computed by maintaining $\textit{min}(x)$ as the incident edge of x that is minimal in $G_i$ in the above algorithm (this can be done efficiently by updating $\textit{min}(x)$ whenever an ear with endpoint x is added). However, the latter order cannot be used for three edge-independent spanning trees.

4 The (2,1)-Edge-Order

We define (2,1)-orders as special ear decompositions.

Definition 6

Let G be a graph with distinct edges rt and ru ($t=u$ is possible). A (2, 1)-edge-order through rt and avoiding ru (see Fig. 2) is an ear decomposition D of G such that

• 1. $rt \in P_0$,

• 2. $P_{m-n} = ru$, and $\triangleright$ i.e., the last ear is the short ear ru

• 3. for every $0 \le i < m-n$, $\overline{G_i}$ contains $\textit{inner}(P_i)$ and, if $P_i$ is short, at least one endpoint of $P_i$.

Fig. 2

A (2,1)-edge-order of a 3-edge connected graph

We will denote the Properties 1, 2, and 3 of Definition 6 as Properties 6.1, 6.2, and 6.3. Property 6.2 implies that $\overline{G_i}$ contains the vertices r and u for every $0 \le i < m-n$. We call Property 6.3 the non-separateness of D. The non-separateness of D states that every inner vertex of a long ear $P_i$ has an incident edge in G that is in $\overline{G_i}$, and that every short ear $P_i$ (seen as edge) has a neighbor in $\overline{G_i}$. The name refers to the following helpful property.

Lemma 7

Let D be a (2,1)-edge-order. Then, for every $0 \le i < m-n$, $\overline{G_i}$ is connected.

Proof

Consider any $i < m-n$ and let e be any edge in $\overline{G_i}$. By Property 6.2, $r \in \overline{G_i}$. We show that $\overline{G_i}$ contains a path from one of the endpoints of e to r. This gives the claim, as $\overline{G_i}$ is an edge-induced graph and therefore does not contain isolated vertices.

Let $P_j$ be the unique ear that contains e. If $P_j$ is short, $P_j = e$ and e has a neighbor in $\overline{G_j}$ due to the non-separateness of D. If $P_j$ is long, at least one endpoint of e must be an inner vertex of $P_j$ and e has a neighbor in $\overline{G_j}$ for the same reason. Hence, in both cases we find a neighbor that is contained in an ear $P_k$ with $k > j$. By applying induction on the indices of these ears, we find a path that starts with an endpoint of e and ends with the only edge left in $\overline{G_{m-n-1}}$, namely ru. $\square$

As described in the introduction, a (2, 1)-edge-order is thus a total order on E such that for each i that completes an ear with the predecessors of i in a fixed ear decomposition, the first i edges induce a 2-edge-connected graph and the remaining edges induce a connected graph. Next, we show that the existence of a (2,1)-edge-order proves the graph to be 3-edge-connected.

Lemma 8

If G has a (2,1)-edge-order, G is 3-edge-connected.

Proof

Let D be a (2,1)-edge-order through rt and avoiding ru. Consider any vertex v of G. By transitivity of edge-connectivity, it suffices to show that G contains three edge-disjoint paths between v and r. Let $P_i$ be the ear that contains v as inner vertex. In particular $i < m-n$, as $P_i$ is long. Then $G_i$ has an ear decomposition and, due to Theorem 2, contains two edge-disjoint paths between v and r.

As $P_{m-n} = ru$ and $\overline{G_i}$ contains $\textit{inner}(P_i)$ (Properties 6.2 + 3), $\overline{G_i}$ contains v and r. According to Lemma 7, $\overline{G_i}$ is connected. Thus, $\overline{G_i}$ contains a third path between v and r, which is edge-disjoint from the first two, as $G_i$ and $\overline{G_i}$ are edge-disjoint. $\square$

Let G have a (2,1)-edge-order. Then Lemma 8 implies $\delta (G) \ge 3$. This in turn gives that, for every vertex v, $P_{{ {last}}(v)}$ is not the first ear that contains v, which implies that $P_{{ {last}}(v)}$ must have v as endpoint. In particular, if vw is an edge and $\textit{last}(v)=\textit{last}(w)=\textit{birth}(vw)$, $P_{{ {birth}}(vw)}$ is the short ear vw and, according to the non-separateness of D, we have $i = m-n$, which implies $vw = ru$.

Lemma 9

For any vertex v, $P_{{ {last}}(v)}$ has v as an endpoint. For any edge vw satisfying $\textit{last}(v)=\textit{last}(w)=\textit{birth}(vw)$, $vw = ru$.

The converse of Lemma 8 is also true: if G is 3-edge-connected, G has a (2,1)-edge-order. This gives a full characterization of 3-edge-connected graphs; however, proving the latter direction is more involved than Lemma 8. In the next section, we will prove the stronger statement that such a (2,1)-edge-order does not only exist but can actually be computed efficiently.

5 Computing a (2,1)-Edge-Order

At the heart of our algorithm is the following classical construction of 3-edge-connected graphs due to Mader.

Definition 10

The following operations on graphs are called Mader-operations (see Fig. 3).

• (a) vertex–vertex-addition Add an edge between the not necessarily distinct vertices v and w (possibly a parallel edge or, if $v=w$, a self-loop).

• (b) edge–vertex-addition Subdivide an edge ab with a vertex v and add the edge vw for a vertex w.

• (c) edge–edge-addition Subdivide two distinct edges ab and cd with vertices v and w, respectively, and add the edge vw.

Fig. 3

Mader-operations. a vertex–vertex-addition: $v=w$ is allowed. b edge–vertex-addition: $w \in \{a,b\}$ is allowed. c edge–edge-addition: $a,b \in \{c,d\}$ is allowed

The edge vw is called the added edge of the Mader-operation. Let $K_2^3$ be the graph that consists of exactly two vertices and three parallel edges.

Theorem 11

([20]) A graph G is 3-edge-connected if and only if G can be constructed from $K_2^3$ using Mader-operations.

According to Theorem 11, applying Mader-operations on 3-edge-connected graphs preserves 3-edge-connectivity. We will call a sequence of Mader-operations that constructs a 3-edge-connected graph a Mader-sequence. It has been shown that a Mader-sequence can be computed efficiently.

Theorem 12

([22, Theorem 4]) A Mader-sequence of a 3-edge-connected graph can be computed in time $O(n+m)$.

Our algorithm for computing a (2,1)-edge-order works as follows. Assume we want a (2,1)-edge-order of G through $r\overline{t}$ and avoiding $r\overline{u}$. We first compute a suitable Mader-sequence of G using Theorem 12 and start with a (2,1)-edge-order of its first graph $K_2^3$. This (2,1)-edge-order is easy to find (see Fig. 4). The crucial part of the algorithm is then to iteratively modify the given (2,1)-edge-order to a (2,1)-edge-order of the next graph in the sequence efficiently.

Fig. 4

A (2,1)-edge-order of $K_2^3$ through rt and avoiding ru

There are several technical difficulties to master. First, the edges $r\overline{t}$ and $r\overline{u}$ may be contained in different 2-connected components $A'$ and $B'$ (implying that r is a cut-vertex). As this would raise problems in the computation of the initial $K_2^3$ later, we perform in such a case the following reduction in advance. Let $\overline{A}$ be the connected component of $G {\setminus } \{r\}$ containing $\overline{t}$, $A := G[V(\overline{A}) \cup \{r\}]$ and $B := G {\setminus } V(\overline{A})$ (note that r may still be a cut-vertex of B). Since r is a cut-vertex of G, A and B are still 3-edge-connected. We compute a (2,1)-edge-order $D_A$ of A through $r\overline{t}$ avoiding an arbitrary edge $ru_A \in A' {\setminus } \{r\overline{t}\}$, and a (2,1)-edge-order $D_B$ of B through an arbitrary edge $rt_B \in B' {\setminus } \{r\overline{u}\}$ avoiding $r\overline{u}$. Then concatenating $D_A$ with $D_B$ gives a (2,1)-edge-order of G. Hence, we assume from now on that $r\overline{t}$ and $r\overline{u}$ are in the same 2-connected component of the input graph G.

Second, the edge $r\overline{t}$ (and analogously $r\overline{u}$) of G is not necessarily contained in the previous graph of the Mader-sequence, as it may have been created by a Mader-operation that subdivided a previous edge rt with the new vertex $\overline{t}$ (a more general view on this dynamics follows from the bijection between the graphs H of the Mader-sequence and H-subdivisions that are contained in G as subgraphs [22, Theorem + Corollary 1]; we refer to [27, Sections 2.3 and 4] for details of this bijection). In such cases, we take t as replacement vertex for $\overline{t}$ (and likewise u for $\overline{u}$) in the previous graph, and iterate this procedure to obtain replacement vertices for t and u in the graph before that previous graph, and so forth. This way, the replacement vertices t and u in any graph of the Mader-sequence containing r are neighbors of r.

Now a special Mader-sequence is used to harness the dynamics of the vertices r, t and u: choose a DFS-tree of G with root r such that $r\overline{t}$ and $r\overline{u}$ are backedges (this is possible, since r has degree at least three) and compute a Mader-sequence of this DFS-tree that contains these two edges in its initial $K_2^3$ (this is possible, since $r\overline{t}$ and $r\overline{u}$ are in the same 2-connected component of G). This way the $K_2^3$ consists of the two vertices r and $t=u$ by the construction of [22, p. 6], and thus all graphs in the Mader-sequence contain r (and t and u are always neighbors of r). The vertices $\overline{t}$ and $\overline{u}$ are not present in this initial $K_2^3$ unless they are identical to $t=u$ (they are however contained in the two paths from r to $t=u$ of the $K_2^3$-subdivision the bijection maps to). For every graph in the Mader-sequence, we will compute a (2,1)-edge-order through rt and avoiding ru using the previous (2,1)-edge-order (which depends on the previous and possibly different replacement vertices); then the choice of t and u ensures that the final (2,1)-edge-order of G is indeed through $r\overline{t}$ and avoids $r\overline{u}$, as desired.

Thus, consider a graph G of the above Mader-sequence for which we know a (2,1)-edge-order D and let $G'$ be the next graph in that sequence. Then $G'$ is only one Mader-operation away and we aim for an efficient modification of D into a (2,1)-edge-order $D'$ of $G'$. We will prove that there is always a modification that is local in the sense that the only ears that are modified are “near” the added edge of the Mader-operation.

Lemma 13

Let $D=(P_0,P_1,\ldots ,P_{m-n})$ be a (2,1)-edge-order of a 3-edge-connected graph G through rt and avoiding ru for replacement vertices t and u. Let $G'$ be obtained from G by applying one Mader-operation $\Gamma$ and let $t'$ and $u'$ be the replacement vertices of $G'$. Then a (2,1)-edge-order $D'$ of $G'$ through $rt'$ avoiding $ru'$ can be computed from D using only constantly many amortized constant-time modifications.

Lemma 13 is our main technical contribution and we split its proof into the following three sections. First, we introduce the operations leg, belly and head in order to combine several cases that can be handled similarly for the different types of $\Gamma$. Second, we show how to modify D to $D'$ and, third, we discuss computational issues.

For all three sections, let vw be the added edge of $\Gamma$ such that v subdivides the edge $ab \in E(G)$ and w subdivides $cd \in E(G)$ (if applicable). Thus, the vertex $t'$ in $G'$ is either t, v or w, and the vertex $u'$ in $G'$ is either u, v or w (hence, $t'r$ and $ru'$ will never be self-loops). In all three sections, birth and last will always refer to D, unless stated otherwise.

Let $P_i \ne P_0$ be an ear with a given orientation and let x be a vertex in $P_i$ (the assumed orientation will fix the start- and/or endvertex of ears in the following two definitions). If $P_i$ is a path, we define $P_i[,x]$ and $P_i[x,]$ as the maximal subpaths of $P_i$ that end and start at x, respectively; if $P_i$ is a cycle, we take the same definition with the additional restriction that $P_i[,x]$ starts at $q_i$ and $P_i[x,]$ ends at $q_i$. Occasionally, the orientation of $P_i$ will not matter; if none is given, an arbitrary orientation can be taken. For paths A and B, let $A+B$ be the concatenation of A and B.

5.1 Legs, Bellies and Heads

While the operations leg and belly are inspired by the ones in [30], the operation head is new. All three operations will show for some special cases how D can be modified to a (2,1)-edge-order $D'$. A complete description for all cases (using these operations) will be given in the next section.

5.1.1 Legs

Let $\Gamma$ be either an edge–vertex-addition such that $ab \ne ru$ and $\textit{last}(w) < \textit{birth}(ab)$ or an edge–edge-addition such that $ab \ne ru$ and $\textit{birth}(cd) < \textit{birth}(ab)$. If $P_{{ {birth}}(ab)}$ is long, at least one of a and b is an inner vertex, say w.l.o.g. b. Otherwise, $P_{{ {birth}}(ab)}=ab$ is short and, as D is non-separating, at least one of a and b, say w.l.o.g. b, has an incident edge in $\overline{G_{{ {birth}}(ab)}}$ (note that this requires $ab \ne ru$). In both cases, orient $P_{{ {birth}}(ab)}$ from a to b. The operation leg constructs $D'$ from D by replacing the ear $P_{{ {birth}}(ab)}$ of D by the two consecutive ears $P_{{ {birth}}(ab)}[,a] + av+ vw$ and $vb + P_{{ {birth}}(ab)}[b,]$ in that order and, if $\Gamma$ is an edge–edge-addition, additionally subdividing the edge cd in $P_{{ {birth}}(cd)}$ with w (see Fig. 5). Note that this definition is well-defined also for cycles $P_{{ {birth}}(ab)}$, including self-loops.

Fig. 5

The result of operation leg (dashed lines), black vertices are in $G_{{ {birth}}(ab)-1}$

We claim that $D'$ is a (2,1)-edge-order through $rt'$ avoiding $ru'$. Assume first that $\Gamma$ is an edge–vertex-addition. Since $\textit{last}(w) < \textit{birth}(ab)$, we conclude that $w \notin P_{{ {birth}}(ab)}$ (w has no incident edge “left” in $\overline{G_{{ {birth}}(ab)-1}}$). For the same reason, $\textit{birth}(ab) > 0$. Hence, no matter whether $P_{{ {birth}}(ab)}$ is a path or a cycle, w and the one or two endpoints of $P_{{ {birth}}(ab)}$ are contained in $G_{{ {birth}}(ab)-1}$. Since $D'$ partitions $E(G')$, this implies that $D'$ is an ear decomposition. If $\Gamma$ is an edge–edge-addition, $\textit{birth}(cd) \le \textit{birth}(ab)$ gives a very similar argument.

It remains to prove that $D'$ satisfies Properties 6.1–3. The first is true, as $rt \in P_0$ is only affected when $\textit{birth}(cd) = 0$ and when rt is subdivided by w; then $w = t'$ in $G'$ and $rt' \in P'_0$, as claimed. The second is true, as $cd \ne ru$ and, by assumption, $ab \ne ru$; hence, the last ear ru does not change. For the non-separateness of $D'$, it suffices to consider the two modified ears $P_{{ {birth}}(cd)}$ and $P_{{ {birth}}(ab)}$, as all other ears still satisfy non-separateness. Since the only new inner vertex w in $P'_{{ {birth}}(cd)}$ is incident to the edge $wv \in \overline{G'_{{ {birth}}(cd)}}$, $P'_{{ {birth}}(cd)}$ is also non-separating. It remains to consider the two new ears $P'_{{ {birth}}(ab)} = P_{{ {birth}}(ab)}[,a]+av+ vw$ and $P'_{{ {birth}}(ab)+1} = vb + P_{{ {birth}}(ab)}[b,]$. All inner vertices of these ears except for the new vertex v inherit their non-separateness directly from $P_{{ {birth}}(ab)}$. Since v is incident to vb, the long ear $P'_{{ {birth}}(ab)}$ is non-separating and, if $P'_{{ {birth}}(ab)+1}$ is long, $P'_{{ {birth}}(ab)+1}$ is non-separating as well. Otherwise $P'_{{ {birth}}(ab)+1}=vb$ is short and $P_{{ {birth}}(ab)}$ cannot be long due to our assumed orientation. Hence, $P_{{ {birth}}(ab)}=ab$ and the assumed orientation implies that b has an incident edge in $\overline{G_{{ {birth}}(ab)}}$, which gives that $P'_{{ {birth}}(ab)+1}$ is non-separating as well.

5.1.2 Bellies

Let $\Gamma$ be either an edge–vertex-addition such that $\textit{last}(w) = \textit{birth}(ab)$ and $w\notin \{a,b\}$ or an edge–edge-addition such that $\textit{birth}(cd) = \textit{birth}(ab)$ (note that $c,d\in \{a,b\}$ is allowed.) Consider the shortest path in $P_{{ {birth}}(ab)}$ from an endpoint to one of the vertices $\{a,b\}$, say w.l.o.g. b, such that w is contained in this path. We orient $P_{{ {birth}}(ab)}$ from a to b. $P_{{ {birth}}(ab)}$ is a long ear with b as inner vertex. If $\Gamma$ is an edge–edge-addition, one of the vertices $\{c,d\}$, say w.l.o.g. c, is contained in $P_{{ {birth}}(ab)}[,w]$.

If $\textit{birth}(ab)>0$, the operation belly constructs $D'$ from D by replacing the ear $P_{{ {birth}}(ab)}$ of D by the two consecutive ears $P_{{ {birth}}(ab)}[,a]+av+ vw + P_{{ {birth}}(ab)}[w,]$ and $vb+ P_{{ {birth}}(ab)}[b,w]$ in that order (if edge–vertex-addition) and by the two consecutive ears $P_{{ {birth}}(ab)}[,a]+av+ vw + wd+ P_{{ {birth}}(ab)}[d,]$ and $vb+ P_{{ {birth}}(ab)}[b,c]+cw$ (if edge–edge-addition), see Fig. 6. Note that this definition is well-defined also if $P_{{ {birth}}(ab)}$ is a cycle. If $\textit{birth}(ab)=0$, the vertices v and w cut $P_0$ in two distinct paths $P_{0,1}$ and $P_{0,2}$ having endpoints v and w. Let $P_{0,1}$ be the path containing r. Then the operation belly constructs $D'$ from D by replacing the ear $P_{{ {birth}}(ab)}$ of D by the two consecutive ears $P_{0,1}+ vw$ and $P_{0,2}$ in this order. If $rt\in \{ab, cd\}$, then either $v=t'$ or $w=t'$, respectively.

Fig. 6

The result of the operation belly (dashed lines)

We claim that $D'$ is a (2,1)-edge-order through $rt'$ avoiding $ru'$. No matter whether $P_{{ {birth}}(ab)}$ is a path or a cycle, the one or two endpoints of it are contained in $G_{{ {birth}}(ab)-1}$ and $D'$ partitions $E(G')$, so clearly $D'$ is an ear decomposition.

It remains to prove that $D'$ satisfies Properties 6.1–3. The first is true, as $rt \in P_0$ is only affected when $\textit{birth}(ab) = 0$. Then, if rt is subdivided by v or w, $v=t'$ or $w = t'$ in $G'$, and $rt' \in P'_0$, as claimed. The second is true, as $ru\notin \{ab,cd\}$ ($P_{{ {birth}}(ab)}\ne \{ru\}$ as it is a long ear and $\textit{birth}(cd)=\textit{birth}(ab)$); hence, the last ear ru does not change. For the non-separateness of $D'$, it again suffices to consider the modified ear $P_{{ {birth}}(ab)}$. First, assume $\textit{birth}(ab)>0$. Consider the two new ears $P'_{{ {birth}}(ab)} = P_{{ {birth}}(ab)}[,a]+av+vw+ P_{{ {birth}}(ab)}[w,]$ (respectively, $P'_{{ {birth}}(ab)} = P_{{ {birth}}(ab)}[,a]+av+vw+ wd +P_{{ {birth}}(ab)}[d,]$ if edge–edge-addition) and $P'_{{ {birth}}(ab)+1} = vb+ P_{{ {birth}}(ab)}[b,w]$ (respectively, $P'_{{ {birth}}(ab)+1} = vb+P_{{ {birth}}(ab)}[b,c]+cw$ if edge–vertex-addition). All inner vertices of these ears except for the new vertex v (and w, if edge–edge-addition) inherit their non-separateness directly from $P_{{ {birth}}(ab)}$. Since v is incident to vb (and w is incident to wc, if edge–edge-addition), the long ear $P'_{{ {birth}}(ab)}$ is non-separating and $P'_{{ {birth}}(ab)+1}$, which is long as it contains b as inner vertex, is non-separating as well. If $\textit{birth}(ab)=0$, very similar arguments show the non-separateness of the new ears.

5.1.3 Heads

Let $\Gamma$ be an edge–vertex-addition such that $w\in \{a,b\}$, $\textit{last}(a) = \textit{birth}(ab)$ and, if $ab=ru$, then $r\ne a$. W.l.o.g. let $w=a$. Then a is an endpoint of $P_{{ {birth}}(ab)}$ ($P_{{ {birth}}(ab)}$ cannot be a self-loop, as $\textit{last}(a)=\textit{birth}(ab)$). We orient $P_{{ {birth}}(ab)}$ from a to b. The operation head constructs $D'$ from D by replacing the ear $P_{{ {birth}}(ab)}$ of D by the two consecutive ears $av+va$ and $vb+P_{{ {birth}}(ab)}[b,]$ in that order (see Fig. 7). Note that this definition is well-defined also for cycles $P_{{ {birth}}(ab)}$.

Fig. 7

The dashed lines show the result of the operation head

We claim that $D'$ is a (2,1)-edge-order through $rt'$ avoiding $ru'$. Clearly, $D'$ is an ear decomposition. Property 6.1 is true, as $\textit{birth}(ab)=\textit{last}(a)>0$ and, hence, the first ear does not change. Property 6.2 is true, as the last ear is only affected when $\textit{birth}(ab) = ru$ and $r\ne a$; then $v=u'$ in $G'$ and the last ear in $D'$ is $ru'$, as claimed. For the non-separateness of $D'$, we consider the two new ears $P'_{{ {birth}}(ab)} =av+va$ and $P'_{{ {birth}}(ab)+1} =vb+P_{{ {birth}}(ab)}[b,]$. $P'_{{ {birth}}(ab)}$ is a long ear with v as only inner vertex. Since v is incident to vb, $P'_{{ {birth}}(ab)}$ is non-separating. All inner vertices of $P'_{{ {birth}}(ab)+1}$ inherit their non-separateness directly from $P_{{ {birth}}(ab)}$ and so, if $P'_{{ {birth}}(ab)+1}$ is long, $P'_{{ {birth}}(ab)+1}$ is non-separating as well. Otherwise, if $P'_{{ {birth}}(ab)+1}=vb$ is short, then either $\textit{last}(b)>\textit{last}(a)$ and so b has an incident edge in $\overline{G_{{ {birth}}(ab)}}$, which gives that $P'_{{ {birth}}(ab)+1}$ is non-separating as well. If $\textit{last}(b)=\textit{last}(a)$ then $ab=ru$ (Lemma 9) and the ear $P'_{{ {birth}}(ab)+1}$ is the last ear of $D'$ and does not have to satisfy the non-separateness.

5.2 Modifying D to D$^\prime$

We will now show how to obtain a (2,1)-edge-order $D'$ through $rt'$ avoiding $ru'$ from D. By symmetry, assume w.l.o.g. that $\textit{birth}(ab) \ge \textit{birth}(cd)$. Note that applying the operations belly, leg and head preserves all properties of a (2, 1)-edge-order. Recall that, for every subdivision the Mader-sequences does on rt or ru, respectively, the subdividing vertex is $t'$ or $u'$, as explained after Fig. 4. We have the following case distinctions:

1.:

${\Gamma }$ is a vertex–vertex-addition (see Fig. 3a)

(a):

vw is a self-loop at v ($v=w$): obtain $D'$ from D by adding the new short ear vv directly after the ear $P_{{ {last}}(v)-1}$. This ensures that the new ear is non-separating.

(b):

$v\ne w$ and $vw\ne \{rt,ru\}$: if $\textit{last}(v)\le \textit{last}(w)$, $D'$ is obtained from D by adding the new short ear vw directly after the ear $P_{{ {last}}(w)-1}$, ensuring that the new ear is non-separating. If $\textit{last}(v)> \textit{last}(w)$, the new short ear vw is added directly after the ear $P_{{ {last}}(v)-1}$.

(c):

$vw=rt$ (the added edge is a parallel edge): the Mader-sequence gives us the information whether rt is $rt'$ or the new added edge is $rt'$. If $rt =rt'$ then add the new edge immediately after the ear $P_{{ {last}}(t)-1}$. Otherwise obtain $D'$ from D by replacing rt with $rt'$ in $P_0$ and adding the old edge rt as an short ear immediately after the ear $P_{{ {last}}(t)-1}$.

(d):

$vw=ru$ (the added edge is a parallel edge): the Mader-sequence gives us the information whether ru is $ru'$ or the new added edge is $ru'$. Depending on this information, obtain $D'$ from D by either adding the new edge directly before or directly after the last ear of D.

2.:

$\Gamma$ is an edge–vertex-addition (see Fig. 3b)

(a):

$\textit{birth}(ab)<\textit{last}(w)$: obtain $D'$ from D by adding the new short ear vw directly after the ear $P_{{ {last}}(w)-1}$ and subdivide the ear $P_{{ {birth}}(ab)}$ with v. This operation is also well-defined when $P_{{ {birth}}(ab)}$ is a cycle or self-loop. Also, the new ear is non-separating and, since v is incident to w, the ear $P_{{ {birth}}(ab)}$ remains non-separating.

(b):

$\textit{last}(w) < \textit{birth}(ab)$ and $ab \ne ru$: apply leg

(c):

$\textit{birth}(ab)=\textit{last}(w)$ and $w \notin \{a,b\}$: apply belly.

(d):

$\textit{birth}(ab)=\textit{last}(w)$ and $w\in \{a,b\}$; if $ab=ru$, then $r\ne w$: apply head.

(e):

$ab=ru$ and if $\textit{birth}(ab)=\textit{last}(w)$ and $w\in \{a,b\}$ then $r=w$: obtain $D'$ from D by replacing the ear ru by the two consecutive ears $wv+vu$ and rv.

3.:

$\Gamma$ is an edge–edge-addition (see Fig. 3c)

(a):

$\textit{birth}(ab)=\textit{birth}(cd)$: apply belly.

(b):

$\textit{birth}(ab) > \textit{birth}(cd)$ and $ab \ne ru$: apply leg.

(c):

$ab=ru$: let w.l.o.g. $r=a$. Obtain $D'$ from D by replacing the last ear of D by the two consecutive ears $bv+vw$ and rv in this order.

In all cases, $D'$ is clearly an ear decomposition. Properties 6.1–3 are satisfied due to the given case distinction and the mentioned properties. Hence, $D'$ is a (2, 1)-edge-order through $rt'$ avoiding $ru'$.

5.3 Computational Complexity

The reduction to a graph G that contains $r\overline{t}$ and $r\overline{u}$ in the same 2-connected component can be computed in time O(m) by using the block-cut-tree (i.e., the tree of 2-connected components) of the input graph. The desired Mader-sequence of G can be computed by Theorem 12 in time O(m), when the initial DFS-tree is chosen as described above.

For proving Lemma 13, it remains to show that each of the constantly many modifications above can be computed in constant amortized time. Note that ears may become arbitrarily long in the process and therefore may contain up to $\Theta (n)$ vertices. Moreover, we have to maintain the birth- and last-values in order to compute which subcase of the last section applies. Thus, we cannot use the standard approach of storing the ears of D explicitly by using doubly-linked lists, as then the birth-values of linearly many vertices may change for every modification.

Instead, we will represent the ears as sets in a data structure for set splitting, which maintains disjoint sets online under an intermixed sequence of find and split operations. Gabow and Tarjan [11] discovered the first such data structure with linear space and constant amortized time per operation. Their and our model of computation is the standard unit-cost word-RAM. Imai and Asano [16] enhanced this data structure to an incremental variant, which additionally supports adding single elements to certain sets in constant amortized time. In both results, all sets are restricted to be intervals of some total order. To represent the (2,1)-edge-order D in the path replacement process, we will use the following more general data structure due to Djidjev [9, Section 3.2], which is not limited to total orders and still supports the add-operation.

The data structure maintains a collection P of edge-disjoint paths under the following operations:

new_path(x,y)::

Creates a new path that consists of the edge xy. The edge xy must not be in any other path of P.

find(e)::

Returns the integer-label of the path containing the edge e.

split(xy)::

Splits the path containing the edge xy into the two subpaths from x to one endpoint and from x to the other endpoint of that path.

sub(x,e)::

Modifies the path containing e by subdividing e with vertex x.

replace(x,y,e)::

Neither x nor y may be an endpoint of the path Z containing e. Cuts Z into the subpath from x to y and into the path that consists of the two remaining subpaths of Z joined by the new edge xy.

add(x,yz)::

The vertex y must be an endpoint of the path Z containing the edge yz and x is either a new vertex or not in Z. Adds the new edge xy to Z.

Note that all ears are not only edge-disjoint but also internally disjoint. Djidjev proved that each of the above operations can be computed in constant amortized time [9, Theorem 1]. We will only represent long ears in the data structure; the remaining short ears can be simply maintained as edges. As the data structure can only store paths, we store every cycle $P_i$ as the union of two paths in $P_i$ of which one is an edge with endpoint $q_i$ (for $P_0$, with endpoint r). For all paths of length at least two, including all long paths $P_i$, we store its two endpoints at its find()-label. Thus, the endpoints of all ears can be be accessed and updated in constant time.

This way, we store the ears of the initial (2,1)-edge-order of $K_2^3$ in constant total time. Every modification of Sect. 5.2 can then be realized with a constant number of operations of the data structure, and hence in amortized constant time.

Additionally, we need to maintain the order of the ears in D. Lemma 13 moves and inserts in every step only a constant number of ears to specified locations of D. Hence, we can maintain the order of ears in D by applying the order data structure (as defined for (1,1)-edge-oders) to the find()-labels of ears; this costs amortized constant time per step.

So far we could have maintained the order of ears also by using doubly-linked lists. However, for deciding which of the subcases in Sect. 5.2 applies, we additionally need to compare birth- and last-values of the vertices and edges involved in $\Gamma$. In fact, it suffices to support the queries “$\textit{birth}(x) < \textit{birth}(y)$” and “$\textit{birth}(x) = \textit{birth}(y)$”, where x and y may be edges or vertices, and analogous queries on the last-values of vertices. If x and y are edges, both birth-queries can be computed in constant amortized time by comparing the labels find(x) and find(y) in the order data structure. In order to allow birth-queries on vertices, we will store pointers at every vertex x to the two edges $e_1$ and $e_2$ that are incident to x in $P_{{ {birth}}(x)}$. The desired query involving $\textit{birth}(x)$ can then be computed by comparing find($\texttt {e}_1$) in the order data structure.

For any new vertex x that is added to D, we can find $e_1$ and $e_2$ in constant time, as these are in $\{av,vb,cw,wd,vw\}$. Since $P_{{ {birth}}(x)}$ may change over time, we have to update $e_1$ and $e_2$. The only situation in which $P_{{ {birth}}x)}$ may loose $e_1$ or $e_2$ (but not both) is a split or replace operation on $P_{{ {birth}}(x)}$ at x (the split operation must be followed by an add operation on x, as x is always inner vertex of some ear). This cuts $P_{{ {birth}}(x)}$ into two paths, each of which contains exactly one edge in $\{e_1,e_2\}$. Checking find($\texttt {e}_1)=\texttt {find}(\texttt {e}_2$) recognizes this case efficiently. Dependent on the particular case, we compute a new consistent pair $\{e'_1,e'_2\}$ that differs from $\{e_1,e_2\}$ in exactly one edge. Finally, the value $\textit{last}(x)$ for a vertex x can be maintained the same way as $\textit{birth}(x)$ with the only difference that it links to (one edge of) the last ear containing x instead of the first such ear. This allows to check the desired comparisons in amortized constant time.

We conclude that $D'$ can be computed from D in amortized constant time. This proves Lemma 13 and implies the following theorem.

Theorem 14

Given edges tr and ru of a 3-edge-connected graph G, a (2,1)-edge-order D of G through tr and avoiding ru can be computed in time O(m).

The proposed algorithms for (1,1)-edge-orders and (2,1)-edge-orders (as well as the computation of edge-independent spanning trees in the next section) are certifying in the sense of [21]: for (1,1)-edge-orders through st, it suffices to check that every edge $e \ne st$ has indeed a smaller and larger neighboring edge. For (2,1)-edge-orders, it suffices to check in linear time that D is an ear decomposition of G and that D satisfies Properties 6.1–3.

6 Edge-Independent Spanning Trees

Let k spanning trees of a graph be edge-independent if they all have the same root vertex r and, for every vertex $x \ne r$, the paths from x to r in the k spanning trees are edge disjoint. The following conjecture was given 1984 by Itai and Rodeh.

Conjecture

(Edge-Independent Spanning Tree Conjecture [17]) Every k-edge-connected graph contains k edge-independent spanning trees.

The conjecture has been proven constructively for $k \le 2$ [17] and $k=3$ [14] with running times O(m) and $O(n^2)$, respectively, for computing the corresponding edge-independent spanning trees. Recently, by using the approach presented in this paper, the conjecture has also been proven for $k=4$ by the existence of a (2, 2)-edge-order [15]. For every $k \ge 5$, the conjecture is open. We first give a short description of an algorithm for $k=2$ and then show the first linear-time algorithm for $k=3$.

For $k=2$, compute the (1,1)-edge-order < through tr using Lemma 5. The first tree $T_1$ consists of the edges $\textit{min}(x)$ for all vertices $x \ne r$ (as defined in Lemma 5), while the second tree $T_2$ consists of tr and the edges $\textit{max}(x)$ for all vertices $x \notin \{r,t\}$. Then $T_1$ and $T_2$ are spanning, as no edge can be taken twice, and edge-independent, as, from every vertex x, the path of smaller edges to r obtained by iteratively applying $\textit{min}()$ must be edge-disjoint from the path of larger edges to r.

For $k=3$, choose any vertex r and two distinct edges tr and ru in the 3-edge-connected graph G. Compute a (2,1)-edge-order D through tr and avoiding ru in time O(m) using Theorem 14. For every vertex $x \in V$, the idea is now to find two edge-disjoint paths from x to r in $G_{{ {birth}}(x)}$ (after all, $G_{{ {birth}}(x)}$ is 2-edge-connected and thus contains a (1,1)-edge-order) and a third path from x to r in $\overline{G_{{ {birth}}(x)}}$ using the non-separateness of D. The subtle part is to make this idea precise: we have to construct the first tree $T_1$ in such a consistent way that the paths of smaller edges from x to r for all vertices $x \in V$ are contained in $T_1$ (and the same for $T_2$ and paths of larger edges).

For a (1,1)-edge-order < through tr of G, let a spanning tree $T_1 \subseteq G$ be down-consistent to a given (2,1)-edge-order through tr if (a) every path in $T_1$ to r is strictly decreasing in < and (b) for every $0 \le i \le m-n$, $T_1 \cap G_i$ is a spanning tree of $G_i$ (analogously, up-consistent spanning trees $T_2$ of $G-r$ are defined by strictly increasing paths to t). Now let a (1,1)-edge-order be consistent to a given (2,1)-edge-order $D'$ if G contains r-rooted spanning trees $T_1$ and $T_2$ that are down- and up-consistent to $D'$, respectively. By the very same argument as used for $k=2$, $T_1$ and $T_2 + tr$ are edge-independent and, in addition, do not use any edge of $\overline{G_{{ {birth}}(x)}}$ for any $x \in V$.

Fig. 8

(1,1)-edge-orders that are consistent and not consistent to the (2,1)-edge-order of Fig. 2. a A consistent order < and the resulting three edge-independent spanning trees. b Although < is a (1,1)-edge-order for every $G_i$, $0 \le i \le m-n$, < is not consistent: any down-consistent tree contains the root-paths 12, 11, 10, 2 in $G_2$ and 6, 5, 3, 2 in $G_5$, which implies a cycle

In fact, the special (1,1)-edge-order that is computed by Lemma 5 is consistent to D: there, the trees $T_1$ and $T_2$ consist of the edges $\textit{min}(x)$ and $\textit{max}(x)$ for $x \in V$, which makes $T_1$ down-consistent and $T_2+tr$ up-consistent to D (see Fig. 8a). We note that a simpler definition of consistent as used for the vertex-variant [6], i.e., as orders that remain (1,1)-edge-orders for all subgraphs$G_i$, $0 \le i \le m-n$, does not suffice here (see Fig. 8b).

It remains to construct the third edge-independent spanning tree. For every edge $e \ne ru$ of G, we compute a pointer to an arbitrary neighboring edge $e'$ in $\overline{G_{{ {birth}}(e)}}$. This edge $e'$ exists, as D is non-separating, and satisfies $\textit{birth}(e') > \textit{birth}(e)$. Similarly, for every vertex $x \in V-r-u$, we compute a pointer to an incident edge $e'$ of x with $\textit{birth}(e') > \textit{birth}(x)$. Both computations take linear total time by comparing $\textit{birth}$ values. The third edge-independent spanning tree is then the union of ur and the u-rooted spanning tree of $G-r$ that interprets the pointers as parent edges. Hence, we obtain the following theorem.

Theorem 15

Given the two edges rt and ru of a 3-edge-connected graph G, three edge-independent spanning trees of G rooted at r (such that two of them contain rt and ru as unique root edges, respectively) can be computed in time O(m).

Relation to vertex-independent spanning trees.

The conjecture above has also received considerable attention for the vertex-case. Recently, a linear-time algorithm for computing three vertex-independent spanning trees of a 3-connected graph was given by [30]. Similarly as for the more general (2,1)-edge-orders, one could be interested why the reduction from k-edge- to k-vertex-connectivity by Galil and Italiano [12] cannot be applied to modify the 3-edge-connected input graph G to a 3-connected one such that three vertex-independent spanning trees of the latter give three edge-independent spanning trees of G.

Fig. 9

The reduction [12] cannot be applied to find edge-independent spanning trees directly, as it may construct cycles. a A 3-edge-connected graph G. b The 3-connected graph $\hat{G}$ to which G is reduced to using [12], and a (2,1)-order of $\hat{G}$ through $r\hat{t}$ avoiding $\hat{u}$ (t and u have to be replaced, as $\hat{G}$ does not contain rt and ru anymore). Gray lines depict short ears. c The three vertex-independent spanning trees $T_1,T_2,T_3$ of $\hat{G}$ implied by the (2,1)-order of $\hat{G}$ [30]. d The corresponding subgraphs of $T_1$, $T_2$ and $T_3$ in G. The red subgraph contains a cycle

The reason is that, although such a reduction attempt is able to give three edge-disjoint paths between two given vertices, for multiple vertex pairs, the union of these paths may form cycles (see Fig. 9). As argued in the introduction, such a reduction could indeed be elusive, as we do not know any way of reducing the existence of edge-independent spanning trees to the existence of their vertex-counterpart.

Direct induction. It may also seem tempting to compute the spanning trees directly without using a (2,1)-edge-order, e.g. by local replacements in an induction over either Mader-operations or inverse contractions. However, without additional restrictions this is bound to fail, as shown in Fig. 10.

Fig. 10

A 3-edge-connected graph G (some edges are not drawn). G is obtained from the 3-edge-connected graph $G':= (G-v) \cup xy$ by performing a Mader-operation (or inverse contraction) that adds the vertex v (the added edge is thus vy). Two of the three edge-independent spanning trees of $G'$ are given, rooted at r (thick edges). However, not both of them can be extended to v.

7 Conclusion

We established the new unifying concept of edge-orders, which is an analogue of canonical orders and their generalizations for edge-connectivity. We showed that st-edge-numberings a.k.a. (1, 1)-edge-orders fit into this concept, showed a simple linear-time algorithm for constructing these, and proposed the first linear-time algorithm that computes (2, 1)-edge-orders.

Additionally, we gave a first application by presenting the first linear time algorithm to compute three edge-independent spanning trees of a 3-edge-connected graph.

As a crucial open problem, we ask whether there are any pairs $(k,\ell )$ other than (1, 1), (2, 1) and (2, 2) such that every $(k+\ell )$-edge-connected graph has a $(k,\ell )$-edge-order (for an appropriate quantification of i).