Quickly Excluding an Annotated Planar Graph

Notice that by our definition, a minor-model of a red $(k\times k)$-grid does not have to be a minimal minor-model of a $(k\times k)$-grid. That is, we explicitly allow for the red vertices to be connected to the grid in the form of dangling paths. See Figure 2 for an example. This notion of “red minor” has already been studied by a variety of authors, often under the name of “rooted minors”. However, depending on the context, rooted minors are sometimes required to respect a fixed bijection between the coloured vertices of $(G,R_G)$ and the coloured vertices of $(H,R_H)$. For better distinction between the two concepts, we say that $(H,R_H)$ is a red minor of $(G,R_G)$ if there exists a minor-model ${\{G_v\}}_{v\in V(H)}$ of $H$ in $G$ such that $R_G\cap V(G_v)\ne \mathrm{\varnothing }$ for all $v\in R_H$. This is in reference to the term “colorful minor” introduced by Protopapas, Thilikos, and Wiederrecht [45] which allows for vertices to carry more than one colour.

The work of Protopapas et al. provides several structural theorems for annotated graphs excluding fundamental patterns, including a variant of Theorem 1 with exponential bounds, a structure theorem for excluding a red clique, and one for the exclusion of an outer red grid, i.e. an annotated graph $(G,R)$ where $G$ is a $(k\times k)$-grid for some $k$ and $R$ is the vertex set of its first column. A small outer red grid can be found in Figure 1. While Protopapas et al. investigate a variant of the outer red grid with more than one colour, the first result describing the structure of graphs excluding an outer red grid is due to Marx, Seymour, and Wollan [39]. It was later observed by Hodor, La, Micek, and Rambaud [31] that the result of Marx et al. provides a min-max characterisation of a type of modulation parameter that falls into a family of structural parametrisations started by Bulian and Dawar with their introduction of elimination distance [4, 5].

The treewidth of a graph $G$, denoted by $\mathrm{𝗍𝗐}(G)$, is the smallest integer $k$ such that $G$ has a tree-decomposition of width at most $k$.

Let $G$ be a graph and $X\subseteq V(G)$ be a vertex set. The torso of $G$ at $X$ is the graph $G_X$ obtained from $G[X]$ by turning the set $N_G(J)\subseteq X$ into a clique for every component $J$ of $G-X$.

The torso treewidth of an annotated graph $(G,R)$, denoted by $\mathrm{𝗍𝗍𝗐}(G,R)$, is the smallest integer $k$ such that there exists a set $X\subseteq V(G)$ with $R\subseteq X$ and $\mathrm{𝗍𝗐}(G_X)\le k$.

As observed by Hodor et al. [31], the result of Marx et al. [39] implies that every annotated graph with large torso treewidth contains a big outer red grid as a red minor. One may observe a hierarchy of parameters as follows:

1. 1.

   The Grid Theorem of Robertson and Seymour explains the structure of graphs excluding a planar graph as minor,

2. 2.

   the theorem of Marx et al. explains the structure of annotated graphs excluding a planar graph with a single red face as a red minor, and

3. 3.

   Theorem 1 explains the structure of an annotated graph excluding an arbitrary annotated planar graph as a red minor.

Among these Theorem 1 is the most general, as it in particular implies Robertson and Seymour’s Grid Theorem, since the treewidth of any graph $G$ equals the bidimensionality of $(G,V(G))$. Moreover, due to torso treewidth being sandwiched between treewidth and bidimensionality, in annotated graphs where all vertices are red all three parameters collapse into one.

A graph $H$ is said to be an apex graph if there exists some vertex $v\in V(H)$ such that $H-v$ is planar. Apex graphs themselves are very close to planar graphs. However, apex-minor-free graph classes generalise planar graphs and any graph class of bounded Euler-genus. Graphs in these classes allow for a range of interesting algorithmic results [22, 21, 30, 11, 13, 12, 24, 36]. Many of these algorithmic applications are in the realm of approximation algorithms. Indeed, as proposed by Eppstein [22, 21] and later built upon by Grohe [30] and Demain and Hajiaghayi [11], apex-minor-free graphs have bounded “local treewidth” which allows for an application of a variant of Baker’s Technique [1], facilitating the design of polynomial approximation schemes (PTAS) for problems which are hard to approximate on general graphs.

Indeed, while the structure theorem for apex-minor-free graphs was known in the community, the first written proof for it can be found in the appendix of a paper by Dvořák and Thomas [20] on approximating list colourings. Since their proof builds on the original results of Robertson and Seymour, they do not come with any estimates on the bounds for the constants describing the running times of their algorithm. This issue is shared among many of the applications mentioned above and gets explicitly mentioned by Grohe [30]. Our result shows that, in the case of apex-minor-free graphs, it is possible to give explicit polynomials bounds directly through the use of modern graph minor theory.

By interpreting the red vertices in each step of the proof as the combined neighbourhood of the apex vertices produced, our techniques show that one may either find any fixed apex graph as a minor, or create a region in the surface-embedded part which avoids the neighbourhood of all apex vertices. This yields a polynomial version of Dvořák and Thomas’ local structure theorem. The term “local” here refers to the fact that the structure theorem is stated with respect to a large wall. A local version of Theorem 1 can be found in the form of Theorem 5.1 in the full version of our article.

We say that a graph $G$ containing a wall $W\subseteq G$ has a weak $k$-near embedding centred at $W$ in a surface $\mathrm{\Sigma }$ if there exists $A\subseteq V(G)$ with $|A|\le k$, such that $G-A=G_0\cup G_1\cup \mathrm{\cdots }\cup G_{\mathrm{\ell }}\cup J_1\cup \mathrm{\cdots }\cup J_h$, $\mathrm{\ell }\le k$ and $h\in \mathbb{N}$, such that $G_0$ has an embedding into $\mathrm{\Sigma }$ with $\mathrm{\ell }+h$ faces $F_i$ where

• $\mathrm{■}$

  the graphs $G_i-V(G_0)$ and $J_j-V(G_0)$ are vertex-disjoint for all $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$ and $j\in \{1,\mathrm{\dots },h\}$,

• $\mathrm{■}$

  for all $j\in \{1,\mathrm{\dots },h\}$, the face $F_j$ contains a set $S_j$ of at most three vertices such that all $S_j$’s are pairwise disjoint and $V(J_j)\cap V(F_j)=S_j=V(J_j)\cap V(G_0)$, and such that, if $|S_j|=3$, $V(F_j)=S_j$ and if $|S_j|=2$ then the vertices of $S_j$ are adjacent on $F_j$,

• $\mathrm{■}$

  for all $i\in \{h+1,\mathrm{\dots },h+\mathrm{\ell }\}$, $V(G_0)\cap V(G_i)=V(F_i)$, for $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$, the $G_i$’s are pairwise vertex-disjoint and each such $G_i$ has a path-decomposition $(P_i,{\beta }_i)$ of adhesion at most $k$ such that $V(P_i)=V(F_i)$, the vertices of $P_i$ appear in agreement to their cyclic ordering on the boundary of $F_i$, and $v\in {\beta }_i(v)$, for all $v\in V(F_i)$, and

• $\mathrm{■}$

  $W$ is vertex-disjoint from ${\bigcup }_{i=1}^{\mathrm{\ell }}{G}_i$ and for each $j\in \{1,\mathrm{\dots },h\}$, $J_j$ contains at most one vertex of degree $3$ from $W$.

The set $A$ is called the apex set, the graphs $G_i$ are called the vortices, and the sets $V(G_i)\setminus V(F_i)$ are the interiors of the vortices and the graphs $J_j$ are called the flaps.

It is important to stress that Theorem 2 is a consequence of our methods and the lemmas we develop along the way, not directly of the main statements that eventually give rise to Theorem 1.

Moreover, the reason why we only state the local variant of Dvořák and Thomas’ structure theorem for apex-minor-free graphs here is three-fold.

First, almost all Robertson-Seymour-style structure theorems are proven in this way: One first proves a local variant with respect to a wall or “tangle” and then applies a well-known technique to turn the local structure theorem into a global one based on tree decompositions – see Section 6 of the fullversion of our article for this local-to-global step proving Theorem 1. Novel arguments are usually only necessary to prove the local theorems, with the local-to-global step seeing few innovations over the years.

Second, while the global theorems are better known, the local structure theorems tend to be the more important ones. Robertson and Seymour point this out in their own proof of the Graph Minor Structure Theorem [52], declaring the global structure theorem to be a “red herring”.

Finally, the third reason is of a technical nature. While the process of going from local to global is by now routine, its approximate nature comes with the drawback of introducing additional vertices to the apex set. Dvořák and Thomas have laid out a technique to capture the neighbourhoods of these new apices inside additional vortices [20] (see also [41] for a more recent take on the technique). However, this step introduces additional technicalities which we believe to be outside the scope of this paper and so we leave this part to the interested readers.

As described above, the notion of bidimensionality for annotated vertex sets may be seen as a vast structural generalisation of the face-cover-number of annotated vertex sets in planar graphs. A wide range of problems defined on annotated graphs are known to be tractable on planar annotated graphs whenever the face-cover-number is bounded. Interesting problems that fall into this framework are the Multiway Cut problem [42] and the problem of counting perfect matchings with defects [8]. Even the Disjoint Paths problem on planar graphs exhibits strong algorithmic properties when the face-cover-number of its terminals is considered [40, 58]. A leading question in this newly arising theory of structural parameters for annotated graphs is the following:

Given an NP-hard computational problem $\mathrm{\Pi }$ defined on annotated graphs which is tractable on planar graphs where the red vertices can be covered by a constant number of faces, which proper red-minor-closed classes of annotated graphs admit polynomial-time algorithms for $\mathrm{\Pi }$?

A prime example of such a behaviour is the Steiner Tree problem [34]. Recently, Steiner Tree has become the subject of a streamlined investigation into the power of structural parameters for annotated graphs. Jansen and Swennenhuis [32] showed that Steiner Tree is fixed-parameter tractable when parameterized by the torso treewidth of the annotated input instance. Groenland, Nederlof, and Koana [29] have shown that excluding a red $K_4$-minor also gives rise to a class of polynomially solvable instances of Steiner Tree. Notice that, due to the structural result of Marx et. al, annotated graphs excluding a red $K_4$-minor may have unbounded torso treewidth, however, since the red $K_4$ is a minor of the red $(3\times 3)$-grid, excluding $K_4$ as a red minor implies bounded bidimensionality. Given that Steiner Tree is NP-hard on the class of all annotated planar graphs [26], it follows that it is also NP-hard on all red-minor-closed classes of unbounded bidimensionality. However, there is strong evidence, that bidimensionality might be what precisely delineates the tractability of Steiner Tree in red-minor-closed classes.

Are there computable functions $f$ and $g$ such that Steiner Tree can be solved in time $f(k)n^{g(k)}$ on annotated graphs of bidimensionality at most $k$?

Due to a result of Krisfaludi-Bak, Nederlof, and Leeuwen [34], the dependency on $k$ in the exponent of $n$ in Section 1.2 is unavoidable assuming the Exponential Time Hypothesis, a feature that is shared by many problems of the same flavour. Key towards providing a positive answer to Section 1.2 is a full understanding of the structural properties of annotated graphs of low bidimensionality, which is one of the main motivations behind our work. Indeed, in case the answer to Section 1.2 is “yes”, the functions $f$ and $g$ are likely to depend on the function from Theorem 1, further emphasising the need for constructive and good bounds.

Apart from its focal role in understanding structural parameters for annotated graphs, bidimensionality has also been observed to be a key player in recent extensions of Courcelle’s Theorem [7]. Courcelle’s Theorem states that the model checking problem for MSO₂-formulas – naively speaking, formulas where one is allowed to quantify over vertex sets and edge sets – is fixed-parameter tractable on graphs of bounded treewidth. In a vast generalisation of this result, Sau, Stamoulis, and Thilikos [53] have shown that in the space of minor-closed graph classes one may extend the applicability of Courcelle’s Theorem beyond the scope of graphs of bounded treewidth by restricting the quantifications allowed in the formulas to vertex sets of bounded bidimensionality and certain disjoint-paths queries. Strengthenings of this “meta-algorithmic” result have been proven for annotated graphs of bounded torso treewidth and annotated graphs excluding a red clique minor by Protopapas, Thilikos, and Wiederrecht [45].

As manifested in Theorem 2, structure theory for excluding red minors in annotated graphs has direct implications for the exclusion of certain types of graphs $H$ in the setting of graph minors. Let $𝒳$ be a minor-closed graph class. We say that a graph $H$ is apex-$𝒳$ if there exists a vertex $v\in V(H)$ such that $H-v\in 𝒳$. In this terminology, an apex graph may also be called an apex-planar graph.

A layering of a graph $G$ is a sequence ${⟨L_i⟩}_{i\in \mathbb{N}}$ such that ${\bigcup }_{i\in \mathbb{N}}{L}_i=V(G)$ and for every edge $uv\in E(G)$ there is $i\in \mathbb{N}$ such that $u,v\in L_i\cup L_{i+1}$.

A layered parameter is a generalisation of a decomposition-based graph parameter evaluated over all possible decompositions and layerings for a given graph. For example, the layered treewidth of a graph $G$ is the minimum value of ${\max }_{i\in \mathbb{N}}{\max }_{t\in V(T)}|L_i\cap \beta (t)|$ taken over all layerings ${⟨L_i⟩}_{i\in \mathbb{N}}$ and all tree-decompositions $(T,\beta )$ of $G$.

Recently, layered graph decompositions have emerged as a powerful tool for solving a number of long-standing open problems even beyond the scope of minor-closed graph classes and including key results in the theory of the clustered chromatic number [18, 17, 15, 54, 19, 16, 3, 38, 10, 31]. In many cases, the existence of such layered decompositions of small width is implied by the absence of some apex-$𝒳$ graph for a carefully chosen class $𝒳$. Indeed, Dujmović, Morin, and Wood [18] showed that a minor-closed graph class has bounded layered treewidth if and only if it excludes some apex-planar graph and their proof makes use of the structure theorem of Dvořák and Thomas. Hence, Theorem 2 has direct implications for the bounds found by Dujmović et al. [18]. To obtain a better understanding for the structure of excluding an apex-$𝒳$ graph as a minor, it is often easier to understand the structure of excluding an annotated graph $(H,R)$ with $H\in 𝒳$ as a red minor [15, 31, 6]. Our main theorem shows that, whenever $𝒳$ is a class of planar graphs, all involved bounds are polynomial.

The original structure theorem for annotated graphs of bounded bidimensionality due to Protopapas, Thilikos, and Wiederrecht [45] had one additional powerful feature which our polynomial version is lacking: Instead of considering only one colour, Protopapas et al. allowed for the presence of up to $q$ colours and considered the situation where they exclude a $(k\times k)$-grid in which every vertex carries all $q$ colours. As a result of this generality, their bound is of the form $2^{k^{𝐎(1)}{2}^{2^{𝐎(q)}}}$. The main reason for this super-exponential dependency on $q$ is the lack of tools which are able to “homogenise” a given flat wall with respect to $q$ distinct colours within polynomial bounds. It should be mentioned that very recently Gorsky, Seweryn, and Wiederrecht [28] introduced a technique that provides precisely such a homogenisation procedure. However, as Gorsky et al. explain in the conclusion of their paper, a variant of Theorem 1 for $q$ colours realising polynomial bounds is still out of reach for now. The reason is that homogenising flat walls is not enough. As explained in Section 1.3, a crucial step is the homogenisation of so-called “transactions” – a notion from deep within the proof of the Graph Minor Structure Theorem (see [48, 33, 27]). A tool for efficiently dealing with the homogenisation of transactions is still missing at the time of writing.

The celebrated Flat Wall Theorem of Robertson and Seymour [51] states that given any large enough wall $W$ in a graph $G$, either there exists a large clique-minor in $G$ whose model is highly connected to $W$, or there exists a weak near embedding of $G$ centred at $W$ in the sphere with a single vortex, without any bound on the adhesion of the path decomposition of the vortex. The outcome of this first step is, that in the absence of a big red grid, one may ensure that all red vertices are confined into the vortex and the apex set.

This part is relatively straightforward. We start with a large wall $W_0$ and apply a polynomial variant of the Flat Wall Theorem – we use the one of Gorsky et al. [27] – to obtain either a large clique or a small apex set $A_1$ together with a big flat subwall $W_1$ of $W_0$. A result of Protopapas, Thilikos, and Wiederrecht [45] allows us to dismiss the case where we find the clique. Otherwise we subdivide $W_1$ into a large number of pairwise disjoint subwalls arranged in a grid-like shape. If each of them contains a red vertex in its interior, we find a large red grid, otherwise one of them is the desired flat wall $W_2$ without any red vertices. See Figure 3 for an illustration.

Towards deducing the excluded apex-minor version of the local structure theorem, after the initial application of the Flat Wall Theorem, declare the neighbourhood of $A_1$ to be the set of red vertices and set up the numbers to obtain a red $(|A_1|k\times |A_1|k)$-grid as one possible outcome. In case this red grid is found, the pigeonhole principle yields a $(k\times k)$-grid rooted in the neighbourhood of a single member of $A_1$. Otherwise, $W_2$ must be flat without deleting a single apex vertex.

The Society Classification Theorem – first proven explicitly by Kawarabayashi, Thomas, and Wollan [33] – may be seen as an extension of the Flat Wall Theorem as follows: Given a vortex surrounded by a large number of concentric cycles in the embedded part – called the nest – contained within a disk $\mathrm{\Delta }$ of the surface, one may find one of four possible outcomes, see Figure 4 for an illustration:

1. 1.

   A large clique-minor in $G$ whose model is highly connected to the nest.

2. 2.

   Subject to removing a small set of apices $A,$ either

   1. (a)

      a large flat crosscap transaction in $\mathrm{\Delta }$ that traverses the interior of the vortex, and moreover is orthogonal³³3A transaction is a set of disjoint paths linking two disjoint boundary segments of $\mathrm{\Delta }$. We say that a transaction escaping the embedded part of our graph is orthogonal to a nest, if the intersection of each path in the transaction with each cycle in the nest consists of two paths – one caused by escaping the embedded part and the other by entering it again (see Figure 4 as a reference). to most of the starting nest,

   2. (b)

      a large flat handle transaction in $\mathrm{\Delta }$ that traverses the interior of the vortex and moreover is orthogonal to most of the starting nest, or

   3. (c)

      a weak near embedding of the part of the graph drawn in $\mathrm{\Delta },$ centred at the nest, with a bounded number of vortices each with a bounded adhesion path decomposition. Moreover, each of these vortices is surrounded by a large nest which is linked back to the starting nest via many disjoint paths which are orthogonal to the starting nest.

The proof of the red society classification theorem (see Theorem 4.2 in the full version) utilizes the society classification theorem above as a departure point and further refines each of its outcomes as outlined below.

Similarly to before, case (i), where a clique minor is given, is delegated to the result of [45].

To explain cases (ii.a) and (ii.b), we briefly recall the notion of a flat transaction. The goal of this outcome eventually is to augment the weak near embedding using structure extracted from the interior of the vortex. We say that a transaction is monotone if the order of its endpoints on one of the two segments of $\mathrm{\Delta }$ its endpoints are placed on is mirrored by the order of its endpoints on the other segment. We define its strip of a monotone transaction as the union of those components of the graph drawn in $\mathrm{\Delta }$ that remain after deleting the transaction and the boundary of $\mathrm{\Delta },$ and that have neighbours on an interior path of the transaction. A transaction is flat (under $A$) if its strip admits a weak near embedding without vortices (after deleting a set of vertices $A$).

As the given flat transaction is orthogonal to most of the nest, arguments analogous to those used in Step 1 yield a flat subtransaction such that all regions between consecutive paths in the weak near embedding of the strip are homogeneous, meaning all contain a red vertex or none does. In the former case we obtain a large red grid; otherwise, the transaction is entirely free of red vertices. See Figure 5 for an illustration of the situation.

Outcome (ii.c) of the society classification theorem constitutes the main technical challenge. In existing proofs of the GMST (e.g. [48, 52, 33, 27]), refining a weak near embedding by repeatedly splitting vortices requires sacrificing part of the nest, and termination is ensured by using so-called crooked transactions [49]. For technical reasons, this tool is unavailable here. However, the existence of a weak near embedding as in (ii.c) allows us to avoid sacrificing cycles.

Using similar techniques as for the proof of the red flat wall theorem on the wall-like structure from (ii.c), we either find a large red grid or obtain a large nest together with many radially traversing paths orthogonal to it, such that every vortex and every red vertex is enclosed by the nest. We then view the interior of the nest as a single vortex. Either this vortex admits a path decomposition of bounded adhesion, or there exists a large transaction traversing the nest. A sequence of lemmas that follow shows that, such a transaction can always be chosen to traverse the nest interior, be orthogonal to the nest, and avoid all red vertices, similarly to cases (ii.a) and (ii.b). This relies on adapting a technique originating in [57] and further developed in [43, 44]. Crucially, this allows us to discard one side of a nest when splitting it, provided that side contains no red vertex or vortex, without reducing the nest size. It is noteworthy that this case never shows up in the actual proof of the Graph Minor Structure Theorem.

To ensure polynomial bounds, we must also control how new nests connect to previous ones. Naively splitting radial paths at each step would lead to exponential loss. Instead, we inductively maintain a nest tree, a hierarchical tree-like structure in which each nest is connected to its two children nests by sets of radial paths extracted from the splitting transactions, rather than from the parent nest’s own radial paths. See Figure 6 for an illustration. This guarantees that no loss accumulates.

Finally, termination is ensured using the nest tree itself. If the number of leaves in the nest tree exceeds a certain quadratic threshold (in terms of the target grid size), a simple argument using Menger’s Theorem and the rich structure of the nest tree yields a large red grid minor. Otherwise, we obtain only a bounded number of leaves for our nest tree, in total containing all original vortices and red vertices. Each of these leaves can now be seen as vortices admitting a path decomposition of bounded adhesion, as no large transaction traversing them exists. Again using Menger’s Theorem and the structure of the nest tree we can link the nests in the leaves back to (part of) the original nest as desired.

Using the red society classification theorem, we now inductively prove the red local structure theorem with respect to a large wall. The statement essentially reads as follows: Given an annotated graph $(G,R)$ with a large wall $W,$ one may find one of the four possible outcomes:

1. 1.

   A small set of vertices $S$ such that the component of $G-S$ that contains the majority of $W$ is free of red vertices.

2. 2.

   A large red clique-minor in $G$ whose model is highly connected to $W$.

3. 3.

   A large red grid-minor in $G$ whose model is highly connected to $W.$

4. 4.

   A weak near embedding of $G$ centred at $W$ with a bounded number of vortices each with a bounded adhesion path decomposition such that all red vertices are confined in the interior of the vortices.

The proof of the red local structure theorem proceeds by induction, with the red flat wall theorem as the base case. In the base case, the red flat wall theorem yields either a large red grid, in which case we are done, or a weak near-embedding with a single vortex that contains all red vertices in its interior. This embedding serves as the starting point of the refinement procedure.

Using the wall infrastructure provided by the flat wall theorem, we first construct the required nest and then iteratively apply the red society classification theorem to the current weak near-embedding. At each step of this process, if the outcome is a red clique or a red grid, we are done.

If instead a flat and homogeneous crosscap or handle transaction is produced, we proceed as follows. If the transaction is red, we again obtain a red grid. Otherwise, we apply tools from [33] to extend the working surface by attaching a crosscap or handle and routing most of the transaction through it. This yields a single new vortex cell for further refinement. The new vortex is disjoint from the added crosscap or handle, contains all red vertices in its interior, and contains a sufficiently large nest which is defined by combining a part of the crosscap or handle transaction with the original nest, allowing the induction to continue.

In the remaining case, the red society classification theorem produces a weak near-embedding in which the vortex is replaced by a bounded number of vortices, each admitting a path decomposition of bounded adhesion and together containing all red vertices in their interiors. By stitching this embedding along the boundary of the vortex to the already embedded part of the graph, we obtain the final outcome and conclude the proof.

Finally, we are able to use the local structure theorem of Step 3 that in the absence of a large red grid, finds the desired tree-decomposition of Theorem 1.

As we have previously discussed this part follows in a straightforward manner, by employing a fairly standard technique originating from [50] that allows to turn the red local structure theorem into the desired global theorem based on tree-decompositions.