Ear decomposition

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 ${\displaystyle G=(V,E)}$ with ${\displaystyle |E|\ge 2}$ 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 2006).

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 ${\displaystyle G=(V,E)}$ with ${\displaystyle |V|\ge 2}$ 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 (1988), 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 is then 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 2007, Theorem 7.2.2):

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 ${\displaystyle P_i}$, there is a single ear ${\displaystyle P_j}$, ${\displaystyle i>j}$, such that both endpoints of ${\displaystyle P_i}$ lie on ${\displaystyle P_j}$ (Khuller 1989). A nested ear decomposition is a tree ear decomposition such that, within each ear ${\displaystyle P_j}$, the set of pairs of endpoints of other ears ${\displaystyle P_i}$ that lie within ${\displaystyle P_j}$ 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 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.