<p>The problem can be reduced to the edge orientation problem. Where if tree width (number of independent trees) is c, we need to orient the edges such that each vertex has an outdegree of <em>at most</em> c.</p>

<p>For planar graphs, where c = 3, an O(n log n) algorithm is given by [1]. For general graphs, a simple O(m + n) time algorithm computing a (2c - 1) orientation is shown in [2]. Other algorithms computing exact c orientation are harder including [3] and [4].</p>

<p>[1] Grossi and Lodi. Simple planar graph partition into three forests. Discrete Applied Mathematics, 84:121-132, 1998.</p>

<p>[2] Srinivasa R. Arikati, Anil Maheshwari, and Christos D. Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78:1-16,1997.</p>

<p>[3] Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7:465-497, 1992.</p>

<p>[4] J. C. Picard and M. Queyranne. A network flow soloution to some non-linear 0-1 programming problems, with applications to graph theory. Networks, 12:141-160, 1982.</p>

CC BY-SA 3.0
2018-04-27T13:34:49.847Z
i am worried if these methods will return spanning trees or not?
immiKhan
CC BY-SA 4.0
2018-06-19T13:15:56.797Z
From c forest decomposition you can trivially get c edge orientation, by rooting each tree in every forest and assign parental edge to a vertex. The other direction gives you only a 2c forest decomposition from c edge orientation. The main problem is the formation of cycles as you compute the forest decomposition.
sbzk
CC BY-SA 4.0
2018-06-19T13:18:14.657Z
Consider the 2c forests. For each vertex, add its i^{th} out edge in 2i^{th} (or (2i-1)^{th}) forest based on whether the index of its out neighbour is lower (or higher) than itself. As a result, each even indexed forest have only edges pointing from higher index to lower index and vice versa for odd indexed forests. This ensures that no cycles are present in a forest.
sbzk
CC BY-SA 4.0
2018-07-26T17:12:53.077Z
For c=1, at least, a graph can have |V|-1 edges and a spanning tree, but not have any way of orienting the edges so that each edge has out-degree 1 (which requires |V| edges).  So it might be clearer to say in the answer what reduction you have in mind by when you write "can be reduced to..."
Neal Young
CC BY-SA 4.0
2018-07-30T08:47:46.387Z
Right updated, the out-degree has to be upper bounded by c. It can be less as well but never greater than c.
sbzk
CC BY-SA 4.0
2018-04-27T09:48:59.057Z
2018-07-30T08:46:38.563Z
2018-07-30T08:46:38.563Z
sbzk
<p>I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.</p>

CC BY-SA 4.0
2018-07-26T16:18:17.750Z
Some 3-edge connected graphs don't have three edge-disjoint spanning trees.  Consider G=(V,E) where V={a, b, c, d, e, f} and E={(a, b), (a, c), (a, d), (a, e), (b, f), (c, f), (d, f), (e, f), (b, c), (d, e)}.  I believe it is 3-edge connected, but has six vertices and only ten edges, so cannot have three edge-disjoint spanning trees.  (As each spanning tree would have five distinct edges.)
Neal Young
CC BY-SA 4.0
2018-07-26T16:51:36.410Z
p.s. conditions for a graph to have k edge-disjoint spanning trees appear to be well studied.  see e.g. https://www.math.wvu.edu/~hjlai/Pdf/Catlin_Pdf/Catlin49a.pdf .
Neal Young
<ds.algorithms><graph-algorithms>
What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?
immiKhan
# What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph?

(Asked by: username_0 on 2018-04-26)

I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: Some 3-edge connected graphs don't have three edge-disjoint spanning trees.  Consider G=(V,E) where V={a, b, c, d, e, f} and E={(a, b), (a, c), (a, d), (a, e), (b, f), (c, f), (d, f), (e, f), (b, c), (d, e)}.  I believe it is 3-edge connected, but has six vertices and only ten edges, so cannot have three edge-disjoint spanning trees.  (As each spanning tree would have five distinct edges.)  
> **username_1**: p.s. conditions for a graph to have k edge-disjoint spanning trees appear to be well studied.  see e.g. https://www.math.wvu.edu/~hjlai/Pdf/Catlin_Pdf/Catlin49a.pdf .  

---

## 1 answers

### Answer by username_2 on 2018-04-27. Score: 1

The problem can be reduced to the edge orientation problem. Where if tree width (number of independent trees) is c, we need to orient the edges such that each vertex has an outdegree of *at most* c.

For planar graphs, where c = 3, an O(n log n) algorithm is given by [1]. For general graphs, a simple O(m + n) time algorithm computing a (2c - 1) orientation is shown in [2]. Other algorithms computing exact c orientation are harder including [3] and [4].

[1] Grossi and Lodi. Simple planar graph partition into three forests. Discrete Applied Mathematics, 84:121-132, 1998.

[2] Srinivasa R. Arikati, Anil Maheshwari, and Christos D. Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78:1-16,1997.

[3] Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7:465-497, 1992.

[4] J. C. Picard and M. Queyranne. A network flow soloution to some non-linear 0-1 programming problems, with applications to graph theory. Networks, 12:141-160, 1982.

> **Comments:**
> **username_0**: i am worried if these methods will return spanning trees or not?  
> **username_2**: From c forest decomposition you can trivially get c edge orientation, by rooting each tree in every forest and assign parental edge to a vertex. The other direction gives you only a 2c forest decomposition from c edge orientation. The main problem is the formation of cycles as you compute the forest decomposition.  
> **username_2**: Consider the 2c forests. For each vertex, add its i^{th} out edge in 2i^{th} (or (2i-1)^{th}) forest based on whether the index of its out neighbour is lower (or higher) than itself. As a result, each even indexed forest have only edges pointing from higher index to lower index and vice versa for odd indexed forests. This ensures that no cycles are present in a forest.  
> **username_1**: For c=1, at least, a graph can have |V|-1 edges and a spanning tree, but not have any way of orienting the edges so that each edge has out-degree 1 (which requires |V| edges).  So it might be clearer to say in the answer what reduction you have in mind by when you write "can be reduced to..."  
> **username_2**: Right updated, the out-degree has to be upper bounded by c. It can be less as well but never greater than c.  

---

