Reduced bandwidth: a qualitative
strengthening of twin-width in
minor-closed classes (and beyond)

Édouard Bonnet ³³3CNRS, Lyon, France ([email protected]). The first author was supported by the ANR projects TWIN-WIDTH (ANR-21-CE48-0014) and Digraphs (ANR-19-CE48-0013). O-joung Kwon ⁴⁴4Department of Mathematics, Incheon National University, and Discrete Mathematics Group, Institute for Basic Science (IBS), South Korea. The second author was supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294), and by the Institute for Basic Science (IBS-R029-C1). ([email protected]). David R. Wood ⁵⁵5School of Mathematics, Monash University, Melbourne, Australia ([email protected]). Research supported by the Australian Research Council.

Abstract

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$ , each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$ . For any graph parameter $f$ , we define the reduced $f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$ . Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$ . We show that planar graphs have reduced bandwidth at most $466$ and twin-width at most $583$ . Our bounds for graphs of Euler genus $\gamma$ are $O(\gamma)$ . Lastly, we show that fixed powers of graphs in a proper minor-closed class have bounded reduced bandwidth (irrespective of the degree of the vertices). In particular, we show that map graphs of Euler genus $\gamma$ have reduced bandwidth $O(\gamma^{4})$ . Lastly, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6.

1 Introduction

Twin-width is a measure of graph¹¹1We consider simple, finite, undirected graphs $G$ with vertex-set $V(G)$ and edge-set $E(G)$ . A graph class is a set of graphs closed under isomorphism. A graph class is hereditary if it is closed under taking subgraphs. A graph class is monotone if it is closed under taking induced subgraphs. A graph $H$ is a minor of a graph $G$ if $H$ is isomorphic to a graph obtained from a subgraph of $G$ by contracting edges. A graph class $\mathcal{G}$ is proper minor-closed if $\mathcal{G}$ is closed under taking minors, and some graph is not in $\mathcal{G}$ . complexity recently introduced by Bonnet et al. [9] (inspired by the work of Marcus and Tardos [34] and Guillemot and Marx [26]). The topic has attracted widespread interest [39, 40, 38, 9, 4, 5, 6, 7, 10, 2, 8, 23, 1, 44, 3, 15], often motivated by connections to model theory, logic, graph sparsity, fixed parameter tractability, enumerative combinatorics, and permutations.

We start with an informal description. Given a graph $G$ , choose two vertices $u$ and $v$ in $G$ , identify $u$ and $v$ into a single vertex, and colour each edge incident to exactly one of $u$ and $v$ red. Repeat this step until the graph has only one vertex. At each stage, the introduced red edges indicate an ‘error’ in the reduction sequence. The goal is to find a sequence of identifications with small error. Twin-width measures the error by the maximum degree of the red graph (minimised over all reduction sequences).

To formalise this idea we need the following definitions. A trigraph is a triple $G=(V,E,R)$ where $V$ is a finite set, and $E$ and $R$ are disjoint subsets of $\binom{V}{2}$ . Elements of $V$ are vertices. Elements of $E\cup R$ are edges, edges in $E$ are black, and edges in $R$ are red. Let $V(G):=V$ and $E(G):=E$ and $R(G):=R$ . Let $\widetilde{G}$ be the spanning subgraph of $G$ consisting of the red edges. For distinct vertices $u,v\in V(G)$ , let $G/u,v$ be the trigraph $(V^{\prime},E^{\prime},R^{\prime})$ with:

•

$V^{\prime}=(V\setminus\{u,v\})\cup\{w\}$ where $w\not\in V$ ,
•

$G-\{u,v\}=(G/u,v)-w$ , and
•
for all $x\in V\setminus\{u,v\}$ :
- –
  
  $wx\in E^{\prime}$ if and only if $ux\in E$ and $vx\in E$ ,
- –
  
  $wx\not\in E^{\prime}\cup R^{\prime}$ if and only if $ux\not\in E\cup R$ and $vx\not\in E\cup R$ , and
- –
  
  $wx\in R^{\prime}$ otherwise.

The underlying graph (or total graph) of a trigraph $G$ is the graph $H$ with $V(H)=V(G)$ and $E(H)=E(G)\cup R(G)$ .

A sequence of trigraphs $G_{\_}n,G_{\_}{n-1},\dots,G_{\_}1$ is a reduction sequence of $G_{\_}n$ (also called contraction sequence) if for each $i\in\{2,\dots,n\}$ we have $G_{\_}{i-1}=G_{\_}i/u,v$ for some $u,v\in V(G_{\_}i)$ , and $G_{\_}1$ is a trigraph with one vertex. In this case, each ‘prefix’ $G_{\_}n,G_{\_}{n-1},\ldots,G_{\_}i$ is called a partial reduction sequence to $G_{\_}i$ . A (partial) reduction sequence of a graph $G$ is a (partial) reduction sequence of the trigraph $(V(G),E(G),\emptyset)$ (with no red edges).

Given a graph $G$ , it is natural to ask for a reduction sequence $G_{\_}n,\dots,G_{\_}1$ such that the red graphs $\widetilde{G}_{\_}n,\dots,\widetilde{G}_{\_}1$ have desirable properties. For example, a graph has a reduction sequence with no red edges if and only if it is a cograph [9] (and cographs are considered to be particularly well-behaved). Bonnet et al. [9] cared about the maximum degree of the red graphs. They defined the twin-width of a graph $G$ , denoted by $\operatorname{tww}(G)$ , to be the minimum $k\in\mathbb{N}_{\_}0$ such that there is a reduction sequence $G_{\_}n,G_{\_}{n-1},\dots,G_{\_}1$ of $G$ where $\widetilde{G}_{\_}i$ has maximum degree at most $k$ for each $i\in\{1,\dots,n\}$ .

This paper studies reduction sequences where the red graph has other properties in addition to bounded maximum degree. For any graph parameter²²2A graph parameter is a function $f$ such that $f(G)\in\mathbb{N}_{\_}0$ for every graph $G$ , and $f(G_{\_}1)=f(G_{\_}2)$ for all isomorphic graphs $G_{\_}1$ and $G_{\_}2$ . Examples of relevance to this paper include maximum degree $\Delta(G)$ , bandwidth $\operatorname{bw}(G)$ , pathwidth $\operatorname{pw}(G)$ , treewidth $\operatorname{tw}(G)$ , clique-width $\operatorname{cw}(G)$ , and boolean-width $\operatorname{blw}(G)$ . A graph parameter $f$ is monotone if for each $k\in\mathbb{N}_{\_}0$ the graph class $\{G:f(G)\leqslant k\}$ is monotone. A graph parameter $f$ is hereditary if for each $k\in\mathbb{N}_{\_}0$ the graph class $\{G:f(G)\leqslant k\}$ is hereditary. A graph parameter $f$ is union-closed if $f(G\cup H)\leqslant\max(f(G),f(H))$ for all disjoint graphs $G$ and $H$ . $f$ , let reduced $f$ be the graph parameter ${f}^{\downarrow}$ , where for any graph $G$ , ${f}^{\downarrow}(G)$ is the minimum $k\in\mathbb{N}$ such that there is a reduction sequence $G_{\_}n,G_{\_}{n-1},\dots,G_{\_}1$ of $G$ where $f(\widetilde{G}_{\_}i)\leqslant k$ for each $i\in\{1,\dots,n\}$ . So reduced maximum degree ${\Delta}^{\downarrow}$ is the same as twin-width.

Every graph has a reduction sequence in which every red graph is a star (just repeatedly identify the centre of the star with any other vertex). So it makes sense to consider graph properties that are unbounded on the class of all stars (such as maximum degree).

This line of research was initiated by Bonnet et al. [7], who considered the following parameter³³3Bonnet et al. [7] also considered the total number of edges in the red graph, but with a slightly different notion of reduction sequence in which red loops appear on identified vertices. The resulting parameter is called total twin-width.. Let $\star(G)$ be the maximum number of vertices in a connected component of a graph $G$ . Then ${\star}^{\downarrow}$ is called the component-twinwidth [7]; here the goal is to find a reduction sequence such that every red graph has small components. Bonnet et al. [9] proved that every graph $G$ satisfies ${\star}^{\downarrow}(G)\leqslant 2^{\operatorname{blw}(G)+1}$ , which implies ${\star}^{\downarrow}(G)\leqslant 2^{\operatorname{tw}(G)+2}$ and ${\star}^{\downarrow}(G)\leqslant 2^{\operatorname{cw}(G)+1}$ . Note that $\Delta(G)\leqslant\star(G)-1$ and thus ${\Delta}^{\downarrow}(G)\leqslant{\star}^{\downarrow}(G)-1$ .

Bonnet et al. [9] proved that every proper minor-closed graph class has bounded twin-width (amongst other results). The primary contribution of this paper is a qualitative strengthening of this result, where reduced maximum degree is replaced by reduced bandwidth. The bandwidth of a graph $G$ is the minimum $k\in\mathbb{N}_{\_}0$ such that there is an ordering $v_{\_}1,\dots,v_{\_}n$ of $V(G)$ satisfying $|i-j|\leqslant k$ for every edge $v_{\_}iv_{\_}j\in E(G)$ . We prove that every proper minor-closed class has bounded reduced bandwidth (Theorem 30).

Note that $\Delta(G)\leqslant 2\,\operatorname{bw}(G)$ , implying ${\Delta}^{\downarrow}(G)\leqslant 2\,{\operatorname{bw}}^{\downarrow}(G)$ . Thus, our upper bound on the reduced bandwidth of proper minor-closed classes implies the above-mentioned analogous result for twin-width, and indeed is qualitatively stronger since there are graph classes with bounded maximum degree and unbounded bandwidth. Complete binary trees are a simple example [14]. There are even trees with maximum degree 3, pathwidth 2, and unbounded bandwidth⁴⁴4 Let $Q_{\_}n$ be the tree consisting of disjoint paths $P_{\_}1,\dots,P_{\_}n$ , each with $n$ vertices, plus an edge joining the first vertex in $P_{\_}i$ and the first vertex in $P_{\_}{i+1}$ for each $i\in\{1,\dots,n-1\}$ . Observe that $Q_{\_}n$ has maximum degree 3, pathwidth 2, $n^{2}$ vertices, diameter less than $3n$ , and bandwidth at least $\frac{n}{3}$ (since $|V(G)|\leqslant\operatorname{bw}(G)\operatorname{diam}(G)+1$ for every graph $G$ ; see [14]).. Generally speaking, graphs with bounded bandwidth are considered to be particularly well-behaved. Indeed, every graph with bandwidth $k$ is a subgraph of the $k$ -th power of a path⁵⁵5For a graph $G$ and $r\in\mathbb{N}$ , the $r$ -th power of $G$ , denoted by $G^{r}$ , is the graph with vertex-set $V(G)$ where two vertices $u$ and $v$ are adjacent in $G^{r}$ if and only if the distance between $u$ and $v$ in $G$ is at most $r$ . The 2-nd power of $G$ is called the square of $G$ ..

In many cases, our results are also quantitatively stronger than previous bounds. The improvements for planar graphs are most significant. The previous proofs that planar graphs have bounded twin-width gave no explicit bounds, but it can be seen that all the previous bounds [7, 9] were at least $2^{1000}$ . We show that every planar graph has reduced bandwidth at most $466$ and twin-width at most $583$ . The proof method generalises for graphs embeddable on any surface⁶⁶6The Euler genus of a surface with $h$ handles and $c$ crosscaps is $2h+c$ . The Euler genus of a graph $G$ is the minimum Euler genus of a surface in which $G$ embeds without edge crossings. For $\gamma\in\mathbb{N}_{\_}0$ , the class of graphs of Euler genus at most $\gamma$ is a proper minor-closed class.. In particular, we show that every graph with Euler genus $\gamma$ has reduced bandwidth at most $164\gamma+466$ and twin-width at most $205\gamma+583$ (Theorems 23 and 23).

A key tool in our proofs are recent product structure theorems, which say that every graph of bounded Euler genus is a subgraph of the strong product of a graph with bounded treewidth and a path; see Section 2.3 for details. Our results hold for any graph class that has such a product structure, which includes several non-minor-closed graph classes. For example, a graph is $(\gamma,k)$ -planar if it has a drawing in a surface of Euler genus $\gamma$ such that every edge is involved in at most $k$ crossings (assuming no three edges cross at a single point) [16]. We prove that every $(\gamma,k)$ -planar graph has reduced bandwidth $2^{O(\gamma k)}$ (Theorem 25).

We also strengthen the above-mentioned results by showing that fixed powers of graphs in any proper minor-closed class have bounded reduced bandwidth (Theorem 30). Since FO-transductions preserve bounded twin-width [9, Section 8], it was previously known that these graphs have bounded twin-width. Note that powers of sparse graphs can be dense; for instance, $2$ -powers of stars are complete graphs. As an example of our results for graphs powers, we consider map graphs, which are well-studied generalisations of graphs embedded in surfaces. We prove that map graphs of Euler genus $\gamma$ have reduced bandwidth $O(\gamma^{4})$ . We emphasise there is no dependence on degree, and that these graphs might be dense.

Section 6 considers limitations of reduced bandwidth. We show that any infinite class of expander graphs excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth (Theorem 31). This result separates reduced bandwidth from twin-width, since Bonnet et al. [4] showed there are bounded-degree expanders (thus excluding a fixed complete bipartite subgraph) with twin-width at most 6. The theme of tied and separated parameters is continued in Section 7 where we show that the reduced versions of several natural parameters are separated. We conclude in Section 8 by presenting a number of open problems.

2 Preliminaries

Let $\mathbb{N}:=\{1,2,\dots\}$ and $\mathbb{N}_{\_}0:=\{0,1,\dots\}$ .

For a graph $G$ and $S\subseteq V(G)$ , let $G[S]$ be the induced subgraph of $G$ with vertex-set $S$ and edge-set $\{vw\in E(G):v,w\in S\}$ . For $F\subseteq E(G)$ , let $G-F$ be the graph obtained from $G$ by removing edges in $F$ . For two graphs $G$ and $H$ , let $G\cup H$ be the graph with vertex-set $V(G)\cup V(H)$ and edge-set $E(G)\cup E(H)$ . A clique in $G$ is a (possibly empty) set of pairwise adjacent vertices. For disjoint sets $S,T\subseteq V(G)$ , we say that $S$ is complete to $T$ in $G$ if every vertex in $S$ is adjacent to every vertex in $T$ .

For vertices $v,w\in V(G)$ , a $(v,w)$ -path in $G$ is a path with end-vertices $v$ and $w$ . For vertices $v,w\in V(G)$ , let $\operatorname{dist}_{\_}G(v,w)$ be the length of a shortest $(v,w)$ -path in $G$ . For a vertex $v$ in $G$ , let $N_{\_}G(v)$ $:=\{w\in V(G):vw\in E(G)\}$ and $N_{\_}G[v]$ $:=\{v\}\cup N_{\_}G(v)$ . Let $\deg_{\_}G(v)$ $:=|N_{\_}G(v)|$ , called the degree of $v$ in $G$ . For each $r\in\mathbb{N}$ , let $N^{r}_{\_}G[v]$ $:=\{w\in V(G):\operatorname{dist}_{\_}G(v,w)\leqslant r\}$ . For $S\subseteq V(G)$ , let $N_{\_}G(S)$ $:=\bigcup_{\_}{v\in S}N_{\_}G(v)\setminus S$ and $N_{\_}G[S]$ $:=\bigcup_{\_}{v\in S}N_{\_}G[v]$ .

For a vertex $v$ in a trigraph $G$ , let $N_{\_}G(v)$ $:=\{w\in V(G):vw\in E(G)\cup R(G)\}$ .

2.1 Tree-decompositions

A tree-decomposition of a graph $G$ is a pair $(T,\mathcal{B})$ consisting of a tree $T$ and a collection $\mathcal{B}=(B_{\_}x\subseteq V(G):x\in V(T))$ of subsets of $V(G)$ (called bags) indexed by the nodes of $T$ , such that:

(a)

for every edge $uv\in E(G)$ , some bag $B_{\_}x$ contains both $u$ and $v$ , and
(b)

for every vertex $v\in V(G)$ , the set $\{x\in V(T):v\in B_{\_}x\}$ induces a non-empty subtree of $T$ .

The width of a tree-decomposition is the size of the largest bag minus 1. The treewidth $\operatorname{tw}(G)$ of a graph $G$ is the minimum width of a tree-decomposition of $G$ . These definitions are due to Robertson and Seymour [42]. Treewidth is recognised as the most important measure of how similar a given graph is to a tree. Note that a connected graph with at least two vertices has treewidth 1 if and only if it is a tree. A path-decomposition is a tree-decomposition in which the underlying tree is a path. The pathwidth $\operatorname{pw}(G)$ of a graph $G$ is the minimum width of a path-decomposition of $G$ . It is well-known and easily proved that for every graph $G$ ,

\operatorname{tw}(G)\leqslant\operatorname{pw}(G)\leqslant\operatorname{bw}(G).

Let $(T,\mathcal{B}=(B_{\_}x:x\in V(T)))$ be a tree-decomposition of a graph $G$ . The torso of a bag $B_{\_}u$ is the subgraph obtained from $G[B_{\_}u]$ by adding, for each edge $uv\in E(T)$ , all edges $xy$ where $x$ and $y$ are distinct vertices in $B_{\_}u\cap B_{\_}v$ .

A separation of a graph $G$ is a pair $(A,B)$ of subsets of $V(G)$ such that $A\cup B=V(G)$ and there is no edge of $G$ between $A\setminus B$ and $B\setminus A$ .

We sometimes consider a tree-decomposition $(T,\mathcal{B}=(B_{\_}x:x\in V(T)))$ to be rooted at a specific root bag $B_{\_}r$ for some $r\in V(T)$ . In this case, for every node $t\neq r$ , let $t^{\prime}$ be the node of $T$ adjacent to $t$ in $T$ and on the $(r,t)$ -path in $T$ . We say that $B_{\_}{t^{\prime}}$ is the parent of $B_{\_}t$ and $B_{\_}t$ is a child of $B_{\_}{t^{\prime}}$ . A bag $B_{\_}x$ is a descendant of a bag $B_{\_}y$ if $y$ lies on the $(r,x)$ -path in $T$ .

Let $t$ be a node of $T$ , and let $\{t_{\_}1,\ldots,t_{\_}d\}$ be a set of children of $t$ . Let $C$ be the union of $B_{\_}t$ and every bag that is a descendant of $B_{\_}{t_{\_}i}$ for some $i\in\{1,2,\ldots,d\}$ . Let $D:=(V(G)\setminus C)\cup B_{\_}t$ . As illustrated in Figure 1, $(C,D)$ is a separation of $G$ with $C\cap D=B_{\_}t$ , said to be a rooted separation at $B_{\_}t$ and a rooted separation from $(T,\mathcal{B})$ .

Refer to caption — Figure 1: A rooted separation $(C,D)$ in a rooted tree-decomposition with root bag $B_{\_}r$ .

For a non-root degree-1 node $t$ of $T$ , we say that $B_{\_}t$ is a leaf bag; every other bag is said to be internal. Note that a root bag is always internal.

For $k,q\in\mathbb{N}$ with $q\geqslant k+1$ , a rooted tree-decomposition $(T,\mathcal{B})$ is $(k,q)$ -rooted if:

•

the root bag is empty,
•

every internal bag has at most $k+1$ vertices, and
•

for every leaf bag $B$ with parent $B^{\prime}$ , $\lvert B\setminus B^{\prime}\rvert\leqslant q$ .

A rooted tree-decomposition $(T,\mathcal{B})$ is $(k,\infty)$ -rooted if the root bag is empty, and every internal bag has at most $k+1$ vertices (so leaf bags can be arbitrarily large).

2.2 Sparsity

For $d\in\mathbb{N}_{\_}0$ , a graph $G$ is $d$ -degenerate if every subgraph of $G$ has minimum degree at most $d$ . The minimum such $d$ is the degeneracy of $G$ .

Kierstead and Yang [31] introduced the following definition. For a graph $G$ , total order $\preceq$ of $V(G)$ , vertex $v\in V(G)$ , and $s\in\mathbb{N}$ , let $\operatorname{reach}_{\_}s(G,\preceq,v)$ be the set of vertices $w\in V(G)$ for which there is a path $v=w_{\_}0,w_{\_}1,\dots,w_{\_}{s^{\prime}}=w$ of length $s^{\prime}\in\{0,\dots,s\}$ such that $w\preceq v$ and $v\prec w_{\_}i$ for all $i\in\{0,\dots,s^{\prime}-1\}$ . For a graph $G$ and $s\in\mathbb{N}$ , the $s$ -strong colouring number $\operatorname{col}_{\_}s(G)$ is the minimum integer $k$ for which there is a total order $\preceq$ of $V(G)$ with $|\operatorname{reach}_{\_}s(G,\preceq,v)|\leqslant k$ for every vertex $v$ of $G$ . Strong colouring numbers interpolate between degeneracy and treewidth [33]. Indeed, $\operatorname{col}_{\_}1(G)$ equals the degeneracy of $G$ plus 1. At the other extreme, Grohe et al. [25] showed that $\operatorname{col}_{\_}s(G)\leqslant\operatorname{tw}(G)+1$ for all $s\in\mathbb{N}$ , and indeed

\lim_{\_}{s\to\infty}\operatorname{col}_{\_}s(G)=\operatorname{tw}(G)+1.

Observe that a graph $H$ is a minor of a graph $G$ if and only if there are pairwise vertex-disjoint subtrees $(T_{\_}v)_{\_}{v\in V(H)}$ in $G$ such that for each edge $vw\in E(H)$ there is an edge between $T_{\_}v$ and $T_{\_}w$ in $G$ . For $r\in\mathbb{N}$ , if each such tree $T_{\_}v$ has radius at most $r$ , then $H$ is an $r$ -shallow minor of $G$ . Let

\nabla_{\_}r(G):=\max_{\_}H\frac{|E(H)|}{|V(H)|},

taken over all $r$ -shallow (non-empty) minors $H$ of $G$ . A graph class $\mathcal{G}$ has bounded expansion if there is a function $f:\mathbb{N}_{\_}0\to\mathbb{R}$ such that $\nabla_{\_}r(G)\leqslant f(r)$ for every graph $G\in\mathcal{G}$ and $r\in\mathbb{N}_{\_}0$ . A graph class $\mathcal{G}$ has linear or polynomial expansion respectively if there is a linear or polynomial expansion function.

2.3 Product Structure Theorems

For graphs $G$ and $H$ , the strong product $G\boxtimes H$ is the graph with vertex-set $V(G)\times V(H)$ , where vertices $(v,w)$ and $(x,y)$ are adjacent if:

•

$v=x$ and $wy\in E(H)$ , or
•

$w=y$ and $vx\in E(G)$ , or
•

$vx\in E(G)$ and $wy\in E(H)$ .

The proofs of our main theorems depend on the following recent product structure results. Bose et al. [11] defined the row-treewidth of a graph $G$ to be the minimum $k\in\mathbb{N}_{\_}0$ such that $G$ is isomorphic to a subgraph of $H\boxtimes P$ for some graph $H$ with treewidth $k$ and path $P$ . The motivation for this definition is the following ‘Planar Graph Product Structure Theorem’ of Dujmović et al. [17] (improved by Ueckerdt et al. [46]).

Theorem 1 ([17, 46]).

Every planar graph has row-treewidth at most 6.

Theorem 1 was generalised for graphs of given Euler genus.

Theorem 2 ([17, 46]).

Every graph of Euler genus $\gamma$ has row-treewidth at most $2\gamma+6$ .

More generally, Dujmović et al. [17] proved that a minor-closed class has bounded row-treewidth if and only if it excludes some apex graph⁷⁷7A graph $X$ is apex if $X-v$ is planar for some vertex $v$ .. For an arbitrary proper minor-closed class, Dujmović et al. [17] obtained by the following ‘Graph Minor Product Structure Theorem’, where $A+B$ is the complete join of graphs $A$ and $B$ (obtained from disjoint copies of $A$ and $B$ by adding every edge with one end-vertex in $A$ and one end-vertex in $B$ ).

Theorem 3 ([17]).

For every graph $X$ , there exist $k,a\in\mathbb{N}$ such that every $X$ -minor-free graph has a tree-decomposition in which every torso is a subgraph of $(H\boxtimes P)+K_{\_}a$ for some graph $H$ of treewidth at most $k$ and some path $P$ .

Product structure theorems for several non-minor-closed classes are known [18, 28]. Here is one example.

Theorem 4 ([18]).

Every $(\gamma,k)$ -planar graph has row-treewidth $O(\gamma k^{6})$ .

With these tools in hand we now give the intuition behind our proofs. First note that Bonnet et al. [4] showed that for all graphs $G$ and $H$ ,

\operatorname{tww}(G\boxtimes H)\leqslant\max\{\operatorname{tww}(G)(\Delta(H)+1)+2\Delta(H),\operatorname{tww}(H)+\Delta(H)\}.

However, this is not enough to conclude results about subgraphs of $G\boxtimes H$ since twin-width is not monotone. Consider a subgraph $G$ of $H\boxtimes P$ where $H$ has bounded tree-width and $P$ is a path. As mentioned in Section 1, $H$ has bounded component twin-width. This says there is a reduction sequence for $H$ such that each red component $X$ has bounded size. Observe that $X\boxtimes P$ has bounded bandwidth. Our strategy is to construct a reduction sequence for $G$ so that each red component is of the form $X\boxtimes P$ where $X$ is a bounded-size subgraph of $H$ , implying each red subgraph has bounded bandwidth. A key to the proof is to find vertex identifications so that the resulting graph stays a subgraph of some $H\boxtimes P$ . The above intuitive description has some inaccuracies. Implementing this strategy rigorously needs several further ideas, especially in the setting of powers (Section 4). Finally, to apply Theorem 3 for $K_{\_}t$ -minor-free graphs we need more ideas to cater for apex vertices and tree-decompositions (Section 5).

3 Neighbourhood Diversity

The following concept will help to optimise our bounds on reduced bandwidth and twin-width, and is of independent interest because of connections to VC-dimension [37, 22, 41] and sparsity theory [19, 41].

Fix a graph $G$ and $r\in\mathbb{N}$ . For vertices $v,w\in V(G)$ , let

\operatorname{dist}^{r}_{\_}G(v,w):=\begin{cases}\operatorname{dist}_{\_}G(v,w)&\text{if $\operatorname{dist}_{\_}G(v,w)\leqslant r$,}\\ \infty&\text{otherwise.}\end{cases}

For $A\subseteq V(G)$ and $v\in V(G)\setminus A$ , the distance- $r$ profile of $v$ on $A$ is

\pi^{r}_{\_}G(v,A):=\{(w,\operatorname{dist}^{r}_{\_}G(v,w)):w\in A\},

and the distance- $r$ diversity on $A$ is

\pi^{r}_{\_}G(A):=|\{\pi^{r}_{\_}G(v,A):v\in V(G)\setminus A\}|.

This definition is different to similar definitions in [19, 41] in that we only consider $v\in V(G)\setminus A$ . We use different notation to avoid confusion. Clearly, $\pi^{r}_{\_}G(A)\leqslant(r+1)^{|A|}$ .

Our upper bounds on reduced bandwidth and twin-width are expressed in terms of $\pi^{r}_{\_}G(A)$ for sets $A$ of a given size (see Lemma 20). Motivated by this connection, Section 3.1 presents various upper bounds on $\pi^{1}_{\_}G(A)$ that are tight for graphs of given Euler genus (Lemma 13) and $K_{\_}t$ -minor-free graphs (Corollary 11). Section 3.2 gives an upper bound on $\pi^{2}_{\_}G(A)$ where $G$ is a graph of given Euler genus.

3.1 First Neighbourhoods

This subsection presents bounds on $\pi^{1}_{\_}G(A)$ for various graphs $G$ . Note that

\pi^{1}_{\_}G(A)=|\{N_{\_}G(u)\cap A:u\in V(G)\setminus A\}|.

So in a monotone class, we may assume that $G$ is bipartite with bipartition $\{A,V(G)\setminus A\}$ , where $N_{\_}G(u)\cap X\neq N_{\_}G(v)\cap X$ for distinct $u,v\in V(G)\setminus A$ .

The following lemma is a more precise version of a result by Gajarský et al. [22] (see Lemma 7). For a graph $H$ and $k\in\mathbb{N}_{\_}0$ , let $C(H,k)$ be the number of cliques of order $k$ in $H$ , where $\emptyset$ is considered to be the only clique of order $0$ in $G$ . So $C(H,0)=1$ , $C(H,1)=|V(H)|$ , and $C(H,2)=|E(H)|$ . Let $C(H,\leqslant k)$ be the number of cliques of order at most $k$ in $H$ , and let $C(H)$ be the total number of cliques in $H$ .

Lemma 5.

Let $G$ be a bipartite graph with bipartition $\{X,Y\}$ , where $K_{\_}t$ is not a 1-shallow minor of $G$ . Then there is a 1-shallow minor $H$ of $G$ on $|X|$ vertices, such that

|\{N_{\_}G(u):u\in Y\}|\leqslant\begin{cases}C(H,\leqslant t-2)&\text{if }t\geqslant 4\\ C(H,\leqslant 2)&\text{if }t=3.\\ \end{cases}

Proof.

We may assume that $N_{\_}G(u)\neq N_{\_}G(v)$ for all distinct $u,v\in Y$ . For $i\in\mathbb{N}_{\_}0$ , let $Y_{\_}i:=\{v\in Y:\deg_{\_}G(v)=i\}$ . For each $v\in Y_{\_}2$ , let $X_{\_}v:=N_{\_}G(v)$ . By assumption, $X_{\_}v\neq X_{\_}w$ for distinct $v,w\in Y_{\_}2$ . Let $A$ be a maximal set such that:

•

$Y_{\_}2\subseteq A\subseteq Y\setminus(Y_{\_}0\cup Y_{\_}1)$ , and
•

for each $v\in A$ there exists $X_{\_}v\subseteq N_{\_}G(v)$ with $|X_{\_}v|=2$ where $X_{\_}v\neq X_{\_}w$ for all distinct $v,w\in A$ .

Let $H$ be the graph obtained from $G[X\cup A]$ , where for each $v\in A$ , we pick one $w\in X_{\_}v$ and contract the edge $vw$ . So $H$ is a 1-shallow minor of $G$ (with each branch set centred at a vertex in $X$ ), where $|X|=|V(H)|$ and $|A|=|E(H)|=C(H,2)$ .

Let $B:=Y\setminus(Y_{\_}0\cup Y_{\_}1\cup A)$ . Consider a vertex $w\in B$ with $d:=\deg_{\_}G(w)$ . So $d\geqslant 3$ since $Y_{\_}2\subseteq A$ . By the maximality of $A$ , we have $N_{\_}G(w)$ is a clique in $H$ , implying $K_{\_}{d+1}$ is a 1-shallow minor of $G$ . Thus $d\in\{3,4,\dots,t-2\}$ . For distinct $v,w\in B$ , we have $N_{\_}G(v)\neq N_{\_}G(w)$ . So $|B|\leqslant\sum_{\_}{i=3}^{t-2}C(H,i)$ , and $B=\emptyset$ if $t\leqslant 4$ .

Also $|Y_{\_}0|\leqslant 1=C(H,0)$ and $|Y_{\_}1|\leqslant|X|=C(H,1)$ . Therefore $|Y|=|Y_{\_}0|+|Y_{\_}1|+|A|+|B|\leqslant C(H,0)+C(H,1)+C(H,2)+|B|$ . If $t\leqslant 4$ then $B=\emptyset$ and $|Y|\leqslant C(H,\leqslant 2)$ ; otherwise $|Y|\leqslant C(H,0)+C(H,1)+C(H,2)+\sum_{\_}{i=3}^{t-2}C(H,i)=C(H,\leqslant t-2)$ . ∎

It is well known (see [48, 49]) that every $d$ -degenerate graph $G$ with $n\geqslant d$ vertices satisfies:

•

$C(G,k)\leqslant\binom{d}{k-1}(n-\frac{(k-1)(d+1)}{k})$ for all $k\in\{0,1,\dots,d+1\}$ ,
•

$C(G)\leqslant 2^{d}(n-d+1)$ .

So Lemma 5 implies:

Corollary 6.

For every graph $G$ and set $A\subseteq V(G)$ , if every 1-shallow minor of $G$ on $|A|$ vertices is $d$ -degenerate, then $\pi^{1}_{\_}G(A)\leqslant\min\{2^{d}(|A|-d+1),2^{|A|}\}$ .

Corollary 6 is applicable with $d=\lfloor 2\nabla_{\_}1(G)\rfloor$ since every 1-shallow minor of a graph $G$ is $\lfloor 2\nabla_{\_}1(G)\rfloor$ -degenerate. We obtain the following lemma, which is a slight strengthening of a result of Gajarský et al. [22, Lemma 4.3].

Lemma 7.

For every graph $G$ with $\nabla_{\_}1(G)\leqslant k$ and for every set $A\subseteq V(G)$ ,

\pi^{1}_{\_}G(A)\leqslant\min\{2^{\lfloor 2k\rfloor}(|A|-\lfloor 2k\rfloor+1),2^{|A|}\}.

Lemma 8.

For every graph $G$ with $\operatorname{col}_{\_}5(G)\leqslant c$ and for every set $A\subseteq V(G)$ ,

\pi^{1}_{\_}G(A)\leqslant\min\{2^{c-1}(|A|-c+2),2^{|A|}\}.

Proof.

Hickingbotham and Wood [28, Lemma 20] proved that for every graph $G$ and every $r$ -shallow minor $G^{\prime}$ of $G$ , we have $\operatorname{col}_{\_}s(G^{\prime})\leqslant\operatorname{col}_{\_}{2rs+2r+s}(G)$ . Every graph $G$ is $(\operatorname{col}_{\_}1(G)-1)$ -degenerate. Thus every 1-shallow minor of a graph $G$ is $(\operatorname{col}_{\_}5(G)-1)$ -degenerate. The result follows from Corollary 6. ∎

Lemma 9.

For every $(\gamma,k)$ -planar graph $G$ and for every set $A\subseteq V(G)$ ,

\pi^{1}_{\_}G(A)\leqslant\min\{2^{22(2\gamma+3)(k+1)-1}(|A|-22(2\gamma+3)(k+1)+2),2^{|A|}\}.

Proof.

Van den Heuvel and Wood [47] proved that $\operatorname{col}_{\_}s(G)\leqslant 2(2\gamma+3)(k+1)(2s+1)$ . The result follows from Lemma 8. ∎

Lemma 10.

For every graph $G$ with row-treewidth at most $k$ and for every set $A\subseteq V(G)$ ,

\pi^{1}_{\_}G(A)\leqslant\min\{2^{11k+10}(|A|-11k-9),2^{|A|}\}.

Proof.

By assumption, $G$ is isomorphic to a subgraph of $H\boxtimes P$ , where $\operatorname{tw}(H)\leqslant k$ and $P$ is a path. Hickingbotham and Wood [28, Lemma 22] showed that

\operatorname{col}_{\_}s(H\boxtimes P)\leqslant(2s+1)\operatorname{col}_{\_}s(H)\leqslant(2s+1)(\operatorname{tw}(H)+1).

In particular, $\operatorname{col}_{\_}5(G)\leqslant\operatorname{col}_{\_}5(H\boxtimes P)\leqslant 11(k+1)$ . The result follows from Lemma 8. ∎

We get improved bounds for minor-closed classes. For every $n$ -vertex $K_{\_}t$ -minor-free graph $G$ , Kostochka [32] and Thomason [45] independently showed that $G$ has $O(t\sqrt{\log t}\,|V(G)|)$ edges, and Fox and Wei [21] showed that $G$ has at most $3^{2t/3+o(t)}|V(G)|$ cliques. Lemma 5 implies:

Corollary 11.

For every $K_{\_}t$ -minor-free graph $G$ and for every set $A\subseteq V(G)$ ,

\pi^{1}_{\_}G(A)\leqslant 3^{2t/3+o(t)}|A|+1.

We now show that this bound is tight up to the $o(t)$ term. We may assume $2t=3p+2$ for some even $p\in\mathbb{N}$ . Let $H$ be the complete $p$ -partite graph $K_{\_}{2,\dots,2}$ , which can be obtained from $K_{\_}{2p}$ by deleting a perfect matching $v_{\_}1w_{\_}1,\dots,v_{\_}pw_{\_}p$ . Obviously, the largest complete subgraph in $H$ is $K_{\_}p$ . Wood [48] showed that the largest complete graph minor in $H$ is $K_{\_}{3p/2}$ (with branch sets $\{v_{\_}1\},\dots,\{v_{\_}p\},\{w_{\_}1,w_{\_}2\},\dots,\{w_{\_}{p-1},w_{\_}p\}$ ). So $H$ is $K_{\_}t$ -minor-free (since $t>\frac{3}{2}p$ ). It is well known that $H$ has exactly $3^{p}$ cliques (since if $C_{\_}i$ is any element of $\{\emptyset,\{v_{\_}i\},\{w_{\_}i\}\}$ , then $C_{\_}1\cup\dots\cup C_{\_}p$ is a clique, giving $3^{p}$ cliques in total, and every clique in $H$ is obtained this way). Let $G$ be the bipartite graph with bipartition $\{X,Y\}$ , where $X=V(H)$ and for each clique $C$ in $H$ , there is a one vertex $y_{\_}C$ in $Y$ with $N_{\_}G(y_{\_}C)=C$ . So $G$ can be obtained from $H$ by clique-sums with complete graphs of order at most $p+1$ (and edge-deletions). So $G$ is also $K_{\_}t$ -minor-free, and every vertex in $Y$ has a unique neighbourhood. Thus $\pi^{1}_{\_}G(X)=|Y|=3^{p}=3^{(2t-2)/3}=3^{2t/3-O(\log t)}|X|$ .

Corollary 12.

For every graph $G$ with treewidth $k\in\mathbb{N}$ and for every set $A\subseteq V(G)$ ,

\pi^{1}_{\_}G(X)\leqslant\begin{cases}2|A|&\text{if }k=1\\ 2^{|A|}&\text{if }k\geqslant 2\text{ and }|A|\leqslant k\\ (2^{k}-1)(|A|-k)+2^{k}&\text{if }k\geqslant 2\text{ and }|A|\geqslant k\\ \end{cases}

Proof.

Let $Y:=V(G)\setminus A$ . First suppose that $k=1$ . So $G$ and every minor of $G$ is a forest. So Lemma 5 is applicable with $t=3$ . Thus, there is a minor $H$ of $G$ on $|A|$ vertices, such that $\pi^{1}_{\_}G(A)=|\{N_{\_}G(u)\cap A:u\in Y\}|\leqslant C(H)\leqslant 2|A|$ since $H$ is a forest.

Now assume that $k\geqslant 2$ . The class of treewidth- $k$ graphs is proper minor-closed and has no $K_{\_}{k+2}$ minor. So Lemma 5 is applicable with $t=k+2\geqslant 4$ . Thus there is a minor $H$ of $G$ on $|A|$ vertices, such that $|\{N_{\_}G(u):u\in Y\}|\leqslant C(H,\leqslant k)$ . This is at most $2^{|A|}$ if $|A|\leqslant k$ . Now assume that $|A|\geqslant k+1$ . Every graph with treewidth at most $k$ is $k$ -degenerate. So $H$ is $k$ -degenerate, implying

\pi^{1}_{\_}G(A)=|\{N_{\_}G(u):u\in Y\}|\leqslant\sum_{\_}{i=0}^{k}\tbinom{k}{i-1}\big{(}|A|-\tfrac{(i-1)(k+1)}{i}\big{)}=2^{k}(|A|-k+1)-|A|+k.\qed

The bound in Corollary 12 is tight: Let $H$ be a $k$ -tree on $n\geqslant k$ vertices, which has $2^{k}(n-k+1)$ cliques and $n-k$ cliques of size $k+1$ [49]. Let $G$ be the bipartite graph with bipartition $\{X,Y\}$ , where $X=V(H)$ and for each clique $C$ with $|C|\leqslant k$ in $H$ , there is a one vertex $y_{\_}C$ in $Y$ with $N_{\_}G(y_{\_}C)=C$ . So $|Y|=C(H,\leqslant k)=2^{k}(n-k+1)-n+k$ . Given a tree-decomposition of $H$ with width $k$ , for each clique $C$ in $H$ with $|C|\leqslant k$ , which must be in some bag $B$ , add one new bag $B^{\prime}=B\cup\{y_{\_}C\}$ adjacent to $B$ to obtain a tree-decomposition of $G$ with width $k$ .

We have the following bound for graphs of given Euler genus. It follows from Euler’s formula that $|E(G)|\leqslant 3(|V(G)|+\gamma-2)$ for every graph $G$ with Euler genus $\gamma$ ; moreover, $|E(G)|\leqslant 2(|V(G)|+\gamma-2)$ if $G$ is bipartite.

Lemma 13.

For every graph $G$ with Euler genus $\gamma$ and for every set $X\subseteq V(G)$ with $|X|\geqslant 2$ ,

\pi^{1}_{\_}G(X)\leqslant 6|X|+5\gamma-9.

Proof.

We may assume that $G$ is bipartite with bipartition $\{X,Y\}$ , and that $N_{\_}G(u)\neq N_{\_}G(v)$ for distinct $u,v\in Y$ (otherwise delete one of the vertices). For $i\in\mathbb{N}_{\_}0$ , let $Y_{\_}i:=\{u\in Y:\deg_{\_}G(u)=i\}$ . Let $G^{\prime}:=G-Y_{\_}0-Y_{\_}1$ . Since $G^{\prime}$ is bipartite,

|E(G)|-|Y_{\_}1|=|E(G^{\prime})|\leqslant 2(|V(G^{\prime})|+\gamma-2)=2(|V(G)|-|Y_{\_}0|-|Y_{\_}1|+\gamma-2).

Thus

\sum_{\_}{i\geqslant 0}i|Y_{\_}i|=|E(G)|\leqslant 2|V(G)|-2|Y_{\_}0|-|Y_{\_}1|+2\gamma-4=2\Big{(}|X|+\sum_{\_}{i\geqslant 0}|Y_{\_}i|\Big{)}-2|Y_{\_}0|-|Y_{\_}1|+2\gamma-4.

Hence

|Y|-|Y_{\_}0|-|Y_{\_}1|-|Y_{\_}2|=\sum_{\_}{i\geqslant 3}|Y_{\_}i|\leqslant\sum_{\_}{i\geqslant 3}(i-2)|Y_{\_}i|\leqslant 2|X|+2\gamma-4,

implying $|Y|\leqslant 2|X|+|Y_{\_}0|+|Y_{\_}1|+|Y_{\_}2|+2\gamma-4$ . Since $N_{\_}G(u)\neq N_{\_}G(v)$ for distinct $u,v\in Y$ , we have $|Y_{\_}0|\leqslant 1$ and $|Y_{\_}1|\leqslant|X|$ . If $H$ is obtained from $G[X\cup Y_{\_}2]$ by contracting one edge incident to each vertex in $Y_{\_}2$ , then $H$ has no parallel edges and $|X|$ vertices, implying $|Y_{\_}2|=|E(H)|\leqslant 3(|X|+\gamma-2)$ . Hence

|Y|\leqslant 2|X|+1+|X|+3(|X|+\gamma-2)+2\gamma-4=6|X|+5\gamma-9.\qed

Lemma 13 is also tight: Let $G_{\_}0$ be a triangulation of a surface with Euler genus $\gamma$ with at least four vertices. Let $G$ be obtained from $G_{\_}0$ as follows: add one vertex adjacent to the three vertices of each face of $G_{\_}0$ , subdivide each edge of $G_{\_}0$ , add one vertex adjacent to each vertex of $G_{\_}0$ , and add one isolated vertex. So $G$ is bipartite with bipartition $\{X,Y\}$ where $X:=V(G_{\_}0)$ and $Y:=V(G)\setminus X$ . No two vertices in $Y$ have the same neighbourhood, and $|Y|=|Y_{\_}0|+|Y_{\_}1|+|Y_{\_}2|+|Y_{\_}3|=1+|X|+3(|X|+\gamma-2)+2(|X|+\gamma-2)=6|X|+5\gamma-9$ .

3.2 Second Neighbourhoods

This section gives bounds on the second neighbourhood diversity in graphs of given Euler genus. These results are useful for bounding the reduced bandwidth of squares and map graphs.

Lemma 14.

Let $G$ be a graph of Euler genus $\gamma$ , and let $X\subseteq V(G)$ with $|X|\geqslant 2$ . Let $Y:=N_{\_}G(X)$ and $Z:=V(G)\setminus(X\cup Y)$ . Then

|\{N^{2}_{\_}G(v)\cap X:v\in Z\}|\leqslant(60\gamma^{2}+125\gamma+68)|X|-120\gamma^{2}-250\gamma-132.

Proof.

We may assume that $N^{2}_{\_}G(v)\cap X\neq N^{2}_{\_}G(w)\cap X$ for all distinct $v,w\in Z$ . Let $Z^{0}:=\{v\in Z:|N^{2}_{\_}G(v)\cap X|=0\}$ and $Z^{1}:=\{v\in Z:|N^{2}_{\_}G(v)\cap X|=1\}$ and $Z^{2}:=\{v\in Z:|N^{2}_{\_}G(v)\cap X|\geqslant 2\}$ . Thus $|Z^{0}|\leqslant 1$ and $|Z^{1}|\leqslant|X|$ . By Lemma 16 below, $|Z^{2}|\leqslant(60\gamma^{2}+125\gamma+67)(|X|-2)+1$ . In total, $|Z|\leqslant(60\gamma^{2}+125\gamma+67)(|X|-2)+|X|+2=(60\gamma^{2}+125\gamma+68)|X|-120\gamma^{2}-250\gamma-132$ , as desired. ∎

The proof of Lemma 16 uses the next lemma, which follows from [35, Proposition 4.2.7] and the discussion after it.

Lemma 15.

If $K_{\_}{2,2\gamma+2}$ is embedded in a surface of Euler genus $\gamma$ , then some 4-cycle in $K_{\_}{2,2\gamma+2}$ is contractible.

Lemma 16.

Let $G$ be a graph of Euler genus $\gamma$ , and let $X\subseteq V(G)$ with $|X|\geqslant 2$ . Let $Y:=N_{\_}G(X)$ and $Z:=V(G)\setminus(X\cup Y)$ . Assume that $|N^{2}_{\_}G(v)\cap X|\geqslant 2$ for every vertex $v\in Z$ , and that $N^{2}_{\_}G(v)\cap X\neq N^{2}_{\_}G(w)\cap X$ for all distinct $v,w\in Z$ . Then $|Z|\leqslant(60\gamma^{2}+125\gamma+67)(|X|-2)+1$ .

Proof.

We prove that $|Z|\leqslant c(|X|-2)+1$ by induction on $|Y|$ , where $c:=60\gamma^{2}+125\gamma+67$ . (This choice of $c$ will become clear at the end of the proof.) In the base case, if $|X|=2$ then $|Z|\leqslant 1=c(|X|-2)+1$ . Now assume that $|X|\geqslant 3$ . We may assume that each of $X$ , $Y$ and $Z$ are independent sets.

First suppose that there is a set $Y_{\_}0\subseteq Y$ and distinct vertices $x_{\_}1,x_{\_}2\in X$ such that $|Y_{\_}0|\geqslant 2\gamma+2$ and $N_{\_}G(y)\cap X=\{x_{\_}1,x_{\_}2\}$ for each $y\in Y$ . Thus $G[\{x_{\_}1,x_{\_}2\}\cup Y_{\_}0]$ contains a $K_{\_}{2,2\gamma+2}$ subgraph. By Lemma 15, there is a contractible 4-cycle $C=(x_{\_}1,y_{\_}1,x_{\_}2,y_{\_}2)$ in $G$ , for some $y_{\_}1,y_{\_}2\in Y_{\_}0$ .

Thus $G=G_{\_}1\cup G_{\_}2$ for some induced subgraphs $G_{\_}1$ and $G_{\_}2$ of $G$ with $G_{\_}1\cap G_{\_}2=C$ , where $C$ is the boundary of a face of both $G_{\_}1$ and $G_{\_}2$ . Let $G^{\prime}$ be the graph obtained from $G_{\_}1$ by identifying $y_{\_}1$ and $y_{\_}2$ into a vertex $y^{\prime}$ . Let $G^{\prime\prime}$ be the graph obtained from $G_{\_}2$ by identifying $y_{\_}1$ and $y_{\_}2$ into a vertex $y^{\prime\prime}$ . Since $y_{\_}1$ and $y_{\_}2$ are on a common face before their identification, $G^{\prime}$ and $G^{\prime\prime}$ have Euler genus at most $g$ .

Let $X^{\prime}:=V(G^{\prime})\cap X$ and $X^{\prime\prime}:=V(G^{\prime\prime})\cap X$ . Note that $X^{\prime}\cap X^{\prime\prime}=\{x_{\_}1,x_{\_}2\}$ . Let $Y^{\prime}:=(V(G^{\prime})\cap Y)\cup\{y^{\prime}\}$ and $Y^{\prime\prime}:=(V(G^{\prime\prime})\cap Y)\cup\{y^{\prime\prime}\}$ . Note that $|Y^{\prime}|<|Y|$ and $|Y^{\prime\prime}|<|Y|$ . Let $Z^{\prime}:=V(G^{\prime})\cap Z$ and $Z^{\prime\prime}:=V(G^{\prime\prime})\cap Z$ . Note that $Z^{\prime}$ and $Z^{\prime\prime}$ partition $Z$ .

We claim that $|N^{2}_{\_}{G^{\prime}}(v)\cap X^{\prime}|\geqslant 2$ for each $v\in Z^{\prime}$ . Suppose that $|N^{2}_{\_}{G^{\prime}}(v)\cap X^{\prime}|\leqslant 1$ . Then there is a vertex from $N^{2}_{\_}G(v)\cap X$ in $G^{\prime\prime}-V(G^{\prime})$ . Since $C$ is separating, $v$ is adjacent to $y_{\_}1$ or $y_{\_}2$ in $G$ , implying $x_{\_}1,x_{\_}2\in N^{2}_{\_}{G^{\prime}}(v)$ and $|N^{2}_{\_}{G^{\prime}}(v)\cap X^{\prime}|\geqslant 2$ , as desired. Similarly, $|N^{2}_{\_}{G^{\prime\prime}}(v)\cap X^{\prime\prime}|\geqslant 2$ for each $v\in Z^{\prime\prime}$ .

Since $N_{\_}{G^{\prime}}(y^{\prime})\cap X^{\prime}=N_{\_}G(y_{\_}1)\cap X=N_{\_}G(y_{\_}2)\cap X=\{x_{\_}1,x_{\_}2\}$ , we have $N^{2}_{\_}{G^{\prime}}(v)\cap X^{\prime}=N^{2}_{\_}G(v)\cap X$ for every $v\in Z^{\prime}$ . Hence $N^{2}_{\_}{G^{\prime}}(v)\cap X^{\prime}\neq N^{2}_{\_}{G^{\prime}}(w)\cap X^{\prime}$ for distinct vertices $v,w\in Z^{\prime}$ . Similarly, $N^{2}_{\_}{G^{\prime\prime}}(v)\cap X^{\prime\prime}\neq N^{2}_{\_}{G^{\prime\prime}}(w)\cap X^{\prime\prime}$ for distinct vertices $v,w\in Z^{\prime\prime}$ .

By assumption, there is at most one vertex $v\in Z$ with $N^{2}_{\_}G(v)\cap X=N_{\_}G(y_{\_}1)\cap X$ . Without loss of generality, if such a vertex $v$ exists, then $v$ is not in $Z^{\prime\prime}$ . Add a new vertex $z$ to $Z^{\prime\prime}$ and to $G^{\prime\prime}$ only adjacent to $y^{\prime\prime}$ in $G^{\prime\prime}$ . Then $x_{\_}1,x_{\_}2\in N^{2}_{\_}{G^{\prime\prime}}(z)\cap X^{\prime\prime}$ and $|N^{2}_{\_}{G^{\prime\prime}}(z)\cap X^{\prime\prime}|\geqslant 2$ as required. If $N^{2}_{\_}{G^{\prime\prime}}(z)\cap X^{\prime\prime}=N^{2}_{\_}{G^{\prime\prime}}(v)\cap X^{\prime\prime}$ for some vertex $v\in Z^{\prime\prime}\setminus\{z\}$ , then $N^{2}_{\_}{G^{\prime\prime}}(v)\cap X^{\prime\prime}=N^{2}_{\_}{G^{\prime\prime}}(z)\cap X^{\prime\prime}=N_{\_}G(y_{\_}1)$ , which contradicts the above property of $Z^{\prime\prime}$ . Hence $N^{2}_{\_}{G^{\prime\prime}}(z)\cap X^{\prime\prime}\neq N^{2}_{\_}{G^{\prime\prime}}(v)\cap X^{\prime\prime}$ for every vertex $v\in Z^{\prime\prime}\setminus\{z\}$ .

Now $|Z_{\_}1|+|Z_{\_}2|=|Z|+1$ . We have shown that $X^{\prime}$ , $Y^{\prime}$ and $Z^{\prime}$ satisfy the assumptions of the inductive hypothesis within $G^{\prime}$ . Since $|Y^{\prime}|<|Y|$ , by induction, $|Z^{\prime}|\leqslant c(|X^{\prime}|-2)+1$ . Similarly, $|Z^{\prime\prime}|\leqslant c(|X^{\prime\prime}|-2)+1$ . Hence

	$\displaystyle\|Z\|\,=\,\|Z^{\prime}\|+\|Z^{\prime\prime}\|-1$	$\displaystyle\leqslant c(\|X^{\prime}\|-2)+1+c(\|X^{\prime\prime}\|-2)+1-1$
		$\displaystyle=c(\|X^{\prime}\|+\|X^{\prime\prime}\|-4)+1$
		$\displaystyle=c(\|X\|-2)+1,$

as desired. Now assume that there are no such vertices $x_{\_}1,x_{\_}2\in X$ and set $Y_{\_}0$ .

As illustrated in Figure 2, let $Y^{1}$ be the set of vertices in $Y$ with exactly one neighbour in $X$ . Let $Y^{1}_{\_}1,\dots,Y^{1}_{\_}p$ be the partition of $Y^{1}$ , where for all $v\in Y^{1}_{\_}i$ and $w\in Y^{1}_{\_}j$ we have $N_{\_}G(v)\cap X=N_{\_}G(w)\cap X$ if and only if $i=j$ . Let $y^{1}_{\_}i$ be a vertex in $Y^{1}_{\_}i$ and let $x_{\_}i$ be the neighbour of $y^{1}_{\_}i$ in $X$ .

Let $Y^{2}$ be the set of vertices in $Y$ with exactly two neighbours in $X$ . Let $Y^{2}_{\_}1,\dots,Y^{2}_{\_}q$ be the partition of $Y^{2}$ , where for all $v\in Y^{2}_{\_}i$ and $w\in Y^{2}_{\_}j$ we have $N_{\_}G(v)\cap X=N_{\_}G(w)\cap X$ if and only if $i=j$ . As shown above, $|Y^{2}_{\_}i|\leqslant 2\gamma+1$ for each $i\in\{1,\dots,q\}$ . Let $y^{2}_{\_}i$ be a vertex in $Y^{2}_{\_}i$ .

Let $Y^{3}$ be the set of vertices in $Y$ with at least three neighbours in $X$ . Let $Y^{3}_{\_}1,\dots,Y^{3}_{\_}r$ be the partition of $Y^{3}$ , where for all $v\in Y^{3}_{\_}i$ and $w\in Y^{3}_{\_}j$ we have $N_{\_}G(v)\cap X=N_{\_}G(w)\cap X$ if and only if $i=j$ . Since $K_{\_}{3,2\gamma+3}$ has Euler genus greater than $\gamma$ , $|Y^{3}_{\_}i|\leqslant 2\gamma+2$ and $|Y^{3}|\leqslant(2\gamma+2)r$ . Let $y^{3}_{\_}i$ be a vertex in $Y^{3}_{\_}i$ .

By construction, the vertices $y^{1}_{\_}1,\dots,y^{1}_{\_}p,y^{2}_{\_}1,\dots,y^{2}_{\_}q,y^{3}_{\_}1,\dots,y^{3}_{\_}r$ have pairwise distinct non-empty neighbourhoods in $X$ . By Lemma 13 applied to the bipartite graph between $X$ and $\{y^{1}_{\_}1,\dots,y^{1}_{\_}p,y^{2}_{\_}1,\dots,y^{2}_{\_}q,y^{3}_{\_}1,\dots,y^{3}_{\_}r\}$ , we have $p+q+r\leqslant(6|X|+5\gamma-9)-1=6|X|+5\gamma-10$ . In fact, $p\leqslant|X|$ and $q+r\leqslant 5|X|+5\gamma-10$ .

Let $H$ be the graph obtained from $G$ as follows: delete $X\setminus\{x_{\_}1,\dots,x_{\_}p\}$ , delete any edges between $\{x_{\_}1,\dots,x_{\_}p\}$ and $Y^{2}\cup Y^{3}$ , and for each $i\in\{1,\dots,p\}$ contract $\{x_{\_}i\}\cup Y^{1}_{\_}i$ (which induces a star) into a new vertex $h_{\_}i$ . Note that $H$ is bipartite and planar, with one colour class $Z$ and the other colour class $\{h_{\_}1,\dots,h_{\_}p\}\cup Y^{2}\cup Y^{3}$ , which has size at most

p+|Y^{2}|+|Y^{3}|\leqslant p+(2\gamma+1)q+(2\gamma+2)r\leqslant p+(2\gamma+2)(q+r)\leqslant|X|+(2\gamma+2)(5|X|+5\gamma-10).

For each $v\in Z$ ,

N^{2}_{\_}G(v)\cap X=\{x_{\_}i:h_{\_}i\in N_{\_}H(v)\}\cup\Big{(}\bigcup_{\_}{u\in N_{\_}H(v)\setminus\{h_{\_}1,\dots,h_{\_}p\}}\!\!\!\!\!\!\!\!\!\!\!\!N_{\_}G(u)\cap X\Big{)}.

Thus $N^{2}_{\_}G(v)\cap X$ is determined by $N_{\_}H(v)$ . For all distinct $v,w\in Z$ , since $N^{2}_{\_}G(v)\cap X\neq N^{2}_{\_}G(w)\cap X$ , we have $N_{\_}H(v)\neq N_{\_}H(w)$ . By Lemma 13 applied to $H$ ,

|Z|\leqslant 6(p+|Y^{2}|+|Y^{3}|)+5\gamma-10\leqslant 6\big{(}|X|+(2\gamma+2)(5|X|+5\gamma-10)\big{)}+5\gamma-10\leqslant c(|X|-2)+1,

since $|X|\geqslant 3$ . Indeed, $c$ is defined so that this final inequality holds. ∎

Lemma 17.

Let $f:\mathbb{N}\to\mathbb{N}$ be a function and let $\mathcal{G}$ be a monotone class, such that for every $G\in\mathcal{G}$ and $X\subseteq V(G)$ and $Z\subseteq V(G)\setminus N_{\_}G[X]$ ,

|\{N^{2}_{\_}G(v)\cap X:v\in Z\}|\leqslant f(|X|).

Then $\pi^{2}_{\_}G(X)\leqslant\pi^{1}_{\_}G(X)\,f(|X|)$ .

Proof.

Let $s:=\pi^{1}_{\_}G(X)$ and $t:=f(|X|)$ . Let $Y:=V(G)\setminus X$ . Let $Y_{\_}1,\dots,Y_{\_}s$ be a partition of $Y$ where $v,w\in Y_{\_}i$ if and only if $N_{\_}G(v)\cap X=N_{\_}G(w)\cap X$ . For each $i\in\{1,\ldots,s\}$ , let $G_{\_}i$ be the graph obtained from $G$ by deleting the edges between $Y_{\_}i$ and $X$ . Since $\mathcal{G}$ is monotone, $G_{\_}i\in\mathcal{G}$ , implying $|\{N^{2}_{\_}{G_{\_}i}(v)\cap X:v\in Y_{\_}i\}|\leqslant t$ . Let $Y_{\_}{i,1},\dots,Y_{\_}{i,t}$ be a partition of $Y_{\_}i$ where $v,w\in Y_{\_}{i,j}$ if and only if $N^{2}_{\_}{G_{\_}i}(v)\cap X=N^{2}_{\_}{G_{\_}i}(w)\cap X$ . It follows that for each $i\in\{1,\ldots,s\}$ and $j\in\{1,\ldots,t\}$ , we have $\pi_{\_}2^{G}(v,X)=\pi_{\_}2^{G}(w,X)$ for all $v,w\in Y_{\_}{i,j}$ . Thus $\pi^{2}_{\_}G(X)\leqslant st$ , as desired. ∎

Lemmas 13, 14 and 17 imply the following bound on $\pi^{2}_{\_}G$ for graphs of given Euler genus.

Corollary 18.

For every graph $G$ of Euler genus $\gamma$ and for every set $X\subseteq V(G)$ with $|X|\geqslant 2$ ,

\pi^{2}_{\_}G(X)\leqslant(6|X|+5\gamma-9)((60\gamma^{2}+125\gamma+68)|X|-120\gamma^{2}-250\gamma-132).

4 Bounded Row Treewidth Classes

This section presents upper bounds on reduced bandwidth and twin-width for powers of graphs with bounded row-treewidth, which includes planar graphs, graphs with Euler genus $\gamma$ , $(\gamma,k)$ -planar graphs, and map graphs. The heart of the proof is Lemma 19 below, which depends on the following definition. As illustrated in Figure 3, for $x,q\in\mathbb{N}$ with $q\geqslant 2$ , let $S^{*}_{\_}{x,q}$ be the graph where:

•

$V(S^{*}_{\_}{x,q})$ is the disjoint union of sets $Q,A_{\_}1,\dots,A_{\_}x,B_{\_}1,\dots,B_{\_}x,C_{\_}1,\dots,C_{\_}x$ with $|Q|=2q-1$ and $|A_{\_}i|=|B_{\_}i|=|C_{\_}i|=q$ for all $i\in\{1,\dots,x\}$ , and
•

$Q\cup A_{\_}1$ is a clique, $Q\cup B_{\_}1$ is a clique, $Q\cup C_{\_}1$ is a clique, and for all $\in\{1,\dots,x-1\}$ , $A_{\_}i\cup A_{\_}{i+1}$ is a clique, $B_{\_}i\cup B_{\_}{i+1}$ is a clique, and $C_{\_}i\cup C_{\_}{i+1}$ is a clique.

For $x,q,r\in\mathbb{N}$ with $q\geqslant 2$ , let $S_{\_}{x,q,r}$ be the graph obtained from $(S^{*}_{\_}{x,q})^{r}$ by removing all edges between $B_{\_}1\cup\dots\cup B_{\_}x$ and $C_{\_}1\cup\dots\cup C_{\_}x$ . We call $Q$ the center of $S_{\_}{x,q,r}$ . Note that the vertices in $Q$ have maximum degree in $S_{\_}{x,q,r}$ . Thus

\Delta(S_{\_}{x,q,r})\leqslant(3r+2)q-2.

(1)

Considering the vertex-ordering $A_{\_}x,A_{\_}{x-1},\dots,A_{\_}1,Q,B_{\_}1,C_{\_}1,B_{\_}2,C_{\_}2,\dots,B_{\_}x,C_{\_}x$ we see that

\operatorname{bw}(S_{\_}{x,q,r})\leqslant|Q|+\sum_{\_}{i=1}^{r}(|B_{\_}i|+|C_{\_}i|)-1=(2q-1)+2qr-1=(2r+2)q-2.

(2)

Lemma 19.

Let $k,q,r\in\mathbb{N}$ with $q\geqslant k+1$ . Let $f$ be a monotone and union-closed graph parameter and let $g:\mathbb{N}\times\mathbb{N}\to\mathbb{R}$ be a function such that $f(S_{\_}{x,q,r})\leqslant g(q,r)$ for all $x\in\mathbb{N}$ . Let $P$ be a path and let $H$ be a graph admitting a $(k,q)$ -rooted tree-decomposition $(T,\mathcal{B})$ . Let $F$ be a trigraph with $V(F)\subseteq V(H\boxtimes P)$ such that:

•

(red edge condition) for every red edge $vw$ of $F$ , there is a leaf bag $B$ with parent $B^{\prime}$ in $(T,\mathcal{B})$ such that $v,w\in(B\setminus B^{\prime})\times V(P)$ ;
•

(separation condition) for every rooted separation $(C,D)$ of $H$ from $(T,\mathcal{B})$ and every $z\in V(P)$ , we have $\left|\left\{N_{\_}{F}(v)\cap(D\times V(P)):v\in((C\setminus D)\times\{z\})\cap V(F)\right\}\right|\leqslant q$ ; and
•

(neighbourhood condition) for every $z\in V(P)$ and $v\in(V(H)\times\{z\})\cap V(F)$ , we have $N_{\_}{F}[v]\subseteq V(H)\times N^{r}_{\_}P[z]$ .

Then ${f}^{\downarrow}(F)\leqslant g(q,r)$ .

Proof.

We may assume that $V(F)=V(H\boxtimes P)$ because adding isolated vertices preserves the above three conditions and ${f}^{\downarrow}(F)$ . Say $P=(w_{\_}1,w_{\_}2,\dots,w_{\_}{\ell})$ . Let $\mathcal{T}:=(T,\mathcal{B})$ and let $R$ be the root bag of $\mathcal{T}$ . We proceed by induction on the number of bags of $\mathcal{T}$ . Since the root bag is empty, $\mathcal{T}$ has at least two bags.

First suppose that $\mathcal{T}$ consists of exactly two bags. Since $(T,\mathcal{B})$ is $(k,q)$ -rooted, $|V(H)|\leqslant q$ . By the neighbourhood condition, the underlying graph of $F$ is isomorphic to a subgraph of $S_{\_}{\ell,q,r}$ . By assumption, $f(S_{\_}{\ell,q,r})\leqslant g(q,r)$ , and since $f$ is monotone, for every subgraph $Y$ of $S_{\_}{\ell,q,r}$ , $f(Y)\leqslant g(q,r)$ . We obtain a reduction sequence of $F$ as follows. For $i=1,\dots,\ell-1$ , arbitrarily identify $V(H)\times\{w_{\_}i\}$ into a vertex, and then identify the resulting vertex with a vertex in $V(H)\times\{w_{\_}{i+1}\}$ . Lastly, we identify $V(H)\times\{w_{\_}\ell\}$ into a vertex. The underlying graph of every trigraph in this reduction sequence is isomorphic to a subgraph of $S_{\_}{\ell,q,r}$ , which shows that ${f}^{\downarrow}(F)\leqslant g(q,r)$ .

Now assume that $\mathcal{T}$ has at least three bags. Let $B$ be an internal bag at maximum distance in $\mathcal{T}$ from $R$ . So all the children of $B$ are leaf bags. If $B=R$ , then let $Y:=\emptyset$ ; otherwise, let $Y:=B\cap B^{\prime}$ where $B^{\prime}$ is the parent of $B$ .

First suppose that $B$ has at least two child bags $Q$ and $Q^{\prime}$ . If $\lvert(Q\cup Q^{\prime})\setminus B\rvert\leqslant q$ , then we obtain a tree-decomposition from $\mathcal{T}$ by removing $Q$ and $Q^{\prime}$ and attaching a leaf bag $Q\cup Q^{\prime}$ to $B$ . This results in a new tree-decomposition that satisfies the given conditions and has one fewer bag. So we are done by induction. Now assume that $\lvert(Q\cup Q^{\prime})\setminus B\rvert>q$ .

Since $(T,\mathcal{B})$ is $(k,q)$ -rooted, $\lvert(Q\cup Q^{\prime})\setminus B\rvert\leqslant 2q$ . Furthermore, since $V(F)=V(H\boxtimes P)$ , for each $w\in V(P)$ , we have $\lvert((Q\cup Q^{\prime})\setminus B)\times\{w\}\rvert=\lvert(Q\cup Q^{\prime})\setminus B\rvert>q$ . Let $C:=Q\cup Q^{\prime}\cup B$ and $D:=(V(H)\setminus(Q\cup Q^{\prime}))\cup B$ . Note that $(C,D)$ is a rooted separation of $H$ at $B$ . By the separation condition, for each $w\in V(P)$ ,

\left|\left\{N_{\_}{F}(v)\cap(D\times V(P)):v\in((C\setminus D)\times\{w\})\cap V(F)\right\}\right|\leqslant q.

So, for each $w\in V(P)$ , there are distinct vertices $y$ and $z$ in $((Q\cup Q^{\prime})\setminus B)\times\{w\}$ having the same neighbourhood on $D\times V(P)$ .

For $i=1,2,\dots,\ell$ , reduce $((Q\cup Q^{\prime})\setminus B)\times\{w_{\_}i\}$ into a set of $q$ vertices, by repeatedly choosing two vertices having the same neighbourhood on $D\times V(P)$ . Note that we create no red edge incident with $D\times V(P)$ .

Suppose that $U$ is the red graph constructed immediately after identifying some vertices of $((Q\cup Q^{\prime})\setminus B)\times\{w_{\_}i\}$ for some $i$ . We claim that $f(U)\leqslant g(q,r)$ .

For each $j<i$ , $((Q\cup Q^{\prime})\setminus B)\times\{w_{\_}j\}$ has been identified to a set of $q$ vertices, say $W_{\_}j$ . For each $j>i$ , $(Q\setminus B)\times\{w_{\_}j\}$ and $(Q^{\prime}\setminus B)\times\{w_{\_}j\}$ are not yet identified, and so there are only black edges between $\bigcup_{\_}{j>i}(Q\setminus B)\times\{w_{\_}j\}$ and $\bigcup_{\_}{j>i}(Q^{\prime}\setminus B)\times\{w_{\_}j\}$ by the red edge condition. Also, $((Q\cup Q^{\prime})\setminus B)\times\{w_{\_}i\}$ has been identified to at most $2q-1$ vertices, because at least one pair of vertices is identified. Call it $W_{\_}i$ . See Figure 4 for an illustration.

Let

A_{\_}1:=\bigcup_{\_}{j\leqslant i}W_{\_}i\cup\left(\bigcup_{\_}{j>i}(Q\setminus B)\times\{w_{\_}j\}\right)\cup\left(\bigcup_{\_}{j>i}(Q^{\prime}\setminus B)\times\{w_{\_}j\}\right),

and let $A_{\_}2:=V(U)\setminus A_{\_}1$ . Observe that $A_{\_}2=D\times V(P)$ . Since we create no red edge incident with $D\times V(P)$ during the identifications, there is no edge between $A_{\_}1$ and $A_{\_}2$ in $U$ . Furthermore, by the red edge condition and the neighbourhood condition, for each component of $U[A_{\_}2]$ , its underlying graph is a subgraph of $S_{\_}{\ell,q,r}$ . Thus, $f(U[A_{\_}2])\leqslant g(q,r)$ . Also, the underlying graph of $U[A_{\_}1]$ is a subgraph of $S_{\_}{\ell,q,r}$ where $W_{\_}i$ is a subset of the center of $S_{\_}{\ell,q,r}$ . So, $f(U[A_{\_}1])\leqslant g(q,r)$ . Since $f$ is union-closed, $f(U)\leqslant g(q,r)$ .

Now we explain how to apply the induction hypothesis to the resulting trigraph. Let $F^{\prime}$ be the resulting trigraph. Let $H^{\prime}$ be the graph obtained from $H$ by removing $(Q\cup Q^{\prime})\setminus B$ and adding a clique $Z$ of size $q$ that is complete to $B$ . We obtain a tree-decomposition $(T^{\prime},\mathcal{B}^{\prime})$ of $H^{\prime}$ from $(T,\mathcal{B})$ by removing bags $Q$ and $Q^{\prime}$ , and adding a new bag $Z\cup B$ incident with $B$ (and $|(Z\cup B)\setminus B|\leqslant q$ as desired). Observe that $F^{\prime}$ is a trigraph with $V(F^{\prime})\subseteq V(H^{\prime}\boxtimes P)$ satisfying the red edge and neighbourhood conditions.

We verify that $F^{\prime}$ , $H^{\prime}$ , and $(T^{\prime},\mathcal{B}^{\prime})$ satisfy the separation condition. Let $(C^{\prime},D^{\prime})$ be a rooted separation of $F^{\prime}$ of $H^{\prime}$ from $(T^{\prime},\mathcal{B}^{\prime})$ , and let $z\in V(P)$ .

Case 1. $Z\subseteq C^{\prime}$ :

Let $(C_{\_}{pre},D^{\prime})$ be the rooted separation of $H$ obtained from $(C^{\prime},D^{\prime})$ by removing $Z$ from $C^{\prime}$ and adding $(Q\cup Q^{\prime})\setminus B$ . Since we identified two vertices in $(C_{\_}{pre}\setminus D^{\prime})\times\{z\}$ that have the same neighbourhood on $D^{\prime}\times V(P)$ ,

		$\displaystyle\left\|\left\{N_{\_}{F^{\prime}}(v)\cap(D^{\prime}\times V(P)):v\in((C^{\prime}\setminus D^{\prime})\times\{z\})\cap V(F^{\prime})\right\}\right\|$
	$\displaystyle\leqslant$	$\displaystyle\left\|\left\{N_{\_}{F}(v)\cap(D^{\prime}\times V(P)):v\in((C_{\_}{pre}\setminus D^{\prime})\times\{z\})\cap V(F)\right\}\right\|\leqslant q.$

Case 2. $Z\subseteq D^{\prime}$ :

Let $(C^{\prime},D_{\_}{pre})$ be the rooted separation of $H$ obtained from $(C^{\prime},D^{\prime})$ by removing $Z$ from $D^{\prime}$ and adding $(Q\cup Q^{\prime})\setminus B$ . Again, since we identified two vertices in $(D_{\_}{pre}\setminus C^{\prime})\times\{z\}$ that have the same neighbourhood on $C^{\prime}\times V(P)$ ,

		$\displaystyle\left\|\left\{N_{\_}{F^{\prime}}(v)\cap(D^{\prime}\times V(P)):v\in((C^{\prime}\setminus D^{\prime})\times\{z\})\cap V(F^{\prime})\right\}\right\|$
	$\displaystyle\leqslant$	$\displaystyle\left\|\left\{N_{\_}{F}(v)\cap(D_{\_}{pre}\times V(P)):v\in((C^{\prime}\setminus D_{\_}{pre})\times\{z\})\cap V(F)\right\}\right\|\leqslant q.$

Thus, $F^{\prime}$ , $H^{\prime}$ , and $(T^{\prime},\mathcal{B}^{\prime})$ satisfy the separation condition.

Since $(T^{\prime},\mathcal{B}^{\prime})$ has one fewer bag than $(T,\mathcal{B})$ , by induction, there is a reduction sequence $L^{\prime}$ of $F^{\prime}$ , where for every trigraph $G$ in $L^{\prime}$ , $f(\widetilde{G})\leqslant g(q,r)$ . Together with the partial reduction sequence producing $F^{\prime}$ from $F$ , this gives the desired reduction sequence for $F$ .

To finish the proof, it remains to consider the case in which $B$ has exactly one child bag $Q$ . Since $\mathcal{T}$ has at least three bags, $B$ has its parent $B^{\prime}$ and $Y=B\cap B^{\prime}$ . Now, $(B\cup Q)\setminus Y$ has at most $q+k+1\leqslant 2q$ vertices, and we can do the same procedure in Cases 1 or 2 to reduce $((B\cup Q)\setminus Y)\times\{w\}$ (for each $w\in V(P)$ ) to a set of at most $q$ vertices by identifying two vertices having the same neighbourhood on $\bigcup_{\_}{j\in\{1,2,\ldots,\ell\}}Y\times\{w_{\_}j\}$ . This will correspond to vertices of $H$ forming one bag with $Y$ . Note that at the beginning, all edges between $\bigcup_{\_}{j\in\{1,2,\ldots,\ell\}}((B\cup Q)\setminus Y)\times\{w_{\_}j\}$ and $\bigcup_{\_}{j\in\{1,2,\ldots,\ell\}}Y\times\{w_{\_}j\}$ are black. So, the underlying graphs of red graphs constructed from $\bigcup_{\_}{j\in\{1,2,\ldots,\ell\}}((B\cup Q)\setminus Y)\times\{w_{\_}j\}$ will be subgraphs of $S_{\_}{\ell,q,r}$ .

Let $F^{\prime}$ be the resulting trigraph. Let $H^{\prime}$ be the graph obtained from $H$ by removing $(B\cup Q)\setminus Y$ and adding a clique $Z$ of size $q$ that is complete to $Y$ . We obtain a tree-decomposition $(T^{\prime},\mathcal{B}^{\prime})$ of $H^{\prime}$ from $(T,\mathcal{B})$ by removing bags $Q$ and $B$ , and adding a new bag $Z\cup Y$ incident with $B^{\prime}$ (and $|Z\setminus B^{\prime}|\leqslant q$ as desired). It is not difficult to see that $F^{\prime},H^{\prime},(\mathcal{T}^{\prime},\mathcal{B}^{\prime})$ satisfy the red edge, separation, and neighbourhood conditions. So, we can apply induction, which completes the proof of the lemma. ∎

We now rewrite Lemma 19 in a more useful form.

Lemma 20.

Let $k,r,\pi^{*}\in\mathbb{N}$ . Let $G$ be a graph with row-treewidth $k$ , such that $\pi^{r}_{\_}G(X)\leqslant\pi^{*}$ for every set $X\subseteq V(G)$ with $|X|\leqslant(2r+1)(k+1)$ . Then

{\operatorname{bw}}^{\downarrow}(G^{r})\leqslant(2r+2)\pi^{*}-2\quad\text{and}\quad\operatorname{tww}(G^{r})\leqslant(3r+2)\pi^{*}-2.

Proof.

We may assume that $G\subseteq H\boxtimes P$ , where $\operatorname{tw}(H)\leqslant k$ and $P$ is a path. We now show that Lemma 19 is applicable, where $F$ is the trigraph obtained from $G^{r}$ with no red edges. The red edge condition holds trivially.

Consider a rooted tree-decomposition $(T,\mathcal{B})$ of $H$ with width at most $k$ . Let $(C,D)$ be a rooted separation of $(T,\mathcal{B})$ . Consider $z\in V(P)$ and $v\in((C\setminus D)\times\{z\})\cap V(F)$ . Every path in $G$ from $v$ to $D\times V(P)$ with length at most $r$ must intersect $(C\cap D)\times N^{r}_{\_}P[z]$ . Thus $N_{\_}{F}(v)\cap(D\times V(P))$ is determined by the distance- $r$ profile of $v$ on $(C\cap D)\times N^{r}_{\_}{P}[z]$ , which has at most $(2r+1)(k+1)$ vertices. Thus

\displaystyle\left|\left\{N_{\_}{F}(v)\cap(D\times V(P)):v\in((C\setminus D)\times\{z\})\cap V(F)\right\}\right|\,\leqslant\,\pi^{r}_{\_}G((C\cap D)\times N^{r}_{\_}{P}[z])\,\leqslant\,\pi^{*}.

Hence the separation condition in Lemma 19 holds with $q=\pi^{*}$ . The neighbourhood condition holds since $N_{\_}F[v]=N^{r}_{\_}G[v]$ and $G\subseteq H\boxtimes P$ .

For the upper bound on ${\operatorname{bw}}^{\downarrow}$ , we may apply Lemma 19 with $f=\operatorname{bw}$ and $g(q,r)=(2r+2)q-2$ by Equation 2. Thus ${\operatorname{bw}}^{\downarrow}(G)\leqslant g(q,r)=(2r+2)\pi^{*}-2$ .

For the upper bound on $\operatorname{tww}$ , we may apply Lemma 19 with $f=\Delta$ and $g(q,r)=(3r+2)q-2$ by Equation 1. Thus $\operatorname{tww}(G)\leqslant g(q,r)=(3r+2)\pi^{*}-2$ . ∎

Since $\pi^{r}_{\_}G(A)\leqslant(r+1)^{|A|}$ , Lemma 20 is applicable with $\pi^{*}=(r+1)^{(2r+1)(k+1)}$ . Thus:

Corollary 21.

For every graph $G$ with row-treewidth $k$ and for $r\in\mathbb{N}$ ,

{\operatorname{bw}}^{\downarrow}(G^{r})\leqslant 2(r+1)^{(2r+1)(k+1)+1}-2\quad\text{and}\quad\operatorname{tww}(G^{r})\leqslant(3r+2)(r+1)^{(2r+1)(k+1)}-2.

Corollaries 21 and 2 imply:

Corollary 22.

For every graph $G$ with Euler genus $\gamma$ and for $r\in\mathbb{N}$ ,

{\operatorname{bw}}^{\downarrow}(G^{r})\leqslant 2(r+1)^{(2r+1)(2\gamma+7)+1}-2\quad\text{and}\quad\operatorname{tww}(G^{r})\leqslant(3r+2)(r+1)^{(2r+1)(2\gamma+7)}-2.

In particular, for every planar graph $G$ and $r\in\mathbb{N}$ ,

{\operatorname{bw}}^{\downarrow}(G^{r})\leqslant 2(r+1)^{14r+8}-2\quad\text{and}\quad\operatorname{tww}(G^{r})\leqslant(3r+2)(r+1)^{14r+7}-2.

Applying the neighbourhood complexity bounds from Section 3.1 we obtain the following improved bounds in the $r=1$ case.

Theorem 23.

For every graph $G$ with Euler genus $\gamma$ ,

{\operatorname{bw}}^{\downarrow}(G)\leqslant 164\gamma+466\quad\text{and}\quad\operatorname{tww}(G)\leqslant 205\gamma+583.

In particular, for every planar graph $G$ ,

{\operatorname{bw}}^{\downarrow}(G)\leqslant 466\quad\text{and}\quad\operatorname{tww}(G)\leqslant 583.

Proof.

By Theorem 2, $G$ has row-treewidth at most $k:=2\gamma+6$ . By Lemma 13, for every $X\subseteq V(G)$ we have $\pi^{1}_{\_}G(X)\leqslant\max\{4,6|X|+5\gamma-9\}$ , which is at most $41\gamma+117$ when $|X|\leqslant 3(k+1)=6\gamma+21$ . The result thus follows from Lemma 20 with $r=1$ and $\pi^{*}=41\gamma+117$ . ∎

Theorem 24.

For every graph $G$ with row-treewidth $k$ and $\operatorname{col}_{\_}5(G)\leqslant c$ ,

{\operatorname{bw}}^{\downarrow}(G^{r})\leqslant 5\min\{2^{c-1}(3k-c+1),2^{3(k+1)}\}\quad\text{and}\quad\operatorname{tww}(G^{r})\leqslant 8\min\{2^{c-1}(3k-c+1),2^{3(k+1)}\}

Proof.

By Lemma 8, for every $X\subseteq V(G)$ we have $\pi^{1}_{\_}G(X)\leqslant\min\{2^{c-1}(|X|-c+2),2^{|X|}\}$ , which is at most $\min\{2^{c-1}(3k-c+1),2^{3(k+1)}\}$ when $|X|\leqslant 3(k+1)$ . The result thus follows from Lemma 20 with $r=1$ and $\pi^{*}=\min\{2^{c-1}(3k-c+1),2^{3(k+1)}\}$ . ∎

Theorem 25.

Every $(\gamma,k)$ -planar graph $G$ has reduced bandwidth,

{\operatorname{bw}}^{\downarrow}(G)\leqslant 2^{O(\gamma k)}.

Proof.

By Theorem 4, $G$ has row-treewidth $O(\gamma k^{6})$ . By Lemma 9, for every $X\subseteq V(G)$ we have $\pi^{1}_{\_}G(X)\leqslant 2^{22(2\gamma+3)(k+1)-1}|X|$ , which is in $2^{O(\gamma k)}$ when $|X|\in O(\gamma k^{6})$ . The result thus follows from Lemma 20 with $r=1$ and $\pi^{*}=2^{O(\gamma k)}$ . ∎

We have the following result for squares of graphs of given Euler genus.

Theorem 26.

For every graph $G$ of Euler genus $\gamma$ ,

	$\displaystyle{\operatorname{bw}}^{\downarrow}(G^{2})$	$\displaystyle\leqslant 234000\gamma^{4}+1983300\gamma^{3}+5769330\gamma^{2}+6671550\gamma+2711084\quad\text{and}$
	$\displaystyle\operatorname{tww}(G^{2})$	$\displaystyle\leqslant 312000\gamma^{4}+2644400\gamma^{3}+7692440\gamma^{2}+8895400\gamma+3614782.$

In particular, for every planar graph $G$ ,

\displaystyle{\operatorname{bw}}^{\downarrow}(G^{2})\leqslant 2711084\quad\text{and}\quad\operatorname{tww}(G^{2})

\displaystyle\leqslant 3614782.

Proof.

By Theorem 2, $G$ has row-treewidth at most $k:=2\gamma+6$ . By Corollary 18, for every set $X\subseteq V(G)$ ,

\pi^{2}_{\_}G(X)\leqslant\max\{2,(6|X|+5\gamma-9)((60\gamma^{2}+125\gamma+68)|X|-120\gamma^{2}-250\gamma-132)\}.

The result thus follows from Lemma 20 with $r=2$ and

	$\displaystyle\pi^{*}$	$\displaystyle=(6(5(k+1))+5\gamma-9)((60\gamma^{2}+125\gamma+68)5(k+1)-120\gamma^{2}-250\gamma-132)$
		$\displaystyle=39000\gamma^{4}+330550\gamma^{3}+961555\gamma^{2}+1111925\gamma+451848.\qed$

We now give an example of the application of Theorem 26. Map graphs are defined as follows. Start with a graph $G_{\_}0$ embedded in a surface of Euler genus $\gamma$ , with each face labelled a ‘nation’ (or a ‘lake’). Let $G$ be the graph whose vertices are the nations of $G_{\_}0$ , where two vertices are adjacent in $G$ if the corresponding faces in $G_{\_}0$ share a vertex. Then $G$ is called a map graph of Euler genus $\gamma$ . A map graph of Euler genus 0 is called a (plane) map graph; see [20, 13] for example. Map graphs generalise graphs embedded in surfaces, since a graph $G$ has Euler genus at most $\gamma$ if and only if $G$ has a representation as a map graph of Euler genus at most $\gamma$ with the extra property that each vertex of $G_{\_}0$ is incident with at most three nations [16]. Our results for map graphs are independent of the number of nations incident to each vertex of $G_{\_}0$ . It follows from the definition that for each map graph $G$ of Euler genus $\gamma$ , there is a bipartite graph $H$ with bipartition $\{A,B\}$ , such that $H$ has Euler genus at most $\gamma$ and $V(G)=A$ and $vw\in E(G)$ whenever $v,w\in N_{\_}H(b)$ for some $b\in B$ (see [16]); $G$ is called the half-square of $H$ . Note that $G$ is an induced subgraph of $H^{2}$ . Since reduced bandwidth is hereditary⁸⁸8It is an easy exercise to show that ${f}^{\downarrow}$ is hereditary for every monotone graph parameter $f$ ; see [9, Section 4.1] for a proof sketch in the case of twin-width., the results in Theorem 26 also hold for map graphs of Euler genus $\gamma$ . We emphasise there is no dependence on the maximum degree (which is customary when considering map graphs).

The proof of Lemma 19 is constructive and the desired reduction sequence can be found in time $O(|V(F)|^{2})$ when $H$ and $P$ are given. For all the above examples, the graphs $H$ and $P$ can be found in $O(|V(G)|^{2})$ time; see [17, 36, 18, 12] for details and speed-ups. So the desired reduction sequence can be found in $O(|V(G)|^{2})$ time.

5 Proper Minor-Closed Classes

This section shows that fixed powers of graphs in any proper minor-closed class have bounded reduced bandwidth. To use the product structure theorem for $K_{\_}t$ -minor-free graphs (Theorem 3), we first prove an upper bound on the reduced bandwidth of the $r$ -th power of a subgraph of $(H\boxtimes P)+K_{\_}a$ where $H$ has bounded treewidth, $P$ is a path, and $a\in\mathbb{N}$ . To do so, in Lemma 27 below we prove an extension of Lemma 19 that allows for apex vertices. Consider the $r$ -th power of a subgraph of $(H\boxtimes P)+K_{\_}a$ . There may exist an edge $vw$ with $v,w\in V(H)\times V(P)$ where the corresponding vertices in $P$ are far apart in $P$ , because there may exist a path of length at most $r$ through some vertices in $K_{\_}a$ . So the neighbourhood condition of Lemma 19 is no longer relevant. Instead, red edges are controlled by a new ‘red edge condition’, and black edges are controlled by two separation conditions. The second separation condition is necessary to deal with the base case when the tree-decomposition of $H$ has one non-empty bag.

Lemma 27.

Let $a,k,q,r\in\mathbb{N}$ with $q\geqslant k+1$ . Let $f$ be a monotone and union-closed graph parameter and let $g:\mathbb{N}\times\mathbb{N}\to\mathbb{R}$ be a function such that $f(S_{\_}{x,q,r})\leqslant g(q,r)$ for all $x\in\mathbb{N}$ . Let $P=(w_{\_}1,w_{\_}2,\dots,w_{\_}{\ell})$ be a path and let $H$ be a graph admitting a $(k,q)$ -rooted tree-decomposition $(T,\mathcal{B})$ . Let $F$ be a trigraph with $V(F)\subseteq V((H\boxtimes P)+K_{\_}a)$ such that:

•

(red edge condition) for every red edge $vw$ of $F$ , there is a leaf bag $B$ with parent $B^{\prime}$ in $(T,\mathcal{B})$ and there are vertices $x,y$ in $P$ with $\operatorname{dist}_{\_}P(x,y)\leqslant r$ , such that $v,w\in(B\setminus B^{\prime})\times\{x,y\}$ ,
•

(first separation condition) for every rooted separation $(C,D)$ of $H$ from $(T,\mathcal{B})$ and every $z\in V(P)$ ,

$\left|\left\{N_{\_}{F}(v)\cap M_{\_}1:v\in((C\setminus D)\times\{z\})\cap V(F)\right\}\right|\leqslant q,$

where $M_{\_}1=\Big{(}D\times V(P)\Big{)}\cup\Big{(}C\times(V(P)\setminus N^{r}_{\_}P[z])\Big{)}\cup V(K_{\_}a)$ ,
•

(second separation condition) for every $t\in\{1,\ldots,\ell\}$ ,

$|\{N_{\_}F(v)\cap M_{\_}2:v\in(V(H)\times\{w_{\_}1,\dots,w_{\_}t\})\cap V(F)\}|\leqslant q,$

where $M_{\_}2=\big{(}V(H)\times\{w_{\_}{t+r+1},\dots,w_{\_}\ell\}\big{)}\cup V(K_{\_}a)$ .

Then:

(1)

there is a partial reduction sequence identifying $(V(H)\times V(P))\cap V(F)$ into at most $q$ vertices such that for every trigraph $G$ in the sequence, $G$ has no red edge incident with $V(K_{\_}a)$ and $f(\widetilde{G})\leqslant g(q,r)$ , and
(2)

${f}^{\downarrow}(F)\leqslant g(a+q,r)$ .

Proof.

We identify the $V(H)\times V(P)$ part using a partial reduction sequence similar to the one in the proof of Lemma 19. The main difference in the induction step is that when we consider a rooted separation $(C,D)$ from $(T,\mathcal{B})$ and $z\in V(P)$ , instead of choosing two vertices having the same neighbourhood on $D\times V(P)$ , here we choose two vertices having the same neighbourhood on

\Big{(}D\times V(P)\Big{)}\cup\Big{(}C\times(V(P)\setminus N^{r}_{\_}P[z])\Big{)}\cup V(K_{\_}a).

This clearly preserves the new red edge and separation conditions. So, as in the proof of Lemma 19, choose an internal bag $B$ at maximum distance in $(T,\mathcal{B})$ from the root bag. Then for $i=1,2,\dots,\ell$ , merge $(Q\setminus B)\times\{w_{\_}i\}$ and $(Q^{\prime}\setminus B)\times\{w_{\_}i\}$ for each $w_{\_}i\in V(P)$ if $B$ has two child bags $Q$ and $Q^{\prime}$ , and otherwise, merge $(B\setminus B^{\prime})\times\{w_{\_}i\}$ and $(Q\setminus B^{\prime})\times\{w_{\_}i\}$ for the unique child $Q$ of $B$ and the parent $B^{\prime}$ of $B$ . Because of the choice of identified vertices, for each red component of an intermediate trigraph, its underlying graph is isomorphic to a subgraph of $S_{\_}{\ell,q,r}$ , and has $f$ at most $g(q,r)$ .

Now, we consider the base case where $(T,\mathcal{B})$ has two bags $R$ and $B$ , where $R$ is the empty root bag. We need a new argument for this case, because if we arbitrarily identify two vertices, then we may create some red edges between two vertices contained in $V(H)\times\{x\}$ and $V(H)\times\{y\}$ where $x$ and $y$ are far from each other in $P$ , and we cannot guarantee that the red graphs have bounded $f$ -values.

We prove by induction on $\ell$ that there is a partial reduction sequence identifying $(V(H)\times V(P))\cap V(F)$ into at most $q$ vertices, such that for every trigraph $G$ in the sequence,

•

$G$ has no red edge incident with $V(K_{\_}a)$ , and $f(\widetilde{G})\leqslant g(q,r)$ .

We may assume that $H$ is a complete graph on $q$ vertices. If $\ell=1$ , then $V(H)\times V(P)$ has at most $q$ vertices, and there is nothing to show.

We assume that $\ell>1$ . If $|(B\times\{w_{\_}1\})\cup(B\times\{w_{\_}2\})|\leqslant q$ , then remove $B\times\{w_{\_}1\}$ and replace $B\times\{w_{\_}2\}$ with $(B\times\{w_{\_}1\})\cup(B\times\{w_{\_}2\})$ . Thus we can reduce the length of $P$ , and are done by induction. Now assume that $|(B\times\{w_{\_}1\})\cup(B\times\{w_{\_}2\})|>q$ . By the second separation condition, there are two vertices in $(B\times\{w_{\_}1\})\cup(B\times\{w_{\_}2\})$ that have the same neighbourhood on

M_{\_}2=\big{(}V(H)\times\{w_{\_}{2+r+1},\dots,w_{\_}\ell\}\big{)}\cup V(K_{\_}a)

By repeatedly identifying two vertices having the same neighbourhoods on $M_{\_}2$ , we identify $(B\times\{w_{\_}1\})\cup(B\times\{w_{\_}2\})$ into at most $q$ vertices. In this way, we can reduce the length of $P$ , and we are done by induction. This proves (1).

For (2), observe that the statement (1) holds when we replace $g(q,r)$ with $g(a+q,r)$ , because every subgraph of $S_{\_}{\ell,q,r}$ is also a subgraph of $S_{\_}{\ell,a+q,r}$ . We obtain the desired reduction sequence by arbitrarily identifying the resulting trigraph on at most $a+q$ vertices into a 1-vertex graph. ∎

We extend Lemma 27 to deal with the internal node case of the tree-decomposition of $X$ -minor free graphs. We now allow bags of size more than $q$ , and we start by identifying vertices corresponding to those bags. The first three conditions in Lemma 28 are the same as the conditions in Lemma 27. We use Lemma 27 as a base case.

Lemma 28.

Let $a,k,q,r,t\in\mathbb{N}$ with $q\geqslant k+1$ . Let $f$ be a monotone and union-closed graph parameter. Let $g:\mathbb{N}\times\mathbb{N}\to\mathbb{R}$ be a function such that $f(S_{\_}{x,q,r})\leqslant g(q,r)$ for all $x\in\mathbb{N}$ . Let $P=(w_{\_}1,w_{\_}2,\dots,w_{\_}{\ell})$ be a path and let $H$ be a graph admitting a $(k,\infty)$ -rooted tree-decomposition $(T,\mathcal{B})$ . Let $F$ be a trigraph with $V(F)\subseteq V((H\boxtimes P)+K_{\_}a)$ such that the red edge, first separation and second separation conditions from Lemma 27 are satisfied, and in addition:

•
(large leaf bag condition) for every leaf bag $B$ with parent bag $B^{\prime}$ and $|B\setminus B^{\prime}|>q$ ,
- –
  
  $B\times V(P)\subseteq B\times\{x,y\}$ for some adjacent vertices $x,y$ of $P$ ,
- –
  
  there is a partial reduction sequence identifying $((B\setminus B^{\prime})\times V(P))\cap V(F)$ into at most $q$ vertices such that for every trigraph $G$ in the reduction sequence, $G$ has no red edge incident with $((V(H)\setminus(B\setminus B^{\prime}))\times V(P))\cup V(K_{\_}a)$ and $f(\widetilde{G})\leqslant t$ .

Then:

(1)

There is a reduction sequence identifying $(V(H)\times V(P))\cap V(F)$ into at most $q$ vertices such that for every trigraph $G$ in the reduction sequence, $G$ has no red edge incident with $V(K_{\_}a)$ and $f(\widetilde{G})\leqslant\max(g(q,r),t)$ .
(2)

${f}^{\downarrow}(F)\leqslant\max(g(a+q,r),t)$ .

Proof.

We say that a leaf bag $B$ of $(T,\mathcal{B})$ with parent bag $B^{\prime}$ is large if $|B\setminus B^{\prime}|>q$ . We prove (1) by induction on the number of large leaf bags. If there are no large leaf bags, then $(T,\mathcal{B})$ is $(k,q)$ -rooted, and the result follows from Lemma 27. Now assume that $(T,\mathcal{B})$ contains a large leaf bag.

Let $B$ be a large leaf bag with parent bag $B^{\prime}$ . Let $U_{\_}1:=(B\setminus B^{\prime})\times V(P)$ and $U_{\_}2:=((V(H)\setminus(B\setminus B^{\prime}))\times V(P))\cup V(K_{\_}a)$ .

Let $L_{\_}B$ be a partial reduction sequence identifying $U_{\_}1\cap V(F)$ , as described in the large leaf bag condition. By the red edge condition, there is no red edge between $U_{\_}1$ and $U_{\_}2$ . Apply $L_{\_}B$ to $U_{\_}1\cap V(F)$ . By assumption, we always identify two vertices having the same neighbourhoods on $U_{\_}2$ , and therefore, it creates no red edge incident with $U_{\_}2$ . Since $B\times V(P)\subseteq B\times\{x,y\}$ for some adjacent vertices $x,y$ of $P$ , the resulting trigraph satisfies the red edge condition. Also, each red graph of an intermediate trigraph constructed from $U_{\_}1$ has $f$ at most $t$ , by assumption.

Let $F^{\prime}$ be the resulting trigraph. Let $H^{\prime}$ be the graph obtained from $H$ by removing $B\setminus B^{\prime}$ and adding a clique $Z$ of size $q$ that is complete to $B^{\prime}$ . We obtain a tree-decomposition $(T^{\prime},\mathcal{B}^{\prime})$ of $H^{\prime}$ from $(T,\mathcal{B})$ by removing the bag $B$ , and adding a new bag $Z\cup B^{\prime}$ incident with $B^{\prime}$ (and $|(Z\cup B^{\prime})\setminus B^{\prime}|\leqslant q$ as desired). Observe that $F^{\prime}$ is a trigraph with $V(F^{\prime})\subseteq V(H^{\prime}\boxtimes P)\cup V(K_{\_}a)$ satisfying the four conditions.

Since $(T^{\prime},\mathcal{B}^{\prime})$ has one fewer large leaf bag than $(T,\mathcal{B})$ , by induction, there is a reduction sequence identifying $(V(H^{\prime})\times V(P))\cap V(F^{\prime})$ into at most $q$ vertices such that for every trigraph $G$ in the reduction sequence, $G$ has no red edge incident with $V(K_{\_}a)$ and $f(\widetilde{G})\leqslant\max(g(q,r),t)$ . Together with the reduction sequence producing $F^{\prime}$ from $F$ , we obtain a desired reduction sequence for $F$ .

Similar to Lemma 27, the statement (1) holds when we replace $g(q,r)$ with $g(a+q,r)$ , because every subgraph of $S_{\_}{\ell,q,r}$ is also a subgraph of $S_{\_}{\ell,a+q,r}$ . We obtain the desired reduction sequence by arbitrarily identifying the resulting trigraph on at most $a+q$ vertices into a 1-vertex graph. ∎

Theorem 29.

Let $t,r\in\mathbb{N}$ . Let $f$ be a monotone and union-closed graph parameter and let $g:\mathbb{N}\times\mathbb{N}\to\mathbb{R}$ be a function such that $f(S_{\_}{x,q,r})\leqslant g(q,r)$ for all $x\in\mathbb{N}$ . Then there exists $c\in\mathbb{N}$ such that ${f}^{\downarrow}(G^{r})\leqslant c$ for every $K_{\_}t$ -minor-free graph $G$ .

Proof.

By Theorem 3, there exist $k,a\in\mathbb{N}$ such that $G$ has a tree-decomposition $\mathcal{T}=(T,\mathcal{B})$ in which every torso of a bag is a subgraph of $(H\boxtimes P)+K_{\_}a$ for some graph $H$ of treewidth at most $k$ and some path $P$ . Consider $\mathcal{T}$ to be rooted at an arbitrary bag $R$ of $\mathcal{T}$ . Let $\beta:=2(k+1)+a$ . Note that the size of a maximum clique of $(H\boxtimes P)+K_{\_}a$ is at most $\beta$ . Let $h$ be the longest path from an internal bag to $R$ in $\mathcal{T}$ . Define

\theta:=a+\tbinom{\beta}{2}(r+1)+\beta r,\quad q:=(r+1)^{(k+1)(2r+1)+\theta}\quad\text{and}\quad c:=g(q,r).

For each bag $B$ of $\mathcal{T}$ , if $B=R$ then let $Y_{\_}B:=\emptyset$ ; otherwise, let $Y_{\_}B:=B\cap B^{\prime}$ where $B^{\prime}$ is the parent of $B$ . Also, let $U_{\_}B$ be the union of $B$ and all the descendants of $B$ . Note that $0\leqslant h-\operatorname{dist}_{\_}T(B,R)\leqslant h$ .

We prove by induction on $h-\operatorname{dist}_{\_}T(B,R)$ that

( $\ast$ )
there is a partial reduction sequence identifying $U_{\_}B\setminus Y_{\_}B$ into at most $q$ vertices in $G^{r}$ such that:
- –
  
  we always identify two vertices $u$ and $v$ where the corresponding vertices in $G$ have the same distance- $r$ profiles on $Y_{\_}B$ in $G[U_{\_}B]$ , and
- –
  
  for every trigraph $G^{*}$ in the sequence, $f(\widetilde{G^{*}})\leqslant c$ .

Let $B$ be a bag. Let $G_{\_}1$ be the graph obtained from $G[U_{\_}B]$ by adding, for each pair of vertices $y_{\_}1,y_{\_}2$ of $Y_{\_}B$ with $\operatorname{dist}_{\_}{G-E(G[U_{\_}B])}(y_{\_}1,y_{\_}2)\leqslant r$ , a new path $X_{\_}{y_{\_}1,y_{\_}2}$ of length $\operatorname{dist}_{\_}{G-E(G[U_{\_}B])}(y_{\_}1,y_{\_}2)$ whose end-vertices are $y_{\_}1$ and $y_{\_}2$ , and then adding, for every vertex $y$ of $Y_{\_}B$ , a path $W_{\_}y$ of length $r-1$ whose end-vertex is $y$ .

We claim that for any two vertices $v,w\in U_{\_}B$ ,

•

$\operatorname{dist}_{\_}G(v,w)\leqslant r$ if and only if $\operatorname{dist}_{\_}{G_{\_}1}(v,w)\leqslant r$ .

Assume that there is a path $Z$ of length at most $r$ between $v$ and $w$ in $G$ . We construct a path $Z^{*}$ of $G_{\_}1$ from $Z$ as follows.

•

We repeatedly choose a maximal subpath $Q$ of $Z$ whose end-vertices are in $U_{\_}B$ and all internal vertices are not in $U_{\_}B$ . Assume its end-vertices are $y_{\_}1$ and $y_{\_}2$ . Then we replace $Q$ with $X_{\_}{y_{\_}1,y_{\_}2}$ .

By construction, $|E(X_{\_}{y_{\_}1,y_{\_}2})|=\operatorname{dist}_{\_}{G-E(G[U_{\_}B])}(y_{\_}1,y_{\_}2)\leqslant|E(Q)|$ . So, the resulting path $Z^{*}$ has length at most $r$ , which shows that $\operatorname{dist}_{\_}{G_{\_}1}(v,w)\leqslant r$ .

For the other direction, assume there is a path $Z$ of length at most $r$ between $v$ and $w$ in $G_{\_}1$ . Similarly, we construct a walk of length at most $r$ in $G$ from $Z$ as follows.

•

We repeatedly choose a maximal subpath $Q$ of $Z$ of length at least $2$ whose end-vertices are in $U_{\_}B$ and all internal vertices are not in $U_{\_}B$ . Note that $Q$ is $X_{\_}{y_{\_}1,y_{\_}2}$ for some $y_{\_}1,y_{\_}2\in Y$ . By the construction, there is a path $Q_{\_}{y_{\_}1,y_{\_}2}$ in $G-E(G[U])$ of length $|E(X_{\_}{y_{\_}1,y_{\_}2})|$ . Then we replace $Q$ with $Q_{\_}{y_{\_}1,y_{\_}2}$ .

The resulting walk has length at most $r$ between $v$ and $w$ in $G$ . Thus, $\operatorname{dist}_{\_}G(v,w)\leqslant r$ .

By the claim, $G^{r}[U_{\_}B]=(G_{\_}1)^{r}[U_{\_}B]$ .

Now focus on $G_{\_}1$ . First observe that $G_{\_}1[B]=G[B]$ and its torso is a subgraph of $(H\boxtimes P)+K_{\_}a$ for some graph $H$ of treewidth at most $k$ and some path $P$ . Let $(T_{\_}B,\mathcal{B}_{\_}B)$ be a rooted tree-decomposition of $H$ of width at most $k$ . Let $P=(w_{\_}1,w_{\_}2,\dots,w_{\_}{\ell})$ .

Observe that $Y_{\_}B\cup(\bigcup_{\_}{\{y_{\_}1,y_{\_}2\}\in\binom{Y_{\_}B}{2}}V(X_{\_}{y_{\_}1,y_{\_}2}))\cup(\bigcup_{\_}{y\in Y_{\_}B}V(W_{\_}y))$ contains at most $\beta+\binom{\beta}{2}(r-1)+\beta(r-1)$ vertices. Since $G_{\_}1[B]$ is a subgraph of $(H\boxtimes P)+K_{\_}a$ , the graph

G_{\_}1[B]\cup\bigcup_{\_}{\{y_{\_}1,y_{\_}2\}\in\binom{Y_{\_}B}{2}}X_{\_}{y_{\_}1,y_{\_}2}\cup\bigcup_{\_}{y\in Y_{\_}B}W_{\_}y.

can be regarded as a subgraph of $(H\boxtimes P)+K_{\_}{\theta}$ , where $Y_{\_}B\cup(\bigcup_{\_}{\{y_{\_}1,y_{\_}2\}\in\binom{Y_{\_}B}{2}}V(X_{\_}{y_{\_}1,y_{\_}2}))\cup(\bigcup_{\_}{y\in Y_{\_}B}V(W_{\_}y))$ is placed in the $K_{\_}{\theta}$ part. Let

G_{\_}2:=G_{\_}1[B]\cup\bigcup_{\_}{\{y_{\_}1,y_{\_}2\}\in\binom{Y_{\_}B}{2}}X_{\_}{y_{\_}1,y_{\_}2}\cup\bigcup_{\_}{y\in Y_{\_}B}W_{\_}y.

Next, we extend the product structure for $G_{\_}2$ into one for $G_{\_}1$ . We modify $H$ to $H^{*}$ as follows. Let $B^{\prime}$ be a child of the bag $B$ . Observe that $B\cap B^{\prime}$ is a clique in the torso of $B$ . Therefore, the vertices of $B\cap B^{\prime}$ lie on $(N_{\_}B\times\{y_{\_}1,y_{\_}2\})\cup V(K_{\_}{\theta})$ for some consecutive two vertices $y_{\_}1$ and $y_{\_}2$ in $P$ and some bag $N_{\_}B$ of $(T_{\_}B,\mathcal{B}_{\_}B)$ . To $H$ , we add a clique $Q_{\_}{B^{\prime}}$ of size $|U_{\_}{B^{\prime}}|$ that is complete to $N_{\_}B$ . We add a leaf bag $Q_{\_}{B^{\prime}}\cup N_{\_}B$ adjacent to $N_{\_}B$ , and embed the vertices of $U_{\_}{B^{\prime}}\setminus B$ into $Q_{\_}{B^{\prime}}\times\{y_{\_}1\}$ . We do this process for every child of $B$ .

Let $H^{*}$ be the resulting graph obtained from $H$ , and let $(T_{\_}B^{*},\mathcal{B}_{\_}B^{*})$ be the resulting rooted tree-decomposition of $H^{*}$ . Since $(T_{\_}B,\mathcal{B}_{\_}B)$ has width at most $k$ , $(T_{\_}B^{*},\mathcal{B}_{\_}B^{*})$ is $(k,\infty)$ -rooted. Also $G_{\_}1$ is a subgraph of $(H^{*}\boxtimes P)+K_{\_}{\theta}$ .

We now apply Lemma 28 to $(G_{\_}1)^{r}$ and $(T_{\_}B^{*},\mathcal{B}_{\_}B^{*})$ . To do so, we verify the four conditions. Since $(G_{\_}1)^{r}$ has no red edges, the red edge condition holds.

(First separation condition) Let $(C,D)$ be a rooted separation of $H^{*}$ from $(T_{\_}B^{*},\mathcal{B}_{\_}B^{*})$ and let $z\in V(P)$ . Let

M_{\_}1:=\Big{(}D\times V(P)\Big{)}\cup\Big{(}C\times(V(P)\setminus N^{r}_{\_}P[z])\Big{)}\cup V(K_{\_}\theta).

Observe that if there is a path of length at most $r$ in $G_{\_}1$ between $((C\setminus D)\times\{z\})\cap V(G_{\_}1)$ and $M_{\_}1$ , this path intersects $((C\cap D)\times N^{r}_{\_}P[z])\cup V(K_{\_}\theta)$ . Thus two vertices $v,w\in((C\setminus D)\times\{z\})\cap V(G_{\_}1)$ having the same distance- $r$ profiles on $((C\cap D)\times N^{r}_{\_}P[z])\cup V(K_{\_}\theta)$ in $G_{\_}1$ have the same neighbourhood on $M_{\_}1$ in $(G_{\_}1)^{r}$ . Therefore,

	$\displaystyle\left\|\left\{N_{\_}{(G_{\_}1)^{r}}(v)\cap M:v\in((C\setminus D)\times\{z\})\cap V(G_{\_}1)\right\}\right\|\leqslant\;$	$\displaystyle\pi^{r}_{\_}{G_{\_}1}\Big{(}((C\cap D)\times N^{r}_{\_}P[z])\cup V(K_{\_}\theta)\Big{)}$
	$\displaystyle\leqslant\;$	$\displaystyle(r+1)^{(k+1)(2r+1)+\theta}\,=\,q.$

(Second separation condition) Let $t\in\{1,2,\ldots,\ell\}$ and let

M_{\_}2:=\big{(}V(H^{*})\times\{w_{\_}{t+r+1},\dots,w_{\_}\ell\}\big{)}\cup V(K_{\_}\theta).

Observe that if there is a path of length at most $r$ in $G_{\_}1$ between $(V(H^{*})\times\{w_{\_}1,\dots,w_{\_}t\})\cap V(G_{\_}1)$ and $M_{\_}2$ , then this path intersects $V(K_{\_}{\theta})$ . So, any two vertices in $(V(H^{*})\times\{w_{\_}1,\dots,w_{\_}t\})\cap V(G_{\_}1)$ having the same distance- $r$ profiles on $V(K_{\_}\theta)$ have the same neighbourhood on $M_{\_}2$ in $(G_{\_}1)^{r}$ . Thus,

\displaystyle|\{N_{\_}{(G_{\_}1)^{r}}(v)\cap M_{\_}2:v\in(V(H)\times\{w_{\_}1,\dots,w_{\_}t\})\cap V(G_{\_}1)\}|\leqslant\;\pi^{r}_{\_}{G_{\_}1}(V(K_{\_}\theta))\,\leqslant\,(r+1)^{\theta}\,\leqslant\,q.

(Large leaf bag condition) Let $A$ be a leaf bag of $(T_{\_}B^{*},\mathcal{B}_{\_}B^{*})$ with parent bag $A^{\prime}$ with $|A\setminus A^{\prime}|>q$ . By the construction of $H^{*}$ and $(T_{\_}B^{*},\mathcal{B}_{\_}B^{*})$ , we know that $A\times V(P)\subseteq A\times\{y_{\_}1,y_{\_}2\}$ for some adjacent vertices $y_{\_}1$ and $y_{\_}2$ in $P$ . Also, $((A\setminus A^{\prime})\times\{y_{\_}1,y_{\_}2\})\cap V(G_{\_}1)=U_{\_}{B^{\prime}}\setminus B$ for some child $B^{\prime}$ of $B$ . By induction, there is a partial reduction sequence identifying $U_{\_}{B^{\prime}}\setminus Y_{\_}{B^{\prime}}$ into at most $q$ vertices in $G^{r}$ such that:

•

we always identify two vertices $u$ and $v$ where the corresponding vertices in $G$ have the same distance- $r$ profiles on $Y_{\_}{B^{\prime}}$ in $G[U_{\_}{B^{\prime}}]$ , and
•

for every trigraph $G^{*}$ in the sequence, $f(\widetilde{G^{*}})\leqslant c$ .

Since $G^{r}[U_{\_}B]=(G_{\_}1)^{r}[U_{\_}B]$ , this sequence is also a partial reduction sequence for $(G_{\_}1)^{r}[U_{\_}{B^{\prime}}\setminus Y_{\_}{B^{\prime}}]$ . Note that if two vertices have the same distance- $r$ profiles on $Y_{\_}{B^{\prime}}$ in $G[U_{\_}{B^{\prime}}]$ , then they have the same distance- $r$ profiles on $Y_{\_}B$ in $G[U_{\_}B]$ . Thus, by the first bullet, this sequence does not create any red edge incident with $V(K_{\_}\theta)$ .

We deduce that $(G_{\_}1)^{r}$ and $(T_{\_}B^{*},\mathcal{B}_{\_}B^{*})$ satisfy the large leaf bag condition of Lemma 28.

Therefore, by Lemma 28, there is a partial reduction sequence identifying $(V(H^{*})\times V(P))\cap V(G_{\_}1)$ into at most $q$ vertices in $(G_{\_}1)^{r}$ such that for every trigraph $G^{*}$ in the sequence, $G^{*}$ has no red edge incident with $V(K_{\_}\theta)$ , and $f(\widetilde{G^{*}})\leqslant\max(g(q,r),c)$ .

Now apply the same reduction sequence to $G^{r}$ . We claim that we always identify two vertices having the same distance- $r$ profiles on $Y_{\_}B$ in $G[U_{\_}B]$ . Suppose for contradiction that we identified two vertices $u$ and $v$ having distinct distance- $r$ profiles on $Y_{\_}B$ in $G[U_{\_}B]$ . We may assume that for some $x\in Y_{\_}B$ and $\ell_{\_}1\in\{1,2,\ldots,r\}$ and $\ell_{\_}2\in\{\ell_{\_}1+1,\ldots r\}\cup\{\infty\}$ , we have $\operatorname{dist}_{\_}{G[U_{\_}B]}(u,x)=\ell_{\_}1$ and $\operatorname{dist}_{\_}{G[U_{\_}B]}(v,x)=\ell_{\_}2$ . But then on the path $W_{\_}x$ , there is a vertex adjacent to $u$ but not to $y$ in $(G_{\_}1)^{r}$ . So, when we identify these vertices in $(G_{\_}1)^{r}$ , we create a red edge incident with $V(K_{\_}{\theta})$ , a contradiction. Therefore, the claim holds.

We conclude that the statement $(\ast)$ holds by induction. When $B=R$ , we know that $U_{\_}B=V(G)$ and $Y_{\_}B=\emptyset$ . Therefore, there is a partial reduction sequence identifying $V(G)$ into at most $q$ vertices in $G^{r}$ such that for every trigraph $G^{*}$ in the sequence, $f(\widetilde{G^{*}})\leqslant c$ . We obtain the desired reduction sequence by arbitrarily identifying the resulting trigraph on at most $q$ vertices into a 1-vertex graph. For every trigraph $G^{**}$ in this sequence, $f(\widetilde{G^{**}})\leqslant g(q,r)=c$ , as every graph on at most $q$ vertices is a subgraph of $S_{\_}{1,q,r}$ . This completes the proof of the theorem. ∎

Theorem 29 with $f=\operatorname{bw}$ and $g(q,r)=(2r+2)q-2$ implies the following result, which is the main contribution of the paper.

Theorem 30.

For all $t,r\in\mathbb{N}$ there exists $c\in\mathbb{N}$ such that for every $K_{\_}t$ -minor-free graph $G$ ,

{\operatorname{bw}}^{\downarrow}(G^{r})\leqslant c.

6 Expanders

This section shows that bounded degree expanders have unbounded reduced bandwidth. In fact, we show a stronger result for expanders excluding a fixed complete bipartite subgraph. For $s\in\mathbb{N}$ and $\beta\in\mathbb{R}^{+}$ , a graph $G$ is an $(s,\beta)$ -expander if $G$ contains no $K_{\_}{s,s}$ subgraph, and for every $S\subseteq V(G)$ with $|S|\leqslant\frac{|V(G)|}{2}$ we have $\lvert N_{\_}G(S)\rvert\geqslant\beta\lvert S\rvert$ . Expanders can be constructed probabilistically or constructively; see the survey [29] for example. In the following result it is necessary to exclude some fixed complete bipartite subgraph, as otherwise complete bipartite graphs would be counterexamples.

Theorem 31.

Let $\mathcal{G}$ be an infinite class of $(s,\beta)$ -expanders for some $s\in\mathbb{N}$ and $\beta\in\mathbb{R}^{+}$ . Then $\mathcal{G}$ has unbounded ${\operatorname{bw}}^{\downarrow}$ .

Proof.

Assume for contradiction that there exists $k\in\mathbb{N}$ such that ${\operatorname{bw}}^{\downarrow}(G)\leqslant k$ for every $G\in\mathcal{G}$ . Consider an $n$ -vertex graph $G\in\mathcal{G}$ where $n\gg k,s,\beta^{-1}$ (as detailed below).

Let $G=G_{\_}n,G_{\_}{n-1},\dots,G_{\_}1$ be a reduction sequence for $G$ such that every red graph has bandwidth at most $k$ . It is convenient to consider the corresponding partition sequence

\{\{v\}:v\in V(G)\}=\mathcal{P}_{\_}n,\mathcal{P}_{\_}{n-1},\dots,\mathcal{P}_{\_}1=\{V(G)\},

and the associated trigraphs $G_{\_}{\mathcal{P}_{\_}n},G_{\_}{\mathcal{P}_{\_}{n-1}},\dots,G_{\_}{\mathcal{P}_{\_}1}$ isomorphic to $G_{\_}n,G_{\_}{n-1},\dots,G_{\_}1$ respectively. If $G_{\_}{i-1}=G_{\_}i/u,v$ and $u\in X$ and $v\in Y$ , then $X$ and $Y$ are distinct parts of $\mathcal{P}_{\_}i$ , and $\mathcal{P}_{\_}{i-1}$ is obtained from $\mathcal{P}_{\_}i$ by replacing $X$ and $Y$ by $X\cup Y$ . We consider the parts of $\mathcal{P}_{\_}i$ to be the vertices of $G_{\_}{\mathcal{P}_{\_}i}$ . Say a part $X\in\mathcal{P}_{\_}i$ is big if $|X|\geqslant s$ and small otherwise. Observe that for each black edge $XY$ in $G_{\_}{\mathcal{P}_{\_}i}$ , there is a complete bipartite subgraph in $G$ between $X$ and $Y$ , which implies that $X$ or $Y$ is small. Moreover, if $X$ is big and $Y_{\_}1,\dots,Y_{\_}r$ are the neighbours of $X$ for which $XY_{\_}i$ is black, then there is a complete bipartite subgraph in $G$ between $X$ and $Y_{\_}1\cup\dots\cup Y_{\_}r$ , implying $|Y_{\_}1\cup\dots\cup Y_{\_}r|\leqslant s-1$ .

Consider the first trigraph $G_{\_}{\mathcal{P}_{\_}m}$ of the sequence (that is, the largest $m$ ) such that $\mathcal{P}_{\_}m$ contains a part $X_{\_}0$ of size at least $\sqrt{n}$ . Thus $X_{\_}0$ is big (for large $n$ ). Let $x:=\lvert X_{\_}0\rvert$ and $t:=\lceil\sqrt{x}\rceil$ . By the choice of $m$ , we have $\sqrt{n}\leqslant x\leqslant 2\sqrt{n}$ , and every part in $\mathcal{P}_{\_}m$ , except $X_{\_}0$ , has size less than $\sqrt{n}$ .

We now show there are distinct parts $X_{\_}0,X_{\_}1,\ldots,X_{\_}t\in\mathcal{P}_{\_}m$ such that $\lvert X_{\_}i\rvert\geqslant\frac{\beta x}{4ki}$ for each $i\in\{1,\dots,t\}$ , and $\{X_{\_}0,X_{\_}1,\dots,X_{\_}t\}$ induce a connected red subgraph in $G_{\_}{\mathcal{P}_{\_}m}$ . Assume that $X_{\_}0,X_{\_}1,\dots,X_{\_}i$ satisfy these properties for some $i\in\{0,\dots,t-1\}$ . We now show how to find $X_{\_}{i+1}$ . For $j\in\{1,\dots,i\}$ ,

|X_{\_}j|\geqslant\frac{\beta x}{4kj}\geqslant\frac{\beta x}{4k(t-1)}\geqslant\frac{\beta x}{4k\sqrt{x}}\geqslant\frac{\beta\sqrt{x}}{4k}\geqslant\frac{\beta n^{1/4}}{4k}\geqslant s\text{ (for large $n$)}.

So $X_{\_}0,X_{\_}1,\dots,X_{\_}i$ are all big. Let $Y_{\_}1,\dots,Y_{\_}p$ be the parts of $\mathcal{P}_{\_}m\setminus\{X_{\_}0,\dots,X_{\_}i\}$ joined to $X_{\_}0\cup\dots\cup X_{\_}i$ by black edges. As argued above, $|Y_{\_}1\cup\dots\cup Y_{\_}p|\leqslant(i+1)(s-1)$ . Let $Z_{\_}1,\dots,Z_{\_}q$ be the parts of $\mathcal{P}_{\_}m\setminus\{X_{\_}0,\dots,X_{\_}i\}$ joined to $X_{\_}0\cup\dots\cup X_{\_}i$ by red edges. Each of $X_{\_}0,\dots,X_{\_}i$ are incident to at most $2k$ red edges in $G_{\_}{\mathcal{P}_{\_}m}$ (since graphs of bandwidth $k$ have maximum degree at most $2k$ ). So $q\leqslant 2k(i+1)$ . On the other hand, $\lvert X_{\_}0\cup\dots\cup X_{\_}i\rvert\leqslant(i+1)x\leqslant tx\leqslant\frac{n}{2}$ , implying $|Y_{\_}1\cup\dots\cup Y_{\_}p|+|Z_{\_}1\cup\dots\cup Z_{\_}q|\geqslant|N_{\_}G(X_{\_}0\cup\dots\cup X_{\_}i)|\geqslant\beta x$ and $|Z_{\_}1\cup\dots\cup Z_{\_}q|\geqslant\beta x-(i+1)(s-1)\geqslant\frac{\beta x}{2}$ (for large $n$ ). Let $X_{\_}{i+1}$ be the largest of $Z_{\_}1,\dots,Z_{\_}q$ . So $|X_{\_}{i+1}|\geqslant\frac{\beta x}{2q}\geqslant\frac{\beta x}{4k(i+1)}$ , and $\{X_{\_}0,X_{\_}1,\dots,X_{\_}{i+1}\}$ induces a connected red graph in $G_{\_}{\mathcal{P}_{\_}m}$ , as desired. Hence there are distinct parts $X_{\_}0,X_{\_}1,\ldots,X_{\_}t\in\mathcal{P}_{\_}m$ such that $\lvert X_{\_}i\rvert\geqslant\frac{\beta x}{4ki}$ for each $i\in\{1,\dots,t\}$ , and $\{X_{\_}0,X_{\_}1,\dots,X_{\_}t\}$ induces a connected red subgraph in $G_{\_}{\mathcal{P}_{\_}m}$ . As shown above, $X_{\_}0,\dots,X_{\_}t$ are all big.

Let $H$ be the connected component of $G_{\_}{\mathcal{P}_{\_}m}$ containing $X_{\_}0,\dots,X_{\_}t$ . Consider a vertex-ordering of $H$ with bandwidth at most $k$ . Since $\{X_{\_}0,X_{\_}1,\ldots,X_{\_}t\}$ induces a connected red subgraph of $H$ , there is a set $I$ of $kt+1$ consecutive vertices in this ordering of $H$ containing $X_{\_}0,\dots,X_{\_}t$ and with at most $k-1$ parts strictly between ‘consecutive’ $X_{\_}i$ s.

Let $Z$ be the union of all the big parts in $I$ . So $\lvert Z\rvert\leqslant(kt+1)x\leqslant\frac{n}{2}$ (for large $n$ ), implying

\lvert N_{\_}G(Z)\rvert\geqslant\beta\lvert Z\rvert\geqslant\beta\lvert X_{\_}1\cup\dots\cup X_{\_}t\rvert\geqslant\frac{\beta^{2}x}{4k}\sum_{\_}{i=1}^{t}\frac{1}{i}\geqslant\frac{\beta^{2}x\ln t}{4k}.

We now upper bound $|N_{\_}G(Z)|$ . Each vertex in $N_{\_}G(Z)$ is either in:

•

a small part of $\mathcal{P}_{\_}m$ in $I$ ,
•

a part of $\mathcal{P}_{\_}m$ adjacent to $I$ in $H$ , or
•

a part of $\mathcal{P}_{\_}m$ outside $H$ .

There are at most $(kt+1)(s-1)$ vertices in small parts of $\mathcal{P}_{\_}m$ in $I$ . There are at most $2k$ parts of $\mathcal{P}_{\_}m$ adjacent to $I$ in $H$ ( $k$ to the left of $I$ , and $k$ to the right), and each such part has at most $x$ vertices, thus contributing at most $2kx$ vertices to $N_{\_}G(Z)$ . Each big part in $I$ is incident to at most $s-1$ vertices in parts outside $H$ (since the corresponding edges are black), so there are at most $(kt+1)(s-1)$ vertices in $N_{\_}G(Z)$ of the third type. Hence

\frac{\beta^{2}x\ln t}{8k}\leqslant|N_{\_}G(Z)|\leqslant(kt+1)(s-1)+2kx+(kt+1)(s-1).

This is the desired contradiction, since the left-hand side is $\Theta(\sqrt{n}\log n)$ and right-hand side is $\Theta(\sqrt{n})$ for fixed $k,s,\beta$ . ∎

7 Tied and Separated Parameters

Let $\preceq$ be the preorder, where for graph parameters $f_{\_}1$ and $f_{\_}2$ , define $f_{\_}1\preceq f_{\_}2$ if there exists a function $g$ such that $f_{\_}1(G)\leqslant g(f_{\_}2(G))$ for every graph $G$ . Graph parameters $f_{\_}1$ and $f_{\_}2$ are tied (also called functionally equivalent) if $f_{\_}1\preceq f_{\_}2$ and $f_{\_}2\preceq f_{\_}1$ . For example, Bonnet et al. [7] showed that total twin-width is tied to linear rank-width, while component twin-width, clique-width and boolean-width are tied.

Define $f_{\_}1\precneq f_{\_}2$ to mean $f_{\_}1\preceq f_{\_}2$ and $f_{\_}2\not\preceq f_{\_}1$ . For example, $\operatorname{tww}\precneq{\operatorname{bw}}^{\downarrow}$ (since for every graph $G$ , we have $\Delta(G)\leqslant 2\operatorname{bw}(G)$ implying $\operatorname{tww}(G)\leqslant 2\,{\operatorname{bw}}^{\downarrow}(G)$ , but there are bounded degree expanders with twinwidth 6 [4] and unbounded reduced bandwidth by Theorem 31). Graph parameters $f_{\_}1$ and $f_{\_}2$ are separated if $f_{\_}1\precneq f_{\_}2$ or $f_{\_}2\precneq f_{\_}1$ (that is, they are not tied).

Recall that in the context of reduction sequences, it only makes sense to consider graph parameters that are unbounded on stars. This motivates the following definition. For a graph parameter $f$ let $f+\Delta$ be the graph parameter defined by $(f+\Delta)(G):=f(G)+\Delta(G)$ . This section shows that ${\Delta}^{\downarrow}$ , ${(\Delta+\operatorname{tw})}^{\downarrow}$ , ${(\Delta+\operatorname{pw})}^{\downarrow}$ and ${\operatorname{bw}}^{\downarrow}$ are separated (even within graphs).

Theorem 32.

${\Delta}^{\downarrow}\precneq{(\Delta+\operatorname{tw})}^{\downarrow}\precneq{(\Delta+\operatorname{pw})}^{\downarrow}\precneq{\operatorname{bw}}^{\downarrow}$ .

The proof of Theorem 32 uses a lemma of Bergé et al. [3].

For every graph $G$ , let $\operatorname{red}(G)$ be the trigraph $G^{\prime}=(V(G^{\prime})=V(G),E(G^{\prime})=\emptyset,R(G^{\prime})=E(G))$ obtained by making all its edges red. An induced subtrigraph of $G$ is another trigraph $H$ obtained by removing some vertices from $G$ , and $G$ is then called a supertrigraph of $H$ . Note that ${f}^{\downarrow}(G)$ is well-defined for any graph parameter $f$ and any trigraph $G$ (since reduction sequences are defined for trigraphs $G$ ).

The 2-blowup of a graph $G$ , denoted by $G\,\rotatebox{90.0}{$\bowtie$}K_{\_}2$ , is the graph obtained by replacing each vertex $u\in V(G)$ by two non-adjacent vertices $u_{\_}1,u_{\_}2$ , and replacing each edge $uv\in E(G)$ by four edges $u_{\_}1v_{\_}1,u_{\_}1v_{\_}2,u_{\_}2v_{\_}1,u_{\_}2v_{\_}2$ .

Lemma 33 (essentially Lemma 10 in [3]).

For every connected graph $H$ of maximum degree $d$ , there is a graph $G$ admitting a partial reduction sequence $G_{\_}n,\ldots,G_{\_}i$ such that:

•

$\Delta(\widetilde{G_{\_}k})\leqslant 2d$ for every $k\in\{i,i+1,\ldots,n\}$ ,
•

each connected component of $\widetilde{G_{\_}k}$ is a subgraph of $G\,\rotatebox{90.0}{$\bowtie$}K_{\_}2$ ,
•

$G_{\_}i$ is isomorphic to $\operatorname{red}(H)$ ,
•

and every (full) reduction sequence of $G$ goes through a supertrigraph of $\operatorname{red}(H)$ or a trigraph with red maximum degree at least $|V(H)|$ .

Proof Sketch.

In Lemma 10 of [3], the second item does not appear, and the second option of the fourth item consists of going through a trigraph of red maximum degree at least $2d+1$ . The lemma is actually shown in greater generality (see Lemma 11 of [3]) and accounts for trigraphs possibly having black edges and a disconnected red graph. Since we do not need this general form here, we can simplify the construction.

The graph $G$ is built as follows, where $t:=\lvert V(H)\rvert^{\lvert V(H)\rvert}+\lvert V(H)\rvert$ . For every vertex $v\in V(H)$ , add to $G$ a clique $v_{\_}1,\ldots,v_{\_}t$ . We informally refer to $\{\{v_{\_}1,\ldots,v_{\_}t\}:v\in V(H)\}$ as the cliques of $G$ . For each edge $vw\in E(H)$ , add to $E(G)$ the matching $v_{\_}1w_{\_}1,v_{\_}2w_{\_}2,\ldots,v_{\_}tw_{\_}t$ .

We now describe the partial reduction sequence of $G$ satisfying the first three items. For every $v\in V(H)$ , identify $v_{\_}1$ and $v_{\_}2$ , and call the resulting vertex $v^{\prime}_{\_}2$ . Then for every $v\in V(H)$ , identify $v^{\prime}_{\_}2$ and $v_{\_}3$ , and call the resulting vertex $v^{\prime}_{\_}3$ ; and so on, until every clique of every $v\in V(H)$ has been identified to a single vertex. It is straightforward to check that this partial reduction sequence satisfies the first three items.

The proof of the fourth item follows the proof of Statement 5 in Lemma 11 in [3]. We sketch the argument here, since the situation is simpler. If two parts of $G$ intersecting different cliques of $G$ are identified, the red degree of the resulting part is at least the number $s$ of other parts intersecting these two cliques, possibly minus 2. Thus the second condition of the item is satisfied unless $s<\lvert V(H)\rvert+2$ . We may now assume that immediately before the first such identification, there is a part $P_{\_}v$ of size at least $\lvert V(H)\rvert^{\lvert V(H)\rvert-1}$ entirely contained within the clique of $v\in V(H)$ . Let $w$ be a neighbour of $v$ in $H$ . For the red degree of $P_{\_}v$ to be less than $\lvert V(H)\rvert$ , the $\lvert P_{\_}v\rvert$ matched vertices in the clique of $w$ , have to be in less than $\lvert V(H)\rvert$ parts. This means that the largest of those parts, $P_{\_}w$ , has size at least $\lvert V(H)\rvert^{\lvert V(H)\rvert-2}$ . Since $H$ is connected, we continue this reasoning along a spanning tree of $H$ , and exhibit a collection $\{P_{\_}u:u\in V(H)\}$ of parts inducing the trigraph $\operatorname{red}(H)$ . ∎

The next lemma says that, for graph parameters $f$ and $g$ satisfying various properties, $f\precneq g$ implies ${f}^{\downarrow}\precneq{g}^{\downarrow}$ . A parameter $f$ is 2-blowup-closed if there is a function $g:\mathbb{N}_{\_}0\to\mathbb{N}_{\_}0$ such that $f(G\,\rotatebox{90.0}{$\bowtie$}K_{\_}2)\leqslant g(f(G))$ for every graph $G$ .

Lemma 34.

Let $f$ and $g$ be monotone graphs parameters such that:

•

$f\precneq g$ ,
•

$f$ is union-closed and 2-blowup-closed,
•

there is a non-decreasing function $q^{\prime}:\mathbb{N}_{\_}0\to\mathbb{N}_{\_}0$ satisfying $\lim_{\_}{n\to\infty}q^{\prime}(n)=\infty$ and $g(G)\geqslant q^{\prime}(\Delta(G))$ for every graph $G$ , and
•

there is a constant $c\in\mathbb{N}$ such that for every $n\in\mathbb{N}$ there is a connected graph $H_{\_}n$ on at least $n$ vertices with $\lim_{\_}{n\to\infty}g(H_{\_}n)=\infty$ and ${f}^{\downarrow}(\operatorname{red}(H))\leqslant c$ .

Then ${f}^{\downarrow}\precneq{g}^{\downarrow}$ .

Proof.

Let $t(H)$ be the graph $G$ from Lemma 33 given graph $H$ . Define $\mathcal{F}:=\{t(H_{\_}n):n\in\mathbb{N}\}$ . Since $f\preceq g$ , it is immediate that ${f}^{\downarrow}\preceq{g}^{\downarrow}$ . To prove that ${g}^{\downarrow}\not\preceq{f}^{\downarrow}$ , we show that ${f}^{\downarrow}$ is bounded on $\mathcal{F}$ , but ${g}^{\downarrow}$ is unbounded.

We first show that ${f}^{\downarrow}$ is bounded on $\mathcal{F}$ . Let $G=t(H)\in\mathcal{F}$ . By Lemma 33, there is a partial reduction sequence $G_{\_}{\lvert V(G)\rvert},\ldots,G_{\_}i$ of $G$ such that $G_{\_}i$ is isomorphic to $\operatorname{red}(H)$ , and every red graph $\widetilde{G_{\_}k}$ (for $k\in\{i,\ldots,\lvert V(G)\rvert\}$ ) is a disjoint union of subgraphs of the 2-blowup of $H$ . Since ${f}^{\downarrow}(\operatorname{red}(H))\leqslant c$ , in particular, $f(H)\leqslant c$ . Since $f$ is monotone, union-closed and 2-blowup-closed, there is a function $q:\mathbb{N}_{\_}0\to\mathbb{N}_{\_}0$ such that $f(\widetilde{G_{\_}k})\leqslant f(H\,\rotatebox{90.0}{$\bowtie$}K_{\_}2)\leqslant q(f(H))\leqslant q(c)$ . By assumption ${f}^{\downarrow}(G_{\_}i)\leqslant c$ , thus $G$ has a (full) reduction sequence witnessing that ${f}^{\downarrow}(G)\leqslant\max(q(c),c)$ .

We now show that ${g}^{\downarrow}$ is unbounded on $\mathcal{F}$ . For the sake of contradiction, suppose there exists $c^{\prime}\in\mathbb{N}$ such that ${g}^{\downarrow}(G^{\prime})\leqslant c^{\prime}$ for every $G^{\prime}\in\mathcal{F}$ . Let $n\in\mathbb{N}$ be such that $g(H_{\_}n)>c^{\prime}$ and $q^{\prime}(n)>c^{\prime}$ . By assumption such an integer always exists. Consider $G:=t(H_{\_}n)\in\mathcal{F}$ . By Lemma 33, every reduction sequence of $G$ either goes through a trigraph $Y$ with red maximum degree $\lvert V(H_{\_}n)\rvert\geqslant n$ or through a supertrigraph $Z$ of $\operatorname{red}(H_{\_}n)$ . In the former case, $g(\widetilde{Y})\geqslant q^{\prime}(\Delta(\widetilde{Y}))\geqslant q^{\prime}(n)>c^{\prime}$ . In the latter case, since $g$ is monotone, ${g}^{\downarrow}(Z)\geqslant{g}^{\downarrow}(\operatorname{red}(H_{\_}n))\geqslant g(H_{\_}n)>c^{\prime}$ . Both cases imply that ${g}^{\downarrow}(G)>c^{\prime}$ , which contradicts the boundedness of ${g}^{\downarrow}$ on $\mathcal{F}$ . ∎

Proof of Theorem 32.

First observe that $\Delta$ , $\Delta+\operatorname{tw}$ , $\Delta+\operatorname{pw}$ and $\operatorname{bw}$ are monotone, union-closed and 2-blowup-closed with function $n\mapsto 2n+1$ . If $g$ is any of these parameters, then $g(G)\geqslant\lfloor\frac{\Delta(G)}{2}\rfloor$ , which provides the $q^{\prime}$ function in Lemma 34.

The first claim, ${\Delta}^{\downarrow}\precneq{(\Delta+\operatorname{tw})}^{\downarrow}$ , follows from Lemma 34 where $H_{\_}n$ is the $n\times n$ planar grid graph, which has $(\Delta+\operatorname{tw})(H_{\_}n)\geqslant n$ (see [27]) and ${\Delta}^{\downarrow}(\operatorname{red}(H_{\_}n))=4$ (see [9]).

The second claim, ${(\Delta+\operatorname{tw})}^{\downarrow}\precneq{(\Delta+\operatorname{pw})}^{\downarrow}$ , follows from Lemma 34 where $H_{\_}n$ is the complete binary tree of height $n$ , which has $(\Delta+\operatorname{pw})(H_{\_}n)\geqslant\frac{n}{2}$ (see [43]) and ${(\Delta+\operatorname{tw})}^{\downarrow}(\operatorname{red}(H_{\_}n))\leqslant 4$ (see [9]).

Finally, ${(\Delta+\operatorname{pw})}^{\downarrow}\precneq{\operatorname{bw}}^{\downarrow}$ follows from Lemma 34 where $H_{\_}n$ is the tree defined in Footnote 4 on page 4, which has $\operatorname{bw}(H_{\_}n)\geqslant\frac{n}{3}$ and ${(\Delta+\operatorname{pw})}^{\downarrow}(\operatorname{red}(H_{\_}n))\leqslant 5$ . The latter can be seen by iteratively identifying any leaf with its parent (in any order), which yields only subtrigraphs of $H_{\_}n$ and can be done until the trigraph has a single vertex. Throughout, the red graphs have maximum degree at most 3 and pathwidth at most 2. ∎

8 Open Problems

Our results lead to several interesting open problems.

Parameter tied to reduced bandwidth?

Recall that component twin-width and clique-width are tied [7]. Is there a ‘natural’ graph parameter tied to reduced bandwidth? This is related to the question of which dense graph classes have bounded reduced bandwidth. Our results for powers give such examples. Complements provide other examples: if $\overline{G}$ is the complement of a graph $G$ , then ${\operatorname{bw}}^{\downarrow}(\overline{G})={\operatorname{bw}}^{\downarrow}(G)$ , since any reduction sequence for $G$ defines a reduction sequence for $\overline{G}$ with equal red graphs. In general, ${f}^{\downarrow}(G)={f}^{\downarrow}(\overline{G})$ for every $G$ and $f$ . Bonnet et al. [5] proved that unit interval graphs have twin-width 2; in fact, they have a reduction sequence in which every red graph is a disjoint union of paths. Thus unit interval graphs have reduced bandwidth 1.

Best possible parameters:

Is bandwidth the largest possible parameter $f$ such that planar graphs have bounded ${f}^{\downarrow}$ ? We formalise this question as follows. Say a graph parameter $f$ is continuous if there exists a function $g$ such that $f(G)\leqslant g(f(G-e))$ for every graph $G$ and edge $e\in E(G)$ , and $f(G)\leqslant g(f(G-v))$ for every graph $G$ and isolated vertex $v$ of $G$ . All the graph parameters studied in this paper are continuous. Is there a continuous⁹⁹9We need to assume $f$ is continuous because of the following example. For a graph $G$ , define $f(G):=\operatorname{bw}(G)$ if $\operatorname{bw}(G)\leqslant 466$ and $f(G):=|V(G)|$ otherwise. So $\operatorname{bw}\precneq f$ and planar graphs have bounded ${f}^{\downarrow}$ , but $f$ is not continuous. graph parameter $f$ such that $\operatorname{bw}\precneq f$ and planar graphs have bounded ${f}^{\downarrow}$ ? Maximum component size is not such a parameter, since planar grid graphs have unbounded clique-width [24] and therefore have unbounded ${\star}^{\downarrow}$ . In general, for a graph class $\mathcal{G}$ , what is a continuous graph parameter $f$ such that ${f}^{\downarrow}$ is bounded on $\mathcal{G}$ , and ${g}^{\downarrow}$ is unbounded on $\mathcal{G}$ for every parameter $g$ with $f\precneq g$ . Does such a graph parameter always exist?

Lower Bounds:

A non-trivial lower bound on reduced bandwidth is Theorem 31 for expanders. Stronger lower bounds are plausible. For example, does every monotone graph class excluding a fixed complete bipartite subgraph and with bounded reduced bandwidth have polynomial expansion? It is even plausible that the degree of the polynomial is an absolute constant. Does every monotone graph class excluding a fixed complete bipartite subgraph and with bounded reduced bandwidth have linear expansion? Graphs with bounded row-treewidth have linear expansion. A good example to consider is the class of 3-dimensional grids, which we guess have unbounded reduced bandwidth.

Subdivisions:

Bonnet et al. [4] showed that $t$ -subdivisions of $K_{\_}n$ have bounded twin-width if and only if $t\in\Omega(\log n)$ . No explicit bound on the twin-width was given. Recently, Bergé et al. [3] proved that every $(\geqslant 2\log n)$ -subdivision of any $n$ -vertex graph has twin-width at most 4. The proof constructs a reduction sequence in which every red graph is a forest. So this class of graphs has exponential expansion, is $K_{\_}{2,2}$ -free, and has ${(\operatorname{tw}+\Delta)}^{\downarrow}\leqslant 5$ . The proof in [3] can be adapted¹⁰¹⁰10In the proof of Theorem 7 in [3], replace the virtual binary red tree by an $n$ -vertex red path, and observe that running the same sequence produces a red caterpillar with maximum degree 4 and at most one vertex of degree 4; refer to Figures 3 and 4 in [3]. Such caterpillars have bandwidth at most 2. to show that every $(\geqslant n)$ -subdivision of any $n$ -vertex graph has reduced bandwidth at most 2. Is this result best possible, in the sense that if $K_{\_}n^{(p)}$ is the $p$ -subdivision of $K_{\_}n$ and ${\operatorname{bw}}^{\downarrow}(K_{\_}n^{(p)})\leqslant O(1)$ , must $p\in\Omega(n)$ ? Since $\Omega(n)$ -subdivisions of $n$ -vertex graphs have linear expansion, a positive answer to this question would be good evidence for the suggestion above that graph classes with bounded reduced bandwidth and excluding a fixed complete bipartite subgraph have linear expansion.

Acknowledgements

This research was initiated at the Dagstuhl workshop Sparsity in Algorithms, Combinatorics and Logic (September 2021). Many thanks to the organisers and other participants.

After the initial announcement of our results, Jacob and Pilipczuk [30] proved that planar graphs have twin-width at most 183. Their proof is based on the proof of Theorem 2.

References

Ahn et al. [2021] Jungho Ahn, Kevin Hendrey, Donggyu Kim, and Sang-il Oum. Bounds for the twin-width of graphs. 2021, arXiv:2110.03957.
Balabán and Hlinený [2021] Jakub Balabán and Petr Hlinený. Twin-width is linear in the poset width. In Petr A. Golovach and Meirav Zehavi, eds., Proc. 16th Int’l Symp. on Parameterized and Exact Computation (IPEC ’21), vol. 214 of Leibniz Int. Proc. Inform., pp. 6:1–6:13. Schloss Dagstuhl, 2021.
Bergé et al. [2021] Pierre Bergé, Édouard Bonnet, and Hugues Déprés. Deciding twin-width at most 4 is NP-complete. 2021, arXiv:2112.08953.
Bonnet et al. [2021a] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Proc. 2021 ACM-SIAM Symp. on Discrete Algorithms (SODA ’21), pp. 1977–1996. SIAM, 2021a.
Bonnet et al. [2021b] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set, min dominating set, and coloring. In Nikhil Bansal, Emanuela Merelli, and James Worrell, eds., Proc. 48th Int’l Coll. on Automata, Languages, and Programming (ICALP ’21), vol. 198 of Leibniz Int. Proc. Inform., pp. 35:1–35:20. Schloss Dagstuhl, 2021b. arXiv:2007.14161.
Bonnet et al. [2021c] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width IV: ordered graphs and matrices. In Proc. Annual ACM Symp. on Theory of Computing (STOC ’22), to appear. ACM, 2021c. arXiv:2102.03117.
Bonnet et al. [2022a] Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, and Stéphan Thomassé. Twin-width VI: the lens of contraction sequences. In Proc. 2022 Annual ACM-SIAM Symp. on Discrete Algorithms (SODA ’22), pp. 1036–1056. 2022a.
Bonnet et al. [2021d] Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Twin-width and polynomial kernels. In Petr A. Golovach and Meirav Zehavi, eds., Proc. 16th Int’l Symp. Parameterized and Exact Computation (IPEC ’21), vol. 214 of Leibniz Int. Proc. Inform., pp. 10:1–10:16. Schloss Dagstuhl, 2021d.
Bonnet et al. [2022b] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. J. ACM, 69(1):#3, 2022b. arXiv:2004.14789.
Bonnet et al. [2021e] Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, and Stéphan Thomassé. Twin-width and permutations. 2021e, arXiv:2102.06880.
Bose et al. [2021] Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, Pat Morin, and David R. Wood. Separating layered treewidth and row treewidth. arXiv:2105.01230, 2021.
Bose et al. [2022] Prosenjit Bose, Pat Morin, and Saeed Odak. An optimal algorithm for product structure in planar graphs. 2022, arXiv:2202.08870.
Chen et al. [2002] Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou. Map graphs. J. ACM, 49(2):127–138, 2002.
Chung and Seymour [1989] Fan R. K. Chung and Paul D. Seymour. Graphs with small bandwidth and cutwidth. Discret. Math., 75(1-3):113–119, 1989.
Dreier et al. [2022] Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, and Jean-Florent Raymond. Twin-width and generalized coloring numbers. Discret. Math., 345(3):112746, 2022.
Dujmović et al. [2017] Vida Dujmović, David Eppstein, and David R. Wood. Structure of graphs with locally restricted crossings. SIAM J. Discrete Math., 31(2):805–824, 2017.
Dujmović et al. [2020] Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. J. ACM, 67(4):#22, 2020.
Dujmović et al. [2019] Vida Dujmović, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. 2019, arXiv:1907.05168.
Eickmeyer et al. [2017] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, eds., Proc. 44th Int’l Coll. on Automata, Languages, and Programming (ICALP ’17), vol. 80 of Leibniz Int. Proc. Inform., pp. 63:1–63:14. Schloss Dagstuhl, 2017.
Fomin et al. [2012] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA ’12), pp. 1563–1575. SIAM, 2012.
Fox and Wei [2017] Jacob Fox and Fan Wei. On the number of cliques in graphs with a forbidden minor. J. Combin. Theory Ser. B, 126:175–197, 2017.
Gajarský et al. [2017] Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219–242, 2017.
Gajarský et al. [2021] Jakub Gajarský, Michal Pilipczuk, and Szymon Torunczyk. Stable graphs of bounded twin-width. 2021, arXiv:2107.03711.
Golumbic and Rotics [2000] Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci., 11(3):423–443, 2000.
Grohe et al. [2018] Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. Coloring and covering nowhere dense graphs. SIAM J. Discrete Math., 32(4):2467–2481, 2018.
Guillemot and Marx [2014] Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proc. 25th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA ’14), pp. 82–101. 2014.
Harvey and Wood [2017] Daniel J. Harvey and David R. Wood. Parameters tied to treewidth. J. Graph Theory, 84(4):364–385, 2017.
Hickingbotham and Wood [2021] Robert Hickingbotham and David R. Wood. Shallow minors, graph products and beyond planar graphs. 2021, arXiv:2111.12412.
Hoory et al. [2006] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439–561, 2006.
Jacob and Pilipczuk [2022] Hugo Jacob and Marcin Pilipczuk. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. 2022, arXiv:2201.09749.
Kierstead and Yang [2003] Hal A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number. Order, 20(3):255–264, 2003.
Kostochka [1984] Alexandr V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4(4):307–316, 1984.
Kreutzer et al. [2016] Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The generalised colouring numbers on classes of bounded expansion. In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, eds., 41st Int’l Symp. on Mathematical Foundations of Comput. Sci. (MFCS ’16), vol. 58 of Leibniz Int. Proc. Inform., pp. 85:1–85:13. Schloss Dagstuhl, 2016.
Marcus and Tardos [2004] Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
Mohar and Thomassen [2001] Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins University Press, 2001.
Morin [2021] Pat Morin. A fast algorithm for the product structure of planar graphs. Algorithmica, 83(5):1544–1558, 2021.
Paszke and Pilipczuk [2020] Adam Paszke and Michał Pilipczuk. VC density of set systems defnable in tree-like graphs. 2020, arXiv:2003.14177.
Pilipczuk et al. [2021] Michał Pilipczuk, Marek Sokołowski, and Anna Zych-Pawlewicz. Compact representation for matrices of bounded twin-width. 2021, arXiv:2110.08106.
Pilipczuk and Sokołowski [2022] Michał Pilipczuk and Marek Sokołowski. Graphs of bounded twin-width are quasi-polynomially $\chi$ -bounded. 2022, arXiv:2202.07608.
Przybyszewski [2022] Wojciech Przybyszewski. VC-density and abstract cell decomposition for edge relation in graphs of bounded twin-width. 2022, arXiv:2202.04006.
Reidl et al. [2019] Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos S. Stavropoulos. Characterising bounded expansion by neighbourhood complexity. Eur. J. Comb., 75:152–168, 2019.
Robertson and Seymour [1986] Neil Robertson and Paul Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986.
Scheffler [1989] Petra Scheffler. Die baumweite von graphen als ein maß für die kompliziertheit algorithmischer probleme. Ph.D. thesis, Akademie der Wissenschaften der DDR, Berlin, Germany, 1989.
Schidler and Szeider [2021] André Schidler and Stefan Szeider. A SAT approach to twin-width. 2021, arXiv:2110.06146.
Thomason [1984] Andrew Thomason. An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc., 95(2):261–265, 1984.
Ueckerdt et al. [2021] Torsten Ueckerdt, David R. Wood, and Wendy Yi. An improved planar graph product structure theorem. 2021, arXiv:2108.00198.
van den Heuvel and Wood [2018] Jan van den Heuvel and David R. Wood. Improper colourings inspired by Hadwiger’s conjecture. J. London Math. Soc., 98:129–148, 2018. arXiv:1704.06536.
Wood [2007] David R. Wood. On the maximum number of cliques in a graph. Graphs Combin., 23(3):337–352, 2007.
Wood [2016] David R. Wood. Cliques in graphs excluding a complete graph minor. Electronic J. Combinatorics, 23:P3.18, 2016.

	$\displaystyle\|Z\|\,=\,\|Z^{\prime}\|+\|Z^{\prime\prime}\|-1$	$\displaystyle\leqslant c(\|X^{\prime}\|-2)+1+c(\|X^{\prime\prime}\|-2)+1-1$
		$\displaystyle=c(\|X^{\prime}\|+\|X^{\prime\prime}\|-4)+1$
		$\displaystyle=c(\|X\|-2)+1,$

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

Abstract

1 Introduction

2 Preliminaries

2.1 Tree-decompositions

2.2 Sparsity

2.3 Product Structure Theorems

Theorem 1 ([17, 46]).

Theorem 2 ([17, 46]).

Theorem 3 ([17]).

Theorem 4 ([18]).

3 Neighbourhood Diversity

3.1 First Neighbourhoods

Lemma 5.

Proof.

Corollary 6.

Lemma 7.

Lemma 8.

Proof.

Lemma 9.

Proof.

Lemma 10.

Proof.

Corollary 11.

Corollary 12.

Proof.

Lemma 13.

Proof.

3.2 Second Neighbourhoods

Lemma 14.

Proof.

Lemma 15.

Lemma 16.

Proof.

Lemma 17.

Proof.

Corollary 18.

4 Bounded Row Treewidth Classes

Lemma 19.

Proof.

Lemma 20.

Proof.

Corollary 21.

Corollary 22.

Theorem 23.

Proof.

Theorem 24.

Proof.

Theorem 25.

Proof.

Theorem 26.

Proof.

5 Proper Minor-Closed Classes

Lemma 27.

Proof.

Lemma 28.

Proof.

Theorem 29.

Proof.

Theorem 30.

6 Expanders

Theorem 31.

Proof.

7 Tied and Separated Parameters

Theorem 32.

Lemma 33 (essentially Lemma 10 in [3]).

Proof Sketch.

Lemma 34.

Proof.

Proof of Theorem 32.

8 Open Problems

Parameter tied to reduced bandwidth?

Best possible parameters:

Lower Bounds:

Subdivisions:

Acknowledgements

References

Reduced bandwidth: a qualitative
strengthening of twin-width in
minor-closed classes (and beyond)