Keywords:-
Article Content:-
Abstract
In 1932 Whitney posed the problem that find an ear decomposition of a graph starting with an ear which is a cycle. In 1939 Robbins proved this result for 2-edge connected graphs. In 1986 Laszlo et al. have given an efficient parallel algorithm for constructing ear decomposition of various types of graphs. In this paper, we survey an ear decomposition of several classes of graphs in particular, covering graphs of posets. We will also discuss in detail about the various types of ear decompositions. In the end, we provide a list of some open problems related to ear decomposition of graphs.
References:-
References
A. N. Bhavale and B. N. Waphare, {it Poset dismantlable by doubly irreducible elements}, Indian Mathematical Society, 88(1--2) (2021), 46--59.
A. N. Bhavale and B. N. Waphare, Enumeration of certain algebraic systems and related results, Ph.D. Thesis, {it (2013)} .
C. Coullard and L. Hellerstein, {it Independence and port oracles for matroids, with an application to computational learning theory}, Combinatorica 16 (2) .(1996), 189--208.
G.A. Dirac, {it Minimally 2-connected graphs}, Journal fur die reine und angewandte Mathematik, 228 (1967), 204--216.
Debarshi Dutta1, Kishore Kothapalli1, G. Ramakrishna, Sai Charan Regunta and Sai Harsh Tondomker, {it An Efficient Ear Decomposition Algorithm}, 15th CTW on graphs and Combinatorial optimization, (2017), 65--68.
David Eppstein, {it Parallel recognition of series parallel graphs}, Information and computation, (98) (1992), 41--55.
S. Even and R.E. Tarjan, {it Computing an st:numbering}, Theoret. Comput. Sci. (2) (1976), 339--344.
Debarshi Dutta, Meher Chaitanya1, Kishore Kothapalli, {it Applications of Ear Decomposition to Efficient Heterogeneous Algorithms for Shortest Path/Cycle Problesm}, IEEE International Symposium on Parallel and Distributed processing workshop and PHD forum C.S, Mathematics (2017), 864--873.
Frank and Andras, {it Conservative weightings and ear decompositions of graphs}, Combinatorica (13) (1993), 65--81.
D.S. Franzblau, {it Ear decomposition with bounds on ear length},Information processing letters (70) (1999), 245--249.
Gross, Jonathan and Jay Yellen, {it Characterization of strongly orientable graphs}, Graph Theory and its Applications (2006), 498-499.
F. Havet and N. Nisse, {it Constrained ear decompositions in graphs and digraphs}, Discrete Mathematics and Theoret. C.S., (21) (4) (2019), (Accepted).
Tibor Jordán, {it Ear-decompositions, minimally connected matroids and rigid graphs}, Egervary research group on combinatorial optimization, Journal of G.T. 105(3), DOI:10.1002/jgt.23046, (2024).
S. Kuller, {it Ear decomposition}, SIGACT News, 20(1) (1989), 128.
A. Kazmiercza and, S. Radhakrsihnan, {it An optimal distributed ear decomposition algorithm with applications to biconnectivity and outerplanarity testing}, IEEE Transaction on Parallel and distributed system, 11(2) (2000), 110--118.
Dimitris Kavvadias, Grammati E. Pantziou, Paul G. Spirakis and Christos D. Zaroliagis, {it Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems}, Mathematical foundation of C.S (1994), 462-472 .
SingLing Lee, Jung-Chun Liu and YuChing Chen, {it An ear-decomposition based approach for survivable routing in WDM networks}, 19th International Conference on AINA 05(1) (2005), 459--464.
A. Lempel, S. Even and I. Cederbaum, {it An algorithm for planarity testing of graphs}, P. Rosenstiehl, Proc. Internat. Syrup. on Theory of Graphs, Rome (1966), Notes in lecture series.
Lovász and László, {it A note on factor-critical graphs}, Studia Sci. Math. Hungar, (7) (1972), 279–-280.
L-Lovasz, {it ear decomposition of matching covered graphs}, Combinatorica (3) (1983), 105--117 .
{it L. Lovasz and M. D. Plummer}, Matching Theory, a book, {it Elsevier Science Publisher}, (1986).
L. Lovász, and Plummer, {it On bicritical graphs}, Colloq. Math. Soc. Jáinos Bolyai (10) (1975), 1051--1079.
Lovansz, Maon Schieber and Vishkin {it Efficient parallel algorithm for constructing ear decomposition of various types}, Theoret. C.S. 47(3) (1986), 277--298.
H. Marcelo, Carvalho and Joseph Cheriyan, {it An O(VE) algorithm for ear decompositions of matching-covered graphs}, ACM Transactions on Algorithms(TALG), 1(2) (2005), 415--423.
H. Marcelo, Carvalho, C. H. C. Little, {it Ear decompositions in combed graphs}, The electronic Journal of Combinatorics (15) (2008), 1077--8926.
H. Marcelo, Carvalho, Claudio L. Lucchesi and U.S.R. Marty, {it Ear decomposition of matching covered graphs}, Relatorio Tecnico IC-98-03 (1998), 151--174.
H. Marcelo, Carvalho, Cláudio L. Lucchesi and U.S.R. Murty, {it Optimal Ear Decompositions of Matching Covered Graphs and Bases for the Matching Lattice}, Journal of Combinatorial Theory Series B 85(1) (2002), 59--93.
Gary Miller and V. Ramachandran, {it Efficient parallel ear decomposition with applications}, MSRT, Berkeley and University of Southern California, Los Angeles, (1986), Unpublished.
U.S.R. Murty, {it Extremal critically connected matroids}, Discrete Math., (8) (1974), 49--58.
Y. Maon, B.Schieber, and U. Vishkin, {it Parallel ear decomposition search(EDS) and st-numbering in graph}, Theoret. C. S.(47) (1986), 34--35.
Charudatt Pachorkar, Meher Chaitanya and Kishore Kothapalli, {it Efficient parallel ear decomposition of graphs with application to betweenness-centrality}, IEEE 23rd International Conference on High Performance Computing (HiPC), Data, and Analytics, (2016).
H.E. Robbins, {it A theorem on graphs with an application to a problem of traffic control}, American Mathematical Monthly, 46(5) (1939), 281--283.
V. Ramachandran, {it Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity}, Synthesis of parallel algorithm, DOI-- cs.utexas.edu, (1992).
B. Szegedy and C. Szegedy, {it Symplectic spaces and ear-decomposition of matroids}, Combinatorica 26(3) (2006), 353--377.
C. Smith, {it Graph Theory and Topology by Geoffrey}, Combinatorica 19(3) (1993), 93--94.
H. Whitney, {it Non-separable and planar graphs}, tran. Amer. Math. Soc. (34) (1932), 339--362.
{it Robin J. Wilson}, Introduction to graph theory, a book, {it fifth edition, Pearson publications, (2010)}
R. Woodroofe, {it Cubical convex ear decompositions},Electron.J. Combinatorics. 16(2) (2007), DOI-- https://doi.org/10.48550/arXiv.0709.2793.
Hailun Zheng, {it Ear Decomposition and Balanced Neighborly Simplicial Manifolds}, Electron. J. Combinatorics. 27(1) (2020), DOI--https://doi.org/10.37236/8341.