We can use such a decomposition in a proof of the Euler formula for polyhedra:

The graph G of a polyhedron is two-edge-connected, since if we remove an edge e we can still connect its endpoints by a path around the other side of one of the two faces of G containing e.Ear decompositions have been especially useful in the design of parallel algorithms, since they are easier to find in parallel than are other structural decompositions of graphs such as depth first search trees. For an example of this see my work on recognizing series parallel graphs.Find an ear decomposition of G, and consider the process of forming G by adding ears one at a time starting from a single vertex. Initially there is one vertex, one face, and no edges. Each new ear forms a path connecting two vertices on the boundary of a face, splitting the face in two; the path has one more edge than it has vertices. So if the ear has

kedges, its addition increases V byk-1, E byk, and F by 1, and the result follows by induction on the number of ears.

Proofs of Euler's Formula.

From the Geometry Junkyard,
computational
and recreational geometry pointers.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Semi-automatically filtered from a common source file. Last update: .