Ear decomposition (original) (raw)

From Wikipedia, the free encyclopedia

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

[edit]

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

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 G = ( V , E ) {\displaystyle G=(V,E)} {\displaystyle G=(V,E)} with | E | ≥ 2 {\displaystyle |E|\geq 2} {\displaystyle |E|\geq 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 G = ( V , E ) {\displaystyle G=(V,E)} {\displaystyle G=(V,E)} with | V | ≥ 2 {\displaystyle |V|\geq 2} {\displaystyle |V|\geq 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

[edit]

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 2007, Theorem 7.2.2):

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

Factor-critical graphs

[edit]

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

[edit]

A tree ear decomposition is a proper ear decomposition in which the first ear is a single edge and for each subsequent ear P i {\displaystyle P_{i}} {\displaystyle P_{i}}, there is a single ear P j {\displaystyle P_{j}} {\displaystyle P_{j}}, i > j {\displaystyle i>j} {\displaystyle i>j}, such that both endpoints of P i {\displaystyle P_{i}} {\displaystyle P_{i}} lie on P j {\displaystyle P_{j}} {\displaystyle P_{j}} (Khuller 1989). A nested ear decomposition is a tree ear decomposition such that, within each ear P j {\displaystyle P_{j}} {\displaystyle P_{j}}, the set of pairs of endpoints of other ears P i {\displaystyle P_{i}} {\displaystyle P_{i}} that lie within P j {\displaystyle P_{j}} {\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 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.

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:

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

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 & 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:

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