Ear decomposition

Short description: Partition of graph into sequence of paths

An example of an ear decomposition of a graph containing 3 ears.

In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.

Ear decompositions may be used to characterize several important graph classes, and as part of efficient graph algorithms. They may also be generalized from graphs to matroids.

Characterizing graph classes

Several important classes of graphs may be characterized as the graphs having certain types of ear decompositions.

Graph connectivity

A graph is k-vertex-connected if the removal of any (k − 1) vertices leaves a connected subgraph, and k-edge-connected if the removal of any (k − 1) edges leaves a connected subgraph.

The following result is due to Hassler Whitney (1932):

A graph [math]\displaystyle{ G=(V,E) }[/math] with [math]\displaystyle{ |E|\geq 2 }[/math] is 2-vertex-connected if and only if it has an open ear decomposition.

The following result is due to Herbert Robbins (1939):

A graph is 2-edge-connected if and only if it has an ear decomposition.

In both cases the number of ears is necessarily equal to the circuit rank of the given graph. Robbins introduced the ear decomposition of 2-edge-connected graphs as a tool for proving the Robbins theorem, that these are exactly the graphs that may be given a strongly connected orientation. Because of the pioneering work of Whitney and Robbins on ear decompositions, an ear decomposition is sometimes also called a Whitney–Robbins synthesis (Gross Yellen).

A non-separating ear decomposition is an open ear decomposition such that, for each vertex v with only one exception, v has a neighbor whose first appearance in the decomposition is in a later ear than the first appearance of v. This type of ear decomposition may be used to generalize Whitney's result:

A graph [math]\displaystyle{ G=(V,E) }[/math] with [math]\displaystyle{ |V|\geq 2 }[/math] is 3-vertex-connected if and only if G has a non-separating ear decomposition.

If such a decomposition exists, it can be chosen with respect to a particular edge uv of G in such a way that u is in the first ear, v is the new vertex in the last ear with more than one edge, and uv is a single-edge ear. This result was first stated explicitly by (Cheriyan Maheshwari), but as (Schmidt 2013b) describes, it is equivalent to a result in the 1971 Ph.D. thesis of Lee Mondshein. Structures closely related to non-separating ear decompositions of maximal planar graphs, called canonical orderings, are also a standard tool in graph drawing.

Strong connectivity of directed graphs

The above definitions can also be applied to directed graphs. An ear would then be a directed path where all internal vertices have indegree and outdegree equal to 1. A directed graph is strongly connected if it contains a directed path from every vertex to every other vertex. Then we have the following theorem (Bang-Jensen Gutin):

A directed graph is strongly connected if and only if it has an ear decomposition.

Factor-critical graphs

An ear decomposition is odd if each of its ears uses an odd number of edges. A factor-critical graph is a graph with an odd number of vertices, such that for each vertex v, if v is removed from the graph then the remaining vertices have a perfect matching. László Lovász (1972) found that:

A graph G is factor-critical if and only if G has an odd ear decomposition.

More generally, a result of (Frank 1993) makes it possible to find in any graph G the ear decomposition with the fewest even ears.

Series–parallel graphs

A tree ear decomposition is a proper ear decomposition in which the first ear is a single edge and for each subsequent ear [math]\displaystyle{ P_i }[/math], there is a single ear [math]\displaystyle{ P_j }[/math], [math]\displaystyle{ i\gt j }[/math], such that both endpoints of [math]\displaystyle{ P_i }[/math] lie on [math]\displaystyle{ P_j }[/math] (Khuller 1989). A nested ear decomposition is a tree ear decomposition such that, within each ear [math]\displaystyle{ P_j }[/math], the set of pairs of endpoints of other ears [math]\displaystyle{ P_i }[/math] that lie within [math]\displaystyle{ P_j }[/math] form a set of nested intervals. A series–parallel graph is a graph with two designated terminals s and t that can be formed recursively by combining smaller series–parallel graphs in one of two ways: series composition (identifying one terminal from one smaller graph with one terminal from the other smaller graph, and keeping the other two terminals as the terminals of the combined graph) and parallel composition (identifying both pairs of terminals from the two smaller graphs).

The following result is due to David Eppstein (1992):

A 2-vertex-connected graph is series–parallel if and only if it has a nested ear decomposition.

Moreover, any open ear decomposition of a 2-vertex-connected series–parallel graph must be nested. The result may be extended to series–parallel graphs that are not 2-vertex-connected by using open ear decompositions that start with a path between the two terminals.

Matroids

The concept of an ear decomposition can be extended from graphs to matroids. An ear decomposition of a matroid is defined to be a sequence of circuits of the matroid, with two properties:

• each circuit in the sequence has a nonempty intersection with the previous circuits, and
• each circuit in the sequence remains a circuit even if all previous circuits in the sequence are contracted.

When applied to the graphic matroid of a graph G, this definition of an ear decomposition coincides with the definition of a proper ear decomposition of G: improper decompositions are excluded by the requirement that each circuit include at least one edge that also belongs to previous circuits. Using this definition, a matroid may be defined as factor-critical when it has an ear decomposition in which each circuit in the sequence has an odd number of new elements (Szegedy Szegedy).

Algorithms

On classical computers, ear decompositions of 2-edge-connected graphs and open ear decompositions of 2-vertex-connected graphs may be found by greedy algorithms that find each ear one at a time. A simple greedy approach that computes at the same time ear decompositions, open ear decompositions, st-numberings and -orientations in linear time (if exist) is given in (Schmidt 2013a). The approach is based on computing a special ear decomposition named chain decomposition by one path-generating rule. (Schmidt 2013b) shows that non-separating ear decompositions may also be constructed in linear time.

(Lovász 1985), (Maon Schieber), and (Miller Ramachandran) provided efficient parallel algorithms for constructing ear decompositions of various types. For instance, to find an ear decomposition of a 2-edge-connected graph, the algorithm of (Maon Schieber) proceeds according to the following steps:

1. Find a spanning tree of the given graph and choose a root for the tree.
2. Determine, for each edge uv that is not part of the tree, the distance between the root and the lowest common ancestor of u and v.
3. For each edge uv that is part of the tree, find the corresponding "master edge", a non-tree edge wx such that the cycle formed by adding wx to the tree passes through uv and such that, among such edges, w and x have a lowest common ancestor that is as close to the root as possible (with ties broken by edge identifiers).
4. Form an ear for each non-tree edge, consisting of it and the tree edges for which it is the master, and order the ears by their master edges' distance from the root (with the same tie-breaking rule).

These algorithms may be used as subroutines for other problems including testing connectivity, recognizing series–parallel graphs, and constructing st-numberings of graphs (an important subroutine in planarity testing).

An ear decomposition of a given matroid, with the additional constraint that every ear contains the same fixed element of the matroid, may be found in polynomial time given access to an independence oracle for the matroid (Coullard Hellerstein).

References

• Bang-Jensen, Jørgen; Gutin, Gregory (2007), "7.2 Ear Decompositions", Digraphs: Theory, Algorithms and Applications, Springer-Verlag, pp. 349–352 
• Cheriyan, J.; Maheshwari, S. N. (1988), "Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs", Journal of Algorithms 9 (4): 507–537, doi:10.1016/0196-6774(88)90015-6 .
• "Independence and port oracles for matroids, with an application to computational learning theory", Combinatorica 16 (2): 189–208, 1996, doi:10.1007/BF01844845 .
• "Parallel recognition of series–parallel graphs", Information and Computation 98 (1): 41–55, 1992, doi:10.1016/0890-5401(92)90041-D, http://www.ics.uci.edu/~eppstein/pubs/Epp-IC-92.pdf .
• "Conservative weightings and ear-decompositions of graphs", Combinatorica 13 (1): 65–81, 1993, doi:10.1007/BF01202790 .
• Gross, Jonathan L.; Yellen, Jay (2006), "Characterization of strongly orientable graphs", Graph theory and its applications, Discrete Mathematics and its Applications (Boca Raton) (2nd ed.), Chapman &Hall/CRC, Boca Raton, FL, pp. 498–499, ISBN 978-1-58488-505-4, https://books.google.com/books?id=unEloQ_sYmkC&pg=PA498 .
• Khuller, Samir (1989), "Ear decompositions", SIGACT News 20 (1): 128, http://portalparts.acm.org/70000/65780/bm/backmatter.pdf .
• "A note on factor-critical graphs", Studia Sci. Math. Hung. 7: 279–280, 1972 .
• Lovász, László (1985), "Computing ears and branchings in parallel", 26th Annual Symposium on Foundations of Computer Science, pp. 464–467, doi:10.1109/SFCS.1985.16 .
• Maon, Y.; Schieber, B. (1986), "Parallel ear decomposition search (EDS) and ST-numbering in graphs", Theoretical Computer Science 47 (3): 277–298, doi:10.1016/0304-3975(86)90153-2 .
• Efficient parallel ear decomposition with applications, Unpublished manuscript, 1986 .
• "A theorem on graphs, with an application to a problem of traffic control", American Mathematical Monthly 46 (5): 281–283, 1939, doi:10.2307/2303897, http://dml.cz/bitstream/handle/10338.dmlcz/101517/CzechMathJ_28-1978-1_10.pdf .
• Schmidt, Jens M. (2013a), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters 113 (7): 241–244, doi:10.1016/j.ipl.2013.01.016 .
• Schmidt, Jens M. (2013b), The Mondshein sequence, Bibcode: 2013arXiv1311.0750S .
• Combinatorial Optimization. Polyhedra and efficiency. Vol A, Springer-Verlag, 2003, ISBN 978-3-540-44389-6 .
• "Symplectic spaces and ear-decomposition of matroids", Combinatorica 26 (3): 353–377, 2006, doi:10.1007/s00493-006-0020-3 .
• "Non-separable and planar graphs", Transactions of the American Mathematical Society 34 (2): 339–362, 1932, doi:10.1090/S0002-9947-1932-1501641-2 .