Canonical decompositions of 3-connected graphs

Every graph is the disjoint union of its connected components, and every connected graph can be decomposed into 2-connected components (and complete graphs on one or two vertices) along a block-cut tree. An interesting feature of these two types of decompositions is that they are unique, and in particular they are also “canonical”, meaning that the image of any part of the decomposition by any automorphism of the graph is again a part of the decomposition. This is a crucial property when analyzing decompositions of vertex-transitive finite connected graphs, such as finite Cayley graphs, as it implies that the decomposition has only one part.

Is it possible to extend the two canonical decompositions above to higher connectivity? It was proved by Tutte in the early sixties that 2-connected graphs can be decomposed canonically into 3-connected components, cycles, and $K_2$’s along separators of size 2.

The next challenge is to obtain a similar type of decomposition for 3-connected graphs into 4-connected components or special parts, but a number of significant obstacles suddently appear, even if we do not require a canonical decomposition. In particular, examples such as toroidal or infinite hexagonal grids show that 4-connectivity of the parts is probably too much to ask for, and quasi-4-connectivity should be required instead (quasi-4-connected means 3-connected and every separator of size 3 is the neighborhood of a vertex of degee 3). It was not until 2016 that a decomposition of this type was obtained, by Grohe, but the decomposition was not canonical and it only applied to finite graphs.

The main result of the present paper is a canonical decomposition of finite or infinite 3-connected graphs into quasi-4-connected components or special parts (wheels or thickened $K_{3,m}$'s), obtained by giving an explicit description of the parts. One of the novelties is that the graphs are not decomposed along vertex separators as in the previous decompositions, but along “mixed separators”, consisting of vertices and edges. While decomposing along vertex separators gives rise to tree-decompositions, decomposing along these mixed separators gives rise to a new type of so-called “mixed-tree-decompositions”, which are related both to tree-decompositions and tree-cut-decompositions.

The authors provide a number of immediate applications, in particular on Cayley graphs: all vertex-transitive finite connected graphs are either essentially 4-connected, cycles, or complete graphs on at most four vertices. It is very likely that further applications will follow.