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 . The approach is based on computing a special ear decomposition named chain decomposition by one path-generating rule. shows that non-separating ear decompositions may also be constructed in linear time.

, , and provided efficient parallel algorithms