Computing the $4$-Edge-Connected Components of a Graph in Linear Time

Abstract

We present the first linear-time algorithm that computes the $4$-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing $4$-edge connectivity. Our results are based on a linear-time algorithm that computes the $3$-edge cuts of a $3$-edge-connected graph $G$, and a linear-time procedure that, given the collection of all $3$-edge cuts, partitions the vertices of $G$ into the $4$-edge-connected components.