View source for Ear decomposition

{{bots|deny=OAbot}}<!-- To prevent re-addition of bogus pmc -->
{{Short description|Partition of graph into sequence of paths}}
[[File:Ear decomposition.png|thumb|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 (graph theory)|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 (graph theory)|degree]] two in ''G''. An '''ear decomposition''' of an undirected graph ''G'' is a [[Partition of a set|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 algorithm]]s. They may also be generalized from graphs to [[matroid]]s.

==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 graph|''k''-vertex-connected]] if the removal of any (''k''&nbsp;&minus;&nbsp;1) vertices leaves a connected subgraph, and [[k-edge-connected graph|''k''-edge-connected]] if the removal of any (''k''&nbsp;&minus;&nbsp;1) edges leaves a connected subgraph.

The following result is due to {{harvs|first=Hassler|last=Whitney|authorlink=Hassler Whitney|year=1932|txt}}:
:A graph <math> G=(V,E)  </math> with <math> |E|\geq 2 </math> is 2-vertex-connected if and only if it has an open ear decomposition.

The following result is due to {{harvs|first=Herbert|last=Robbins|authorlink=Herbert Robbins|year=1939|txt}}:
: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''' {{harv|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 <math> G=(V,E)  </math> with <math> |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 {{harvtxt|Cheriyan|Maheshwari|1988}}, but as {{harvtxt|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 graph]]s. 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 {{harv|Bang-Jensen|Gutin|2007|loc=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]]. {{harvs|first=László|last=Lovász|authorlink=László Lovász|year=1972|txt}} found that:
:A graph ''G'' is factor-critical if and only if ''G'' has an odd ear decomposition.
More generally, a result of {{harvtxt|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> P_i </math>, there is a single ear <math> P_j </math>, <math> i>j </math>, such that both endpoints of <math> P_i </math> lie on <math> P_j </math> {{harv|Khuller|1989}}. A ''nested'' ear decomposition is a tree ear decomposition such that, within each ear <math> P_j </math>, the set of pairs of endpoints of other ears <math> P_i </math> that lie within <math> 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 {{harvs|first=David|last=Eppstein|authorlink=David Eppstein|year=1992|txt}}:
: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 [[matroid]]s. 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 {{harv|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 {{harvtxt|Schmidt|2013a}}. The approach is based on computing a special ear decomposition named [[chain decomposition (undirected graphs)|chain decomposition]] by one path-generating rule. {{harvtxt|Schmidt|2013b}} shows that non-separating ear decompositions may also be constructed in linear time.

{{harvtxt|Lovász|1985}}, {{harvtxt|Maon|Schieber|Vishkin|1986}}, and {{harvtxt|Miller|Ramachandran|1986}} provided efficient [[parallel algorithm]]s for constructing ear decompositions of various types. For instance, to find an ear decomposition of a 2-edge-connected graph, the algorithm of {{harvtxt|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 [[matroid oracle|independence oracle]] for the matroid {{harv|Coullard|Hellerstein|1996}}.

==References==
{{refbegin|colwidth=30em}}
*{{citation
 | last1 = Bang-Jensen | first1 = Jørgen
 | last2 = Gutin | first2 = Gregory
 | contribution = 7.2 Ear Decompositions
 | pages = 349–352
 | publisher = Springer-Verlag
 | title = Digraphs: Theory, Algorithms and Applications
 | year = 2007}}
*{{citation
 | last1 = Cheriyan | first1 = J.
 | last2 = Maheshwari | first2 = S. N.
 | doi = 10.1016/0196-6774(88)90015-6
 | issue = 4
 | journal = Journal of Algorithms
 | mr = 970192
 | pages = 507–537
 | title = Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
 | volume = 9
 | year = 1988}}.
*{{citation
 | last1 = Coullard | first1 = Collette R. | author1-link = Collette Coullard
 | last2 = Hellerstein | first2 = Lisa
 | doi = 10.1007/BF01844845
 | issue = 2
 | journal = [[Combinatorica]]
 | mr = 1401892
 | pages = 189–208
 | title = Independence and port oracles for matroids, with an application to computational learning theory
 | volume = 16
 | year = 1996| s2cid = 1437169 }}.
*{{citation
 | last = Eppstein| first = D.  | authorlink = David Eppstein
 | journal = Information and Computation
 | pages = 41–55
 | title = Parallel recognition of series–parallel graphs
 | volume = 98
 | issue = 1
 | doi = 10.1016/0890-5401(92)90041-D
 | mr = 1161075
 | year = 1992| url = http://www.ics.uci.edu/~eppstein/pubs/Epp-IC-92.pdf
 }}.
*{{citation
 | last = Frank | first = András | author-link = András Frank
 | doi = 10.1007/BF01202790
 | issue = 1
 | journal = [[Combinatorica]]
 | mr = 1221177
 | pages = 65–81
 | title = Conservative weightings and ear-decompositions of graphs
 | volume = 13
 | year = 1993| s2cid = 10857300 }}.
*{{citation
 | last1 = Gross | first1 = Jonathan L.
 | last2 = Yellen | first2 = Jay
 | contribution = Characterization of strongly orientable graphs
 | edition = 2nd
 | isbn = 978-1-58488-505-4
 | mr = 2181153
 | pages = 498–499
 | publisher = Chapman &Hall/CRC, Boca Raton, FL
 | series = Discrete Mathematics and its Applications (Boca Raton)
 | title = Graph theory and its applications
 | url = https://books.google.com/books?id=unEloQ_sYmkC&pg=PA498
 | year = 2006}}.
*{{citation
 | last = Khuller | first = Samir
 | title = Ear decompositions
 | journal = [[SIGACT News]]
 | url = http://portalparts.acm.org/70000/65780/bm/backmatter.pdf
 | page = 128
 | year = 1989
 | volume = 20
 | issue = 1}}.
*{{citation
 | last = Lovász | first = László | authorlink = László Lovász
 | journal = Studia Sci. Math. Hung. 
 | mr = 0335371
 | pages = 279–280
 | title = A note on factor-critical graphs
 | volume = 7
 | year = 1972}}.
*{{citation
 | last = Lovász | first = László
 | contribution = Computing ears and branchings in parallel
 | doi = 10.1109/SFCS.1985.16
 | pages = 464–467
 | title = [[Symposium on Foundations of Computer Science|26th Annual Symposium on Foundations of Computer Science]]
 | year = 1985| isbn = 0-8186-0644-4
 | s2cid = 14879896
 }}.
*{{citation
 | last1 = Maon | first1 = Y.
 | last2 = Schieber | first2 = B. 
 | last3 = Vishkin | first3 = U. | author3-link = Uzi Vishkin
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | title = Parallel ear decomposition search (EDS) and ST-numbering in graphs
 | volume = 47
 | issue = 3
 | mr = 0882357
 | doi = 10.1016/0304-3975(86)90153-2
 | year = 1986 | pages=277–298| doi-access = free
 }}.
*{{citation
 | last1 = Miller | first1 = G. | author1-link = Gary Miller (computer scientist)
 | last2 = Ramachandran | first2 = V.
 | title = Efficient parallel ear decomposition with applications
 | publisher = Unpublished manuscript
 | year = 1986}}.
*{{citation
 | last = Robbins | first = H. E. | authorlink = Herbert Robbins
 | journal = [[American Mathematical Monthly]]
 | pages = 281–283
 | title = A theorem on graphs, with an application to a problem of traffic control
 | volume = 46
 | year = 1939
 | issue = 5 | doi=10.2307/2303897| jstor = 2303897 | url = http://dml.cz/bitstream/handle/10338.dmlcz/101517/CzechMathJ_28-1978-1_10.pdf
 }}.
*{{citation
 | last1 = Schmidt| first1 = Jens M.
 | journal = Information Processing Letters
 | title = A Simple Test on 2-Vertex- and 2-Edge-Connectivity
 | year = 2013a
 | pages = 241–244
 | volume = 113
 | number = 7
 | doi = 10.1016/j.ipl.2013.01.016| arxiv = 1209.0700
 | s2cid = 7040381
 }}.
*{{citation
 | last = Schmidt | first = Jens M.
 | arxiv = 1311.0750
 | title = The Mondshein sequence
 | year = 2013b| bibcode = 2013arXiv1311.0750S}}.
*{{citation
 | last1 = Schrijver | first1 = Alexander | authorlink = Alexander Schrijver
 | title = Combinatorial Optimization. Polyhedra and efficiency. Vol A
 | year = 2003
 | publisher = Springer-Verlag
 | isbn = 978-3-540-44389-6}}.
*{{citation
 | last1 = Szegedy | first1 = Balázs | author1-link = Balázs Szegedy
 | last2 = Szegedy | first2 = Christian
 | doi = 10.1007/s00493-006-0020-3
 | issue = 3
 | journal = [[Combinatorica]]
 | mr = 2246153
 | pages = 353–377
 | title = Symplectic spaces and ear-decomposition of matroids
 | volume = 26
 | year = 2006| s2cid = 11578490 }}.
*{{citation
 | last = Whitney | first = H. | authorlink = Hassler Whitney
 | doi = 10.1090/S0002-9947-1932-1501641-2
 | journal = [[Transactions of the American Mathematical Society]]
 | jstor = 1989545
 | pages = 339–362
 | title = Non-separable and planar graphs
 | volume = 34
 | year = 1932 | issue = 2 | doi-access = free
 }}.
{{refend}}

{{Authority control}}

[[Category:Graph theory objects]]
[[Category:Matroid theory]]