Ear decomposition

Last updated June 02, 2024

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.

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 HasslerWhitney ( 1932 ):

A graph

G=(V,E)

with

|E|\geq 2

is 2-vertex-connected if and only if it has an open ear decomposition.

The following result is due to HerbertRobbins ( 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)

with

|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

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

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

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

Find a spanning tree of the given graph and choose a root for the tree.
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.
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).
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 ).

Related Research Articles

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E )).

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

<span class="mw-page-title-main">Circuit rank</span> Fewest graph edges whose removal breaks all cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank $r$ is easily computed using the formula

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, a connected graph is $k$ -edge-connected if it remains connected whenever fewer than $k$ edges are removed.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every induced subgraph of $n - 1$ vertices has a perfect matching.

In graph theory, series–parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Clique-sum</span> Gluing graphs at complete subgraphs

In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In graph theory, a Trémaux tree of an undirected graph $is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor-descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.$

In graph theory, Robbins' theorem, named after Herbert Robbins, states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph $G$ , turning it into a directed graph that has a path from every vertex to every other vertex, if and only if $G$ is connected and has no bridge.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.

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, MR 0970192 .
Coullard, Collette R.; Hellerstein, Lisa (1996), "Independence and port oracles for matroids, with an application to computational learning theory", Combinatorica , 16 (2): 189–208, doi:10.1007/BF01844845, MR 1401892, S2CID 1437169 .
Eppstein, D. (1992), "Parallel recognition of series–parallel graphs" (PDF), Information and Computation, 98 (1): 41–55, doi:10.1016/0890-5401(92)90041-D, MR 1161075 .
Frank, András (1993), "Conservative weightings and ear-decompositions of graphs", Combinatorica , 13 (1): 65–81, doi:10.1007/BF01202790, MR 1221177, S2CID 10857300 .
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, MR 2181153 .
Khuller, Samir (1989), "Ear decompositions" (PDF), SIGACT News , 20 (1): 128.
Lovász, László (1972), "A note on factor-critical graphs", Studia Sci. Math. Hung., 7: 279–280, MR 0335371 .
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, ISBN 0-8186-0644-4, S2CID 14879896 .
Maon, Y.; Schieber, B.; Vishkin, U. (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 , MR 0882357 .
Miller, G.; Ramachandran, V. (1986), Efficient parallel ear decomposition with applications, Unpublished manuscript.
Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control" (PDF), American Mathematical Monthly , 46 (5): 281–283, doi:10.2307/2303897, JSTOR 2303897 .
Schmidt, Jens M. (2013a), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, arXiv: 1209.0700 , doi:10.1016/j.ipl.2013.01.016, S2CID 7040381 .
Schmidt, Jens M. (2013b), The Mondshein sequence, arXiv: 1311.0750 , Bibcode:2013arXiv1311.0750S .
Schrijver, Alexander (2003), Combinatorial Optimization. Polyhedra and efficiency. Vol A, Springer-Verlag, ISBN 978-3-540-44389-6 .
Szegedy, Balázs; Szegedy, Christian (2006), "Symplectic spaces and ear-decomposition of matroids", Combinatorica , 26 (3): 353–377, doi:10.1007/s00493-006-0020-3, MR 2246153, S2CID 11578490 .
Whitney, H. (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society , 34 (2): 339–362, doi: 10.1090/S0002-9947-1932-1501641-2 , JSTOR 1989545 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.