Contractions, removals and certifying 3-connectivity in linear time

Abstract

As existence result, it is well known that every 3-connected graph G=(V,E) on more than 4 vertices admits a sequence of contractions and a sequence of removal operations to K_4 such that every intermediate graph in the sequences is 3-connected. We show that both sequences can be computed in linear time, improving the previous best known running time of O(|V|^2) to O(|V|+|E|). This settles also the open question of finding a certifying 3-connectivity test in linear time and extents to certify 3-edge-connectivity in linear time as well.