An Ear Decomposition ofaGraph

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.