We provide proofs certifying that the structure theorem for vertex sets of bounded bidimensionality holds with polynomial bounds. The bidimensionality of vertex sets is a common generalisation of both treewidth and the face-cover-number of vertex sets in planar graphs. As such, it plays a crucial role in extensions of Courcelle’s Theorem to H-minor-free graphs. Recently, bidimensionality and similar parameters have emerged as key for extensions of known parameterized algorithms for problems defined on a terminal set R. A prominent example for such a problem is Steiner Tree, which admits efficient algorithms on planar graphs whenever R can be covered with few faces. Key to the algorithmic applications of bidimensionality is a structure theorem that explains how a graph G can be decomposed into pieces where the behaviour of R is highly controlled. One may see this structure theorem as a rooted analogue of Robertson and Seymour’s celebrated Grid Theorem. Combining recent advances in obtaining polynomial bounds in the Graph Minors framework with new techniques for handling annotated vertex sets, we show that all parameters in the structure theorem above admit polynomial bounds. As an application, we also provide a sketch showing how our techniques imply polynomial bounds for the structure theorem for graphs excluding an apex minor.

We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. A $q$-colorful graph= is defined as a pair $(G, χ),$ where $G$ is a graph and $χ$ assigns to each vertex a (possibly empty) subset of at most $q$ colors. The colorful minor relation enhances the classical minor relation by merging color sets at contracted edges and allowing the removal of colors from vertices. This framework naturally models algorithmic problems involving graphs with (possibly overlapping) annotated vertex sets. We develop a structural theory for colorful minors by establishing three core theorems characterizing $\mathcal{H}$-colorful minor-free graphs, where $\mathcal{H}$ consists either of a clique or a grid with all vertices assigned all colors, or of grids with colors segregated and ordered on the outer face. Our results reveal that when exclusion is imposed not only on graphs but also to the way colors are distributed in them, a more refined structural landscape appears. On the algorithmic side, we deduce that colorful minor testing is fixed-parameter tractable. Together with the fact that the colorful minor relation forms a well-quasi-order, this implies that every colorful minor-monotone parameter on colorful graphs admits a fixed-parameter algorithm. Furthermore, we derive two algorithmic meta-theorems (AMTs) whose structural conditions are linked to extensions of treewidth and Hadwiger number on colorful graphs. Our results suggest how known AMTs can be extended to incorporate not only the structure of the input graph but also the way the colored vertices are distributed in it.

Let$\mathcal{G}$and$\mathcal{H}$be minor-closed graph classes. We say that the pair$(\mathcal{H},\ \mathcal{G})$is an Erdös-Pósa pair (EP-pair) if there exists a function$f$such that for every$k$and every graph$G\in \mathcal{G}$, either$G$has$k$pairwise vertex-disjoint sub graphs which do not belong to$\mathcal{H}$, or there exists a set$S\subseteq V(G)$of size at most$f(k)$for which$G-S\in \mathcal{H}$. The classic result of Erdös and Pósa says that if$\mathcal{F}$is the class of forests, then$(\mathcal{F}, \mathcal{G})$is an EP-pair for all graph classes$\mathcal{G}$. A minor-closed graph class$\mathcal{G}$is an EP-counterexample for$\mathcal{H}$if$\mathcal{G}$is minimal with the property that$(\mathcal{H},\ \mathcal{G})$is not an EP-pair. In this paper, we prove that for every minor-closed graph class$\mathcal{H}$the set$\mathfrak{C}_{\mathcal{H}}$of all EP-counterexamples for$\mathcal{H}$is finite. In particular, we provide a complete characterization of$\mathfrak{C}_{\mathcal{H}}$for every$\mathcal{H}$and give a constructive upper bound on its size. We show that each class$\mathcal{G}$in$\mathfrak{C}_{\mathcal{H}}$can be described as the set of all minors of some, suitably defined, sequence of grid-like graphs$\langle{W}_{k}\rangle_{k\in \mathbb{N}}$. Moreover, each$\mathrm{W}_{k}$admits a half-integral packing, i.e.,$k$copies of some$H\not\in \mathcal{H}$where no vertex is used more than twice. This implies a complete delineation of the half-integrality threshold of the Erdös-Pósa property for minors and as a corollary, we obtain a constructive proof of Thomas' conjecture on the half-integral Erdös-Pósa property for minors which was recently confirmed by Liu. Our results are algorithmic. Let$h=h(\mathcal{H})$denote the maximum size of an obstruction to$\mathcal{H}$. For every minor-closed graph class$\mathcal{H}$, we construct an algorithm that, given a graph$G$and an integer$k$, either outputs a half-integral packing of$k$copies of some$H\not\in \mathcal{H}$or outputs a set of at most$2^{k^{\overline{\mathcal{O}}_{h}(1)}}$vertices whose deletion creates a graph in$\mathcal{H}$in time$2^{2^{k^{\mathcal{O}_{h}(1)}}}\cdot\vert G\vert ^{4}\log\vert G\vert$. Moreover, as a consequence of our results, for every minor-closed class$\mathcal{H}$, we obtain min-max-dualities, which may be seen as analogues of the celebrated Grid Theorem of Robertson and Seymour, for the recently introduced parameters$\mathcal{H}$-treewidth and elimination distance to$\mathcal{H}$.

In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minors if and only if it is planar. In particular, for every non-planar graph H they gave examples showing that the Erdős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. Liu’s proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation on graph parameters) graph parameter EP_H such that H has the Erdős-Pósa property in a minor-closed graph class 𝒢 if and only if sup{EP_H(G) ∣ G ∈ 𝒢} is finite. We prove this conjecture for the class ℋ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H ∈ ℋ, the parameter EP_H(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa property of H which can be found as a minor in G. Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in ℋ.

Many important graph classes are characterized by means of layouts (a vertex ordering) excluding some patterns. For example, a graph G = (V,E) is a proper interval graph if and only if G has a layout 𝐋 such that for every triple of vertices such that x≺_𝐋 y≺_𝐋 z, if xz ∈ E, then xy ∈ E and yz ∈ E. Such a triple x, y, z is called an indifference triple. In this paper, we investigate the concept of excluding a set of patterns in tree-layouts rather than layouts. A tree-layout 𝐓_G = (T,r,ρ_G) of a graph G = (V,E) is a tree T rooted at some node r and equipped with a one-to-one mapping ρ_G between V and the nodes of T such that for every edge xy ∈ E, either x is an ancestor of y, denoted x≺_{𝐓_G} y, or y is an ancestor of x. Excluding patterns in a tree-layout is now defined using the ancestor relation. This leads to an unexplored territory of graph classes. In this paper, we initiate the study of such graph classes with the class of proper chordal graphs defined by excluding indifference triples in tree-layouts. Our results combine characterization, compact and canonical representation as well as polynomial time algorithms for the recognition and the graph isomorphism of proper chordal graphs. For this, one of the key ingredients is the introduction of the concept of FPQ-hierarchy generalizing the celebrated PQ-tree data-structure.