Generating 3-vertex connected spanning subgraphs

In this paper we present an algorithm to generate all minimal 3-vertex connected spanning subgraphs of an undirected graph with nn vertices and mm edges in incremental polynomial time, i.e., for every KK we can generate KK (or all) minimal 3-vertex connected spanning subgraphs of a given graph in O(K2log(K)m2+K2m3)O(K2log(K)m2+K2m3) time, where nn and mm are the number of vertices and edges of the input graph, respectively. This is an improvement over what was previously available and is the same as the best known running time for generating 2-vertex connected spanning subgraphs. Our result is obtained by applying the decomposition theory of 2-vertex connected graphs to the graphs obtained from minimal 3-vertex connected graphs by removing a single edge.