# Vortices and Graph Decomposition

At the heart of the proof of Seymour and Robertson’s graph minor theorem lies the graph decomposition theorem (commonly referred to as the graph structure theorem), which is the main result of Graph Minors XVI and which Seymour and Robertson describe as “the cornerstone theorem of the [Graph Minors] series”. This theorem states that any graph $G$ with no $H$ minor can be decomposed as into graphs $H_i$ which (almost) constitute “obvious” obstructions to a $H$ minor because there exist surfaces $\Sigma_i$ into which $H_i$ can (almost) be embedded, but $H$ cannot.

Two restatements

More precisely, any $H$-minor-free graph is the result of clique-sums, with join sets of size $\leq\alpha$, of graphs $H_i$ which are $\alpha$-close to admitting a totally bounded $\alpha$-near embedding into a surface $\Sigma$ into which $H$ does not embed.

Note that a tree decomposition is precisely a clique-sum of its parts torsos along their respective torsos intersections. This motivates an even more precise re-statement of the theorem: any $H$-minor-free graph $G$ has a bounded number $\theta$ of apex vertices $Z$, and a rooted tree decomposition $\{V_t \:|\: t \in T\}$ with root $r$ such that

1. its torsos $\{G_t \:|\: t \in T\}$ have vertex subsets $\{A_t \:|\: t \in T\}$ of bounded size $\alpha$ such that $G_t - A_t$ has an $\alpha$-near embedding into a surface $\Sigma_t$ into which $H$ does not embed;
2. these embeddings are totally bounded, i.e. $G_t - A_t$ is obtained from a graph embeddable in $\Sigma_t$ by adding $\leq \alpha$ vortices, each of path-width $\leq \alpha$ (in particular, the path decompositions of the vortices have adhesion $\leq \alpha$, so that this is an indeed a strengthening of $\alpha$-bounded);
3. for adjacent vertices $t, t' \in T$,where $t \in rTt'$ (i.e. $t$ is the parent of $t'$), $V_t \cap V_{t'} \subset A_t$ (i.e. the overlap sits inside the excluded vertices of the parent), and $V_t \cap V_{t'} \subset A_t \cup X_t$ where $X_t$ is either two consecutive parts of a vortex decomposition in $G_t - A_t$, or an embedded clique of size at most 3 (i.e. the overlap almost sits inside the excluded vertices of the child, modulo two controllable special cases);
4. the apex vertices $Z$ sit inside $A_r$.

where $\alpha$ and $\theta$ depend only on the excluded minor $H$.

This last is the form in which Kawarabayashi and Wollan prove the theorem using induction on $|V(G)|$.

What is a vortex?

The original motivation for this structure theorem is the result from Graph Minors V, inspired by the earlier result of Dirac and Duffin characterising $K_4$-minor-free graphs as series-parallel graphs, that states that for $H$ a planar graph, every $H$-minor-free graph has tree-width bounded by some number which is a function of $H$ only. Additional elements, however, need to be introduced to generalize to the case where $H$ is not planar:

1. In particular, drawing on Wagner’s characterisation of $K_5$-minor-free graphs as graphs with tree-decompositions whose parts are either planar or isomorphic to $V_8$ (the graph obtained by joining opposite vertices of a 8-cycle), we allow the building blocks of our tree-decomposition to be arbitrary graphs of bounded genus.
2. Adding a single vertex connected to every vertex to a large grid produces a $K_6$-minor-free graph of large genus; similarly adding $k$ such vertices produces a $K_{k+5}$-minor-free graph or large genus. Hence we really want our building blocks to be arbitrary graphs of bounded genus plus a bounded number of arbitrarily-connected vertices (such vertices are known as apex vertices, from the image of the archetypal single vertex connected to everything on a grid.)
3. There is one more sort of obstruction that must be taken into account, and these are vortices …

A vortex is, roughly speaking, a site of limited complexity where we allow arbitrary violations of bounded genus; they differ from apex vertices in that their complexity is limited not by the size of their vertex set, but by (essentially) their path-width. The archetypal vortex is a planar graph with edges added between every pair of vertices at distance 2 in the boundary of its infinite face—such a graph has no $K_8$ minor (Seese and Wessel, cited in Graph Minors XVI, 45), but cannot be obtained (as a family) by adding a bounded number of apex vertices to graphs of bounded genus.

More precisely, a vortex is a pair $(G, \Omega)$ where $G$ is a graph and $\Omega$ is a cyclic ordering of some $\bar{\Omega} = \{v_1, \dots, v_n\} \subset V(G)$ such that we can find a partition of $G$ into edge-disjoint subgraphs $H_1, \dots, H_n$ satisfying

1. $v_i \in V(H_i)$ and for every edge $e \in G$, we have $latex e \in H_j$ for some $j$.
2. $\{v_j : v \in V(H_j)\} \cap \bar{\Omega} =: \Omega_j$ forms a segment or circular interval of  $\bar{\Omega}$, i.e. if $v_m, v_n \in \Omega_j$, then $v_ k \in \Omega_j$ whenever $m \leq k \leq n$.

(Notational asides: the pair $(G[\bar{\Omega}], \Omega)$ is known as the society of the vortex; $H_1, \dots, H_n$ is a vortex decomposition of $(G, \Omega)$.)

The depth $\alpha$ of a vortex is the maximum of $|V(H_i) \cap V(H_j)|$ over all choices of $i, j$.

One way to build a vortex constructively (which also generalises in a visible way from the archetypal example given above) is to start with a cycle $C$, consider a finite list $\Lambda$ of segments on that circle, add a vertex $v_\gamma$ for each segment $\gamma \in \Lambda$ which is arbitrarily connected to the vertices of $C$, and then add an edge between $v_\gamma$ and $v_{\gamma'}$ if $\gamma \cap \gamma' \neq \varnothing$. If no vertex of $C$ appears in more than $\alpha$ intervals of $\Lambda$, we have a vortex of depth $\alpha$. This construction corresponds to what are called fringes of depth $\alpha$ in Lovász’s survey. If $C$ was the boundary of a face in an embedding of a graph $G$, then we say that the graph resulting from this construction was obtained by adding a vortex of depth $\alpha$ to $G$.

One way to visualize what the graph structure theorem is saying is provided by this awesome picture drawn by Felix Reidl:

(here the things sticking out are apex vertices, and the circular things on the surface that are not holes are vortices.)

References

For definitions of terminology which appears but is not defined here see e.g. Kawarabayashi and Wollan’s article, or the chapter on Minors in Diestel’s book. See also these slides from Daniel Marx, which are good for aiding intuition.