# Are there nice generalizations of SPQR trees to k-connected components for k>3?

I'm curious how one should best understand the connections between the k-connected components when $G$ has minimum cuts of size $k>3$, or perhaps approximate minimum cuts produced by Karger's algorithm. SPQR trees answer this question for 2-connected graphs. And obviously 1-connected graphs are simply a tree of their 2-connected components.

• just a note: Karger's algorithm is not usually thought of as an approximation, but as a Monte Carlo algorithm. It produces the exact min cut with high probability. – Sasho Nikolov Oct 19 '11 at 16:16

Nagamochi and Ibaraki gave an algorithm to find a sparse $k$-node-connected subgraph of a given graph $G$ that contains $O(k n)$ edges where $n$ is the number of nodes in $G$. Not directly relevant perhaps but could be a useful preprocessing step. http://www.springerlink.com/content/u334lr0418n1719u/