Ear decomposition

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): The following result is due to Herbert Robbins (1939): In both cases the number of ears is necessarily equal to the circuit rank of the given graph.

Structures closely related to non-separating ear decompositions of maximal planar graphs, called canonical orderings, are also a standard tool in graph drawing.

An ear is then a directed path where all internal vertices have indegree and outdegree equal to 1.

The following result is due to Eppstein (1992): 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.

The concept of an ear decomposition can be extended from graphs to matroids.

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).

Schmidt (2013b) shows that non-separating ear decompositions may also be constructed in linear time.

Lovász (1985), Maon, Schieber & Vishkin (1986), and Miller & Ramachandran (1986) 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 & Vishkin (1986) proceeds according to the following steps: 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).