Search

Data quantity and quality play a vital role in determining the performance of Large Language Models (LLMs). High-quality data, in particular, can significantly boost the LLM's ability to generalize on a wide range of downstream tasks. Large pre-training datasets for leading LLMs remain inaccessible to the public, whereas many open datasets are small in size (less than 5 trillion tokens), limiting their suitability for training large models. In this paper, we introduce GneissWeb, a large dataset yielding around 10 trillion tokens that caters to the data quality and quantity requirements of training LLMs. Our GneissWeb recipe that produced the dataset consists of sharded exact sub-string deduplication and a judiciously constructed ensemble of quality filters. GneissWeb achieves a favorable trade-off between data quality and quantity, producing models that outperform models trained on state-of-the-art open large datasets (5+ trillion tokens). We show that models trained using GneissWeb dataset outperform those trained on FineWeb-V1.1.0 by 2.73 percentage points in terms of average score computed on a set of 11 commonly used benchmarks (both zero-shot and few-shot) for pre-training dataset evaluation. When the evaluation set is extended to 20 benchmarks (both zero-shot and few-shot), models trained using GneissWeb still achieve a 1.75 percentage points advantage over those trained on FineWeb-V1.1.0.

We introduce Granite Vision, a lightweight large language model with vision capabilities, specifically designed to excel in enterprise use cases, particularly in visual document understanding. Our model is trained on a comprehensive instruction-following dataset, including document-related tasks, such as content extraction from tables, charts, diagrams, sketches, and infographics, as well as general image tasks. The architecture of Granite Vision is centered around visual modality alignment with a decoder-only, 2 billion parameter Granite large language model. Additionally, we introduce a dedicated safety classification approach in test-time that leverages a sparse set of attention vectors to identify potential harmful inputs. Despite its lightweight architecture, Granite Vision achieves strong results in standard benchmarks related to visual document understanding, as well as on the LiveXiv benchmark, which is designed to avoid test set contamination by using a constantly updated corpus of recently published Arxiv papers. We are releasing the model under the Apache-2 license, allowing for both research and commercial use, while offering complete visibility into the training data and other relevant details. See https://huggingface.co/ibm-granite/ for model weights.

The Planar Graph Product Structure Theorem of Dujmovi\'c et al. [J. ACM '20] says that every planar graph $G$ is contained in $H\boxtimes P\boxtimes K_3$ for some planar graph $H$ with treewidth at most 3 and some path $P$. This result has been the key to solving several old open problems. Several people have asked whether the Planar Graph Product Structure Theorem can be proved with good upper bounds on the length of $P$. No $o(n)$ upper bound was previously known for $n$-vertex planar graphs. We answer this question in the affirmative, by proving that for any $\epsilon\in (0,1)$ every $n$-vertex planar graph is contained in $H\boxtimes P\boxtimes K_{O(1/\epsilon)}$, for some planar graph $H$ with treewidth 3 and for some path $P$ of length $O(\frac{1}{\epsilon}n^{(1+\epsilon)/2})$. This bound is almost tight since there is a lower bound of $\Omega(n^{1/2})$ for certain $n$-vertex planar graphs. In fact, we prove a stronger result with $P$ of length $O(\frac{1}{\epsilon}\,\textrm{tw}(G)\,n^{\epsilon})$, which is tight up to the $O(\frac{1}{\epsilon}\,n^{\epsilon})$ factor for every $n$-vertex planar graph $G$. Finally, taking $\epsilon=\frac{1}{\log n}$, we show that every $n$-vertex planar graph $G$ is contained in $H\boxtimes P\boxtimes K_{O(\log n)}$ for some planar graph $H$ with treewidth at most 3 and some path $P$ of length $O(\textrm{tw}(G)\,\log n)$. This result is particularly attractive since the treewidth of the product $H\boxtimes P\boxtimes K_{O(\log n)}$ is within a $O(\log^2n)$ factor of the treewidth of $G$., Comment: 21 pages, 1 figure

Purpose: Subarachnoid haemorrhage is a potentially fatal consequence of intracranial aneurysm rupture, however, it is difficult to predict if aneurysms will rupture. Prophylactic treatment of an intracranial aneurysm also involves risk, hence identifying rupture-prone aneurysms is of substantial clinical importance. This systematic review aims to evaluate the performance of machine learning algorithms for predicting intracranial aneurysm rupture risk. Methods: MEDLINE, Embase, Cochrane Library and Web of Science were searched until December 2023. Studies incorporating any machine learning algorithm to predict the risk of rupture of an intracranial aneurysm were included. Risk of bias was assessed using the Prediction Model Risk of Bias Assessment Tool (PROBAST). PROSPERO registration: CRD42023452509. Results: Out of 10,307 records screened, 20 studies met the eligibility criteria for this review incorporating a total of 20,286 aneurysm cases. The machine learning models gave a 0.66-0.90 range for performance accuracy. The models were compared to current clinical standards in six studies and gave mixed results. Most studies posed high or unclear risks of bias and concerns for applicability, limiting the inferences that can be drawn from them. There was insufficient homogenous data for a meta-analysis. Conclusions: Machine learning can be applied to predict the risk of rupture for intracranial aneurysms. However, the evidence does not comprehensively demonstrate superiority to existing practice, limiting its role as a clinical adjunct. Further prospective multicentre studies of recent machine learning tools are needed to prove clinical validation before they are implemented in the clinic., Comment: Clin Neuroradiol (2024)

This paper provides a primer on Large Language Models (LLMs) and identifies their strengths, limitations, applications and research directions. It is intended to be useful to those in academia and industry who are interested in gaining an understanding of the key LLM concepts and technologies, and in utilising this knowledge in both day to day tasks and in more complex scenarios where this technology can enhance current practices and processes., Comment: 33 pages, 19 figures

This study concerns the far-field boundary conditions (BCs) for airfoil simulations at high incidence where the lift and drag are comparable in magnitude and the moment is significant. A NACA 0012 airfoil was simulated at high Reynolds number with the Spalart-Allmaras turbulence model in incompressible, steady flow. We use the impulse form of the lift, drag, and moment equations applied to a control volume coincident with the square computational domain, to explore the BCs. It is well known that consistency with the lift requires representing the airfoil by a point vortex, but it is largely unknown that consistency with the drag requires a point source as was first discovered by Lagally (1922) and Filon (1926). We show that having a point source in the BCs is more important at high drag than using a point vortex. The reason is that BCs without a point source cause blockage at the top and bottom sidewalls in a manner very similar to wind tunnel blockage for experiments. A simple "Lagally-Filon" correction for small levels of blockage is derived and shown to bring the results much closer to those obtained using boundary conditions including a point source. Although consistent with the lift and drag, the combined point vortex and source boundary condition is not consistent with the moment equation but the further correction for this inconsistency is shown to be very small. We speculate that the correction may be more important in cases where the moment is critical, such as vertical-axis turbines., Comment: 32 pages, 14 figures

This paper summarises the intersection of Web3 and AI technologies, synergies between these technologies, and gaps that we suggest exist in the conception of the possible integrations of these technologies. The summary is informed by a comprehensive literature review of current academic and industry papers, analyst reports, and Ethereum research community blogposts. We focus our contribution on the perceived gaps and detail some novel approaches that would benefit the blockchain/Web3 ecosystem. We believe that the overview presented in this paper will help guide researchers interested in the intersection of Web3 and AI technologies., Comment: 20 pages, 6 figures

We prove that every planar graph is contained in $H_1\boxtimes H_2\boxtimes K_2$ for some graphs $H_1$ and $H_2$ both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible: for any $c \in \mathbb{N}$, there is a planar graph $G$ such that for any tree $T$ and graph $H$ with $\text{tw}(H) \leq 2$, $G$ is not contained in $H \boxtimes T \boxtimes K_c$., Comment: arXiv admin note: text overlap with arXiv:2410.20333

This paper explores the structure of graphs defined by an excluded minor or an excluded odd minor through the lens of graph products and tree-decompositions. We prove that every graph excluding a fixed odd minor is contained in the strong product of two graphs each with bounded treewidth. For graphs excluding a fixed minor, we strengthen the result by showing that every such graph is contained in the strong product of two digraphs with bounded indegree and with bounded treewidth. This result has the advantage that the product now has bounded degeneracy. In the setting of 3-term products, we show that every $K_t$-minor-free graph is contained in $H_1\boxtimes H_2 \boxtimes K_{c(t)}$ where $\text{tw}(H_i)\leq t-2$. This treewidth bound is close to tight: in any such result with $\text{tw}(H_i)$ bounded, both $H_1$ and $H_2$ can be forced to contain any graph of treewidth $t-5$, implying $\text{tw}(H_1)\geq t-5$ and $\text{tw}(H_2)\geq t-5$. Analogous lower and upper bounds are shown for any excluded minor, where the minimum possible bound on $\text{tw}(H_i)$ is tied to the treedepth of the excluded minor. Subgraphs of the product of two graphs with bounded treewidth have two tree-decompositions where any bag from the first decomposition intersects any bag from the second decomposition in a bounded number, $k$, of vertices, so called $k$-orthogonal tree-decompositions. We show that graphs excluding a fixed odd-minor have a tree-decomposition and a path-decomposition that are $O(1)$-orthogonal. This implies that such graphs have a tree-decomposition in which each bag has bounded pathwidth. This result is best possible in that `pathwidth' cannot be replaced by `bandwidth' or `treedepth'. Moreover, we characterize the minor-closed classes that have a tree-decomposition in which each bag has bounded bandwidth, or each bag has bounded treedepth.

Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence of a large complete graph minor. To formalise this, we say that a graph class $\mathcal{G}$ is (tw,had)-bounded if there is a function $f$ (called the (tw,had)-bounding function) such that tw$(G)$ $\leq$ $f$(had$(G)$) for every graph $G \in \mathcal{G}$. We characterise (tw,had)-bounded graph classes as those that exclude some planar graph as an induced minor, and use this characterisation to show that every proper vertex-minor-closed class is (tw,had)-bounded. Furthermore, we demonstrate that any (tw,had)-bounded graph class has a (tw,had)-bounding function in O(had$(G)^9$polylog(had$(G)$)). Our bound comes from the bound for the Grid Minor Theorem given by Chuzhoy and Tan, and any quantitative improvement to their result will lead directly to an improvement to our result. More strongly, we conjecture that every (tw,had)-bounded graph class has a linear (tw,had)-bounding function. In support of this conjecture, we show that it holds for the class of outer-string graphs, and for a natural generalisation of outer-string graphs: intersection graphs of strings rooted at the boundary of a fixed surface. We also verify our conjecture for low-rank perturbations of circle graphs, which is an important step towards verifying it for all proper vertex-minor-closed classes., Comment: 26 pages, 6 Figures

The mechanical competence and suturing ability of collagen-based membranes are paramount in Guided Bone Regeneration (GBR) therapy, to ensure damage-free implantation, fixation and space maintenance in vivo. However, contact with the biological medium can induce swelling of collagen molecules, yielding risks of membrane sinking into the bone defect, early loss of barrier function, and irreversibly compromised clinical outcomes. To address these challenges, this study investigates the effect of the crosslinked network architecture on both mechanical and suture-holding properties of a new atelocollagen (AC) membrane. UV-cured networks were obtained via either single functionalisation of AC with 4-vinylbenzyl chloride (4VBC) or sequential functionalisation of AC with both 4VBC and methacrylic anhydride (MA). The wet-state compression modulus (Ec), Atomic Force Microscopy elastic modulus (EAFM) and swelling ratio (SR) were significantly affected by the UV-cured network architecture, leading up to a three-fold reduction in SR, and about two-fold increase in both Ec and EAFM, in the sequentially functionalised, compared to the single-functionalised, samples. Electron microscopy, dimensional analysis and compression testing revealed the direct impact of the ethanol series dehydration process on membrane microstructure, yielding densification of the freshly synthesised porous samples and a pore-free microstructure with increased Ec. Noteworthy, the single-functionalised, but not the sequentially functionalised, samples displayed higher suture retention strength in both the dry state and following 1 hour in Phosphate Buffered Saline (PBS), compared to Bio-Gide(r). These structure-property relationships confirm the key role played by the molecular architecture of covalently crosslinked collagen, aimed towards long-lasting resorbable membranes for predictable GBR., Comment: 40 pages, 9 figures, 1 Table. Accepted in Biomaterials Materials

Data preparation is the first and a very important step towards any Large Language Model (LLM) development. This paper introduces an easy-to-use, extensible, and scale-flexible open-source data preparation toolkit called Data Prep Kit (DPK). DPK is architected and designed to enable users to scale their data preparation to their needs. With DPK they can prepare data on a local machine or effortlessly scale to run on a cluster with thousands of CPU Cores. DPK comes with a highly scalable, yet extensible set of modules that transform natural language and code data. If the user needs additional transforms, they can be easily developed using extensive DPK support for transform creation. These modules can be used independently or pipelined to perform a series of operations. In this paper, we describe DPK architecture and show its performance from a small scale to a very large number of CPUs. The modules from DPK have been used for the preparation of Granite Models [1] [2]. We believe DPK is a valuable contribution to the AI community to easily prepare data to enhance the performance of their LLM models or to fine-tune models with Retrieval-Augmented Generation (RAG)., Comment: 10 pages, 7 figures

We show that a quantum spin system has an exact free-parafermion solution if its frustration graph is an oriented indifference graph. Further, we show that if the frustration graph of a model can be dipath oriented via switching operations, then the model is integrable in the sense that there is a family of commuting independent set charges. Additionally, we establish an efficient algorithm for deciding whether this is possible. Our characterisation extends that given for free-fermion solvability. Finally, we apply our results to solve three qudit spin models., Comment: 22 pages, 2 figures

This paper studies the structure of graphs with given tree-width and excluding a fixed complete bipartite subgraph, which generalises the bounded degree setting. We give a new structural description of such graphs in terms of so-called quasi-tree-partitions. We demonstrate the utility of this result through applications to (fractional) clustered colouring. Further generalisations of these structural and colouring results are presented.

A colouring of a graph $G$ has clustering $k$ if the maximum number of vertices in a monochromatic component equals $k$. Motivated by recent results showing that many natural graph classes are subgraphs of the strong product of a graph with bounded treewidth and a path, this paper studies clustered colouring of strong products of two bounded treewidth graphs, where none, one, or both graphs have bounded degree. For example, in the case of two colours, if $n$ is the number of vertices in the product, then we show that clustering $\Theta(n^{2/3})$ is best possible, even if one of the graphs is a path. However, if both graphs have bounded degree, then clustering $\Theta(n^{1/2})$ is best possible. With three colours, if one of the graphs has bounded degree, then we show that clustering $\Theta(n^{3/7})$ is best possible. However, if neither graph has bounded degree, then clustering $\Omega(n^{1/2})$ is necessary. More general bounds for any given number of colours are also presented.

We show that every $n$-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order $O(\sqrt{n}\log^2 n)$. Equivalently, every $n$-vertex planar graph $G$ has a set $X$ of $O(\sqrt{n}\log^2 n)$ vertices such that $G-X$ has bandwidth $O(\sqrt{n}\log^2 n)$. This result holds in the more general setting of graphs contained in the strong product of a bounded treewidth graph and a path, which includes bounded genus graphs, graphs excluding a fixed apex graph as a minor, and $k$-planar graphs for fixed $k$. These results are obtained using two ingredients. The first is a new local sparsification lemma, which shows that every $n$-vertex planar graph $G$ has a set of $O((n\log n)/D)$ vertices whose removal results in a graph with local density at most $D$. The second is a generalization of a method of Feige and Rao, that relates bandwidth and local density using volume-preserving Euclidean embeddings., Comment: 34 pages including 4 figures, many formulas, and two appendices

There are finitely many graphs with diameter $2$ and girth 5. What if the girth 5 assumption is relaxed? Apart from stars, are there finitely many triangle-free graphs with diameter $2$ and no $K_{2,3}$ subgraph? This question is related to the existence of triangle-free strongly regular graphs, but allowing for a range of co-degrees gives the question a more extremal flavour. More generally, for fixed $s$ and $t$, are there infinitely many twin-free triangle-free $K_{s,t}$-free graphs with diameter 2? This paper presents partial results regarding these questions, including computational results, potential Cayley-graph and probabilistic constructions.

Computing at the edge is increasingly important as Internet of Things (IoT) devices at the edge generate massive amounts of data and pose challenges in transporting all that data to the Cloud where they can be analyzed. On the other hand, harnessing the edge data is essential for offering cognitive applications, if the challenges, such as device capabilities, connectivity, and heterogeneity can be overcome. This paper proposes a novel three-tier architecture, called EdgeSphere, which harnesses resources of the edge devices, to analyze the data in situ at the edge. In contrast to the state-of-the-art cloud and mobile applications, EdgeSphere applications span across cloud, edge gateways, and edge devices. At its core, EdgeSphere builds on Apache Mesos to optimize resources usage and scheduling. EdgeSphere has been applied to practical scenarios and this paper describes the engineering challenges faced as well as innovative solutions.

A $\textit{dominating $K_t$-model}$ in a graph $G$ is a sequence $(T_1,\dots,T_t)$ of pairwise disjoint non-empty connected subgraphs of $G$, such that for $1 \leqslant i

Purpose: Most studies evaluating artificial intelligence (AI) models that detect abnormalities in neuroimaging are either tested on unrepresentative patient cohorts or are insufficiently well-validated, leading to poor generalisability to real-world tasks. The aim was to determine the diagnostic test accuracy and summarise the evidence supporting the use of AI models performing first-line, high-volume neuroimaging tasks. Methods: Medline, Embase, Cochrane library and Web of Science were searched until September 2021 for studies that temporally or externally validated AI capable of detecting abnormalities in first-line CT or MR neuroimaging. A bivariate random-effects model was used for meta-analysis where appropriate. PROSPERO: CRD42021269563. Results: Only 16 studies were eligible for inclusion. Included studies were not compromised by unrepresentative datasets or inadequate validation methodology. Direct comparison with radiologists was available in 4/16 studies. 15/16 had a high risk of bias. Meta-analysis was only suitable for intracranial haemorrhage detection in CT imaging (10/16 studies), where AI systems had a pooled sensitivity and specificity 0.90 (95% CI 0.85 - 0.94) and 0.90 (95% CI 0.83 - 0.95) respectively. Other AI studies using CT and MRI detected target conditions other than haemorrhage (2/16), or multiple target conditions (4/16). Only 3/16 studies implemented AI in clinical pathways, either for pre-read triage or as post-read discrepancy identifiers. Conclusion: The paucity of eligible studies reflects that most abnormality detection AI studies were not adequately validated in representative clinical cohorts. The few studies describing how abnormality detection AI could impact patients and clinicians did not explore the full ramifications of clinical implementation.

This letter critically examines the recent article by Infante et al. assessing the utility of large language models (LLMs) like GPT-4, Perplexity, and Bard in identifying urgent findings in emergency radiology reports. While acknowledging the potential of LLMs in generating labels for computer vision, concerns are raised about the ethical implications of using patient data without explicit approval, highlighting the necessity of stringent data protection measures under GDPR.

Artificial neural networks trained on large, expert-labelled datasets are considered state-of-the-art for a range of medical image recognition tasks. However, categorically labelled datasets are time-consuming to generate and constrain classification to a pre-defined, fixed set of classes. For neuroradiological applications in particular, this represents a barrier to clinical adoption. To address these challenges, we present a self-supervised text-vision framework that learns to detect clinically relevant abnormalities in brain MRI scans by directly leveraging the rich information contained in accompanying free-text neuroradiology reports. Our training approach consisted of two-steps. First, a dedicated neuroradiological language model - NeuroBERT - was trained to generate fixed-dimensional vector representations of neuroradiology reports (N = 50,523) via domain-specific self-supervised learning tasks. Next, convolutional neural networks (one per MRI sequence) learnt to map individual brain scans to their corresponding text vector representations by optimising a mean square error loss. Once trained, our text-vision framework can be used to detect abnormalities in unreported brain MRI examinations by scoring scans against suitable query sentences (e.g., 'there is an acute stroke', 'there is hydrocephalus' etc.), enabling a range of classification-based applications including automated triage. Potentially, our framework could also serve as a clinical decision support tool, not only by suggesting findings to radiologists and detecting errors in provisional reports, but also by retrieving and displaying examples of pathologies from historical examinations that could be relevant to the current case based on textual descriptors., Comment: Under Review

The defective chromatic number of a graph class $\mathcal{G}$ is the minimum integer $k$ such that for some integer $d$, every graph in $\mathcal{G}$ is $k$-colourable such that each monochromatic component has maximum degree at most $d$. Similarly, the clustered chromatic number of a graph class $\mathcal{G}$ is the minimum integer $k$ such that for some integer $c$, every graph in $\mathcal{G}$ is $k$-colourable such that each monochromatic component has at most $c$ vertices. This paper determines or establishes bounds on the defective and clustered chromatic numbers of graphs with given girth in minor-closed classes defined by the following parameters: Hadwiger number, treewidth, pathwidth, treedepth, circumference, and feedback vertex number. One striking result is that for any integer $k$, for the class of triangle-free graphs with treewidth $k$, the defective chromatic number, clustered chromatic number and chromatic number are all equal. The same result holds for graphs with treedepth $k$, and generalises for graphs with no $K_p$ subgraph. We also show, via a result of K\"{u}hn and Osthus~[2003], that $K_t$-minor-free graphs with girth $g\geq 5$ are properly $O(t^{c_g})$ colourable, where $c_g\in(0,1)$ with $c_g\to 0$, thus asymptotically improving on Hadwiger's Conjecture.

Climate change and environmental concerns represent a global crisis accompanied by significant economic challenges. Regular international conferences held to address these issues, such as in the UK (2021) and Egypt (2022), spark debate about the effectiveness and practicality of international commitments. This study examines international treaties from a different perspective, emphasizing the need to understand the power dynamics and stakeholder interests that delay logical actions to mitigate anthropogenic contributions to climate change and their impacts. Environmental and social concerns tend to increase within nations as their economies develop, where they fight to keep acceptable standards of living while reducing emissions volume. So, nations play disproportionate roles in global decision-making based on the size of their economies. Addressing climate change requires a paradigm shift to emphasize acknowledging and adhering to global commitments through civil pressure, rather than relying on traditional yet biased systems of international political diplomacy. Here, climate-friendly actions are evaluated and ideas to promote such activities are proposed. We introduce a "transition regime" as a solution to this metastasis challenge which gradually infects all nations.

Motivated by recent developments regarding the product structure of planar graphs, we study relationships between treewidth, grid minors, and graph products. We show that the Cartesian product of any two connected $n$-vertex graphs contains an $\Omega(\sqrt{n})\times\Omega(\sqrt{n})$ grid minor. This result is tight: The lexicographic product (which includes the Cartesian product as a subgraph) of a star and any $n$-vertex tree has no $\omega(\sqrt{n})\times\omega(\sqrt{n})$ grid minor.

A multigraph drawn in the plane is non-homotopic if no two edges connecting the same pair of vertices can be continuously deformed into each other without passing through a vertex, and is $k$-crossing if every pair of edges (self-)intersects at most $k$ times. We prove that the number of edges in an $n$-vertex non-homotopic $k$-crossing multigraph is at most $6^{13 n (k + 1)}$, which is a big improvement over previous upper bounds. We also study this problem in the setting of monotone drawings where every edge is an x-monotone curve. We show that the number of edges, $m$, in such a drawing is at most $2 \binom{2n}{k + 1}$ and the number of crossings is $\Omega\bigl(\frac{m^{2 + 1/k}}{n^{1 + 1/k}}\bigr)$. For fixed $k$ these bounds are both best possible up to a constant multiplicative factor., Comment: 19 pages

Clinical neuroimaging data is naturally hierarchical. Different magnetic resonance imaging (MRI) sequences within a series, different slices covering the head, and different regions within each slice all confer different information. In this work we present a hierarchical attention network for abnormality detection using MRI scans obtained in a clinical hospital setting. The proposed network is suitable for non-volumetric data (i.e. stacks of high-resolution MRI slices), and can be trained from binary examination-level labels. We show that this hierarchical approach leads to improved classification, while providing interpretability through either coarse inter- and intra-slice abnormality localisation, or giving importance scores for different slices and sequences, making our model suitable for use as an automated triaging system in radiology departments.

The clustered chromatic number of a graph class $\mathcal{G}$ is the minimum integer $c$ such that every graph $G\in\mathcal{G}$ has a $c$-colouring where each monochromatic component in $G$ has bounded size. We study the clustered chromatic number of graph classes $\mathcal{G}_H^{\text{odd}}$ defined by excluding a graph $H$ as an odd-minor. How does the structure of $H$ relate to the clustered chromatic number of $\mathcal{G}_H^{\text{odd}}$? We adapt a proof method of Norin, Scott, Seymour and Wood (2019) to show that the clustered chromatic number of $\mathcal{G}_H^{\text{odd}}$ is tied to the tree-depth of $H$.

We prove that the $k$-power of any planar graph $G$ is contained in $H\boxtimes P\boxtimes K_{f(\Delta(G),k)}$ for some graph $H$ with bounded treewidth, some path $P$, and some function $f$. This resolves an open problem of Ossona de Mendez. In fact, we prove a more general result in terms of shallow minors that implies similar results for many `beyond planar' graph classes, without dependence on $\Delta(G)$. For example, we prove that every $k$-planar graph is contained in $H\boxtimes P\boxtimes K_{f(k)}$ for some graph $H$ with bounded treewidth and some path $P$, and some function $f$. This resolves an open problem of Dujmovi\'c, Morin and Wood. We generalise all these results for graphs of bounded Euler genus, still with an absolute bound on the treewidth. At the heart of our proof is the following new concept of independent interest. An $\ell$-blocking partition of a graph $G$ is a partition of $V(G)$ into connected sets such that every path of length greater than $\ell$ in $G$ contains at least two vertices in one part. We prove that for some constant $\ell \ge 1$ every graph of Euler genus $g$ has an $\ell$-blocking partition with parts of size bounded by a function of $\Delta(G)$ and $g$. Motivated by this result, we study blocking partitions in their own right. We show that every graph $G$ has a $2$-blocking partition with parts of size bounded by a function of $\Delta(G)$ and $\textrm{tw}(G)$. On the other hand, we show that 4-regular graphs do not have $\ell$-blocking partitions with bounded size parts.

We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes K_c$. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a fixed graph as a minor.