A new algorithm to test an arbitrary graph for 3-edge-connectivity is proposed,
implemented and tested. It is a modication of the classic linear algorithm of
Hopcroft and Tarjan for dividing a graph into 3-connected components. The algo-
rithm uses three depth-rst searches to locate separation pairs. It runs in time
O(m + n), where m is the number of edges and n is the number of vertices in the
graph. Testing was done on simple graphs and Feynman diagrams. The results show
good agreement with the time complexity analysis, validating the algorithm design
and implementation.
