# A coarse geometric approach to graph layout problems

Wanying Huang  McGill University, Montreal, Canada  David Hume  University of
Birmingham, UK  Samuel J. Kelly  University of Bristol, UK  Ryan Lam
University of Bristol, UK

###### Abstract

We define a range of new coarse geometric invariants based on various graph-
theoretic measures of complexity for finite graphs, including: treewidth,
pathwidth, cutwidth, search number, topological bandwidth, bandwidth, minimal
linear arrangment, sumcut, profile, vertex and edge separation. We prove that,
for bounded degree graphs, these invariants can be used to define functions
which satisfy a strong monotonicity property, namely they are monotonically
non-decreasing with respect to regular maps, and as such have potential
applications in coarse geometry and geometric group theory. On the graph-
theoretic side, we prove asymptotically optimal upper bounds on the treewidth,
pathwidth, cutwidth, search number, topological bandwidth, vertex separation,
edge separation, minimal linear arrangement, sumcut and profile for the family
of all finite subgraphs of any bounded degree graph whose separation profile
is known to be of the form $r^{a}\log(r)^{b}$ for some $a>0$. This large class
includes the Diestel-Leader graph, all Cayley graphs of non-virtually cyclic
polycyclic groups, uniform lattices in almost all connected unimodular Lie
groups, and certain hyperbolic groups.

##  1 Introduction

The primary objects of study in this paper are graph layout problems: finding
linear orderings or decompositions of graphs which minimise a specified cost
function. Examples of such invariants include treewidth, cutwidth and
bandwidth. There are many motivations for finding upper bounds on these
invariants coming from a variety of areas including: optimization of networks
for parallel computer architectures, VLSI circuit design, information
retrieval, numerical analysis, computational biology, graph theory, scheduling
and archaeology (cf. [DPS02], [Bod06] and references therein). Typically,
realising the minimal possible value of these invariants is NP-hard (see, for
example [GJ79] for cutwidth and [ACP87] for treewidth). Despite this, there
are asymptotically optimal upper bounds for large classes of graphs. One
noteworthy result in the context of this paper is that for every $m$-vertex
graph $H$, any $n$-vertex graph which does not contain $H$ as a minor has
treewidth at most $m^{3/2}n^{1/2}$ [AST90, (1.8)]. The goal of this paper is
to take a “large-scale” viewpoint on these invariants which will enable us to
give asymptotically optimal upper and lower bounds on the growth of some of
these graph layout parameters for subgraphs of particular infinite graphs of
bounded degree. The motivation for working in this level of generality comes
from the study of (obstructions to) regular maps.

Until recently, there were very few methods to obstruct regular maps between
graphs, but in the last decade the number and variety of tools has greatly
increased [BST12, HMT20, HMT22, BH21, HMT23]. This paper is another part of
this proliferation of new techniques.

A map between the vertex sets of two bounded degree graphs is regular if it is
Lipschitz (with respect to the shortest path metrics) and preimages of
vertices have uniformly bounded cardinality. The inclusion of one graph as a
subgraph of another is always a regular map; also, given two finitely
generated groups $H,G$, there is a regular map from a Cayley graph of $H$ to a
Cayley graph of $G$ whenever $H$ admits a finite-index subgroup which is
isomorphic to a subgroup of $G$. Thus, the statement that no regular map
exists between two graphs is a strong geometric version of the statement $X$
is not (similar to) a subgraph of $Y$, or $H$ is not (similar to) a subgroup
of $G$. For bounded degree graphs, regular maps generalise both quasi-
isometric and coarse embeddings. These observations give combinatorial and
algebraic motivations for determining obstructions to the existence of regular
maps.

To fix notation, the vertex and edge sets of a graph $\Gamma$ will be denoted
by $V\Gamma$ and $E\Gamma$ respectively, and we write
$\Gamma\leq\Gamma^{\prime}$ to denote that $\Gamma$ is a subgraph of
$\Gamma^{\prime}$. The maximal vertex degree of $\Gamma$ (when it exists) will
be denoted by $\Delta(\Gamma)$ or just $\Delta$ when there is no ambiguity.

###  1.1 Invariants and monotonicity under regular maps

Our main result is that many invariants related to graph layout problems can
be used as obstructions to the existence of regular maps. Specifically, we
will define four spectra of invariants. The first three are denoted
$\operatorname{ec}^{p}$, $\operatorname{vc}^{p}$ and $\ell^{p}$ with
$p\in[1,+\infty]$: they include several well-studied invariants.

  * •

$\operatorname{ec}^{\infty}$ is cutwidth ($\operatorname{cw}$), and
$\operatorname{ec}^{1}=\ell^{1}$ is minimal linear arrangement111also known as
the optimal linear ordering, the edge sum, the minimum-$1$\- sum, the
bandwidth sum or the wirelength problem in other parts of the literature
($\operatorname{mla}$).

  * •

$\operatorname{vc}^{\infty}$ is vertex separation ($\operatorname{vs}$), and
$\operatorname{vc}^{1}$ is sumcut ($\operatorname{sc}$) which is also equal to
profile.

  * •

$\ell^{\infty}$ is bandwidth.

The final class of invariants are denoted $\operatorname{wid}^{G,p}$ and are
indexed by graphs $G$ and $p\in[1,\infty]$. These also include two well-
studied invariants: when $G$ is the disjoint union of all trees or paths,
$\operatorname{wid}^{G,\infty}-1$ equals the treewidth ($\operatorname{tw}$)
or pathwidth ($\operatorname{pw}$) respectively. We note here that for any
finite graph $\Gamma$ and any $G$,
$\operatorname{wid}^{G,1}(\Gamma)=|V\Gamma|$, but for other finite values of
$p$ the invariants are more interesting (cf. Remark 2.5).

We now define our set of invariants

$\mathcal{I}=\bigcup_{p\in[1,\infty]}\left(\left\\{\operatorname{ec}^{p},\operatorname{vc}^{p},\ell^{p}\right\\}\cup\bigcup_{G}\left\\{\operatorname{wid}^{G,p}\right\\}\right).$

######  Theorem 1.1.

Let $X$ and $Y$ be bounded degree graphs and assume $Y$ has infinitely many
edges. If there is a regular map $VX\to VY$, then for every $I\in\mathcal{I}$,
there is a constant $C$ such that for all $r\in\mathbb{N}$

$\displaystyle I_{X}(r)\leq CI_{Y}(Cr+C)+C$

where $I_{X}(r)=\max\left\\{I(\Gamma)\ \left|\ \Gamma\leq X,\ |V\Gamma|\leq
r\right.\right\\}$.

The motivation behind the definition of $I_{X}$ comes from the separation
profile $\operatorname{sep}_{X}$ of Benjamini-Schramm-Timár (where $I$ is the
cutsize cf. Definition 4.1) [BST12]. We will refer to $I_{X}$ as the
$I$-profile of $X$, which we generally consider as a $\simeq$-equivalence
class of functions partially ordered by $\lesssim$, where $f\lesssim g$ if
there is some constant $C$ such that $f(r)\leq Cg(Cr+C)+C$ for all $r$, and
$f\simeq g$ if $f\lesssim g$ and $g\lesssim f$.

###  1.2 Comparing Invariants

Our next goal is to compare these new invariants with each other and to other
cost functions associated to graph layout problems. Firstly, we present some
elementary comparisons of $\ell^{p}$ norms on functions.

######  Theorem 1.2.

For any bounded degree graph $X$ and any $p\in[1,\infty]$:

$\displaystyle\operatorname{ec}^{p}_{X}(r)$
$\displaystyle\simeq\operatorname{vc}^{p}_{X}(r).$

Moreover, for any $p,q\in[1,\infty]$ with $p\leq q$ and any graph $G$:

$\displaystyle\operatorname{ec}^{q}_{X}(r)$
$\displaystyle\lesssim\operatorname{ec}^{p}_{X}(r)\lesssim
r^{\frac{1}{p}-\frac{1}{q}}\operatorname{ec}^{q}_{X}(r),$
$\displaystyle\ell^{q}_{X}(r)$ $\displaystyle\lesssim\ell^{p}_{X}(r)\lesssim
r^{\frac{1}{p}-\frac{1}{q}}\ell^{q}_{X}(r),$
$\displaystyle\operatorname{wid}^{G,q}_{X}(r)$
$\displaystyle\lesssim\operatorname{wid}^{G,p}_{X}(r)\lesssim
r^{\frac{1}{p}-\frac{1}{q}}\operatorname{wid}^{G,q}_{X}.$

Throughout the paper we make the convention that $\frac{1}{\infty}=0$.

Next, using known bounds from the literature, we obtain the following
comparisons. Given any finite graph $\Gamma$ with maximal degree $\Delta$:

  * •

$\operatorname{cut}(\Gamma)\leq\operatorname{tw}(\Gamma)$, [BST12, Lemma 2.3].

  * •

$\operatorname{tw}(\Gamma)\leq\operatorname{pw}(\Gamma)$ by definition.

  * •

$\operatorname{pw}(\Gamma)\leq\operatorname{cw}(\Gamma)$, [Bod88, Theorem
5.4].

  * •

$\operatorname{cw}(\Gamma)\leq\lfloor\frac{1}{2}\Delta\rfloor(\operatorname{sn}(\Gamma)-1)+1$,
[MS89, Theorem 3.2].

  * •

$\operatorname{sn}(\Gamma)\leq\operatorname{tbw}(\Gamma)+1$, [MPS83, Corollary
2.2].

  * •

$\operatorname{tbw}(\Gamma)\leq\operatorname{cw}(\Gamma)$, [MPS83, Corollary
2.1].

  * •

$\operatorname{cw}(\Gamma)\leq\Delta\operatorname{pw}(\Gamma)$, [CS89].

  * •

$\operatorname{tbw}(\Gamma)\leq\operatorname{bw}(\Gamma)$, by definition.

Here $\operatorname{cut}$ is the cutsize, $\operatorname{sn}$ is the search
number and $\operatorname{tbw}$ is the topological bandwidth. We will not
define these notions in this paper, the interested reader is recommended to
check the above papers and the references therein. In order, the above
inequalities prove the relations:

######  Theorem 1.3.

For any bounded degree graph $X$,

$\displaystyle\operatorname{sep}_{X}$
$\displaystyle\lesssim\operatorname{tw}_{X}\lesssim\operatorname{pw}_{X}$
$\displaystyle\operatorname{pw}_{X}$
$\displaystyle\lesssim\operatorname{cw}_{X}\lesssim\operatorname{sn}_{X}\lesssim\operatorname{tbw}_{X}\lesssim\operatorname{cw}_{X}\lesssim\operatorname{pw}_{X}$
$\displaystyle\operatorname{tbw}_{X}$
$\displaystyle\lesssim\operatorname{bw}_{X}.$

In certain cases, we know that the invariants we get definitely differ. For
example, when $X$ is the infinite $3$-regular tree,
$\operatorname{sep}_{X}(r)=\operatorname{tw}_{X}(r)=1$,
$\operatorname{pw}_{X}(r)\simeq\log(r)$ and $\operatorname{bw}_{X}(r)\simeq
r/\log(r)$. We are not aware of an example of a bounded degree graph $X$ where
$\operatorname{sep}_{X}\not\simeq\operatorname{tw}_{X}$, this and other
questions arising from this work are listed in $\S\ref{sec:qu}$.

###  1.3 Calculations

Our next result states that when the separation profile is a “nice” function
and not too small, then all of the invariants mentioned in Theorem 1.3 (except
bandwidth) are $\simeq$-equivalent.

######  Theorem 1.4.

Let $X$ be a bounded degree graph such that $\operatorname{sep}_{X}(r)\lesssim
r^{a}\log(r)^{b}$ with $a>0$ and $b\in\mathbb{R}$. Then

$\operatorname{cw}_{X}(r)\lesssim\left\\{\begin{array}[]{lll}r^{a}\log(r)^{b}&\textrm{if}&a>0\\\
\log(r)^{b+1}&\textrm{if}&a=0\end{array}\right.$

In particular, if $\operatorname{sep}_{X}(r)\simeq r^{a}\log(r)^{b}$ with
$a>0$, then

$\operatorname{sep}_{X}(r)\simeq\operatorname{tw}_{X}(r)\simeq\operatorname{pw}_{X}(r)\simeq\operatorname{cw}_{X}(r)\simeq\operatorname{sn}_{X}(r)\simeq\operatorname{tbw}_{X}(r).$

Moving to lower bounds, we obtain the following result:

######  Theorem 1.5.

For every bounded degree graph $X$ and every $p\in[1,\infty]$,

$\operatorname{vc}^{p}_{X}(r)\gtrsim
r^{\frac{1}{p}}\operatorname{sep}_{X}(r).$

Thus, if $\operatorname{sep}_{X}(r)\simeq r^{a}\log(r)^{b}$ with $a>0$, then
for every $p\in[1,\infty]$

$\operatorname{vc}^{p}_{X}(r)\simeq r^{\frac{1}{p}+a}\log(r)^{b}.$

The class of graphs whose separation profile is known to be of the form
$r^{a}\log(r)^{b}$ with $a>0$ is rich. As a sample, we obtain the following
two results:

######  Corollary 1.6.

Let $X$ be a bounded degree graph such that $\operatorname{sep}_{X}(r)\simeq
r^{1-1/d}$ for some $d>1$. For each
$I\in\\{\operatorname{tw},\operatorname{pw},\operatorname{cw},\operatorname{sn},\operatorname{tbw}\\}$
there is a constant $C=C(X,I)$ such that for every $r\geq 1$

  * •

each $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $I(\Gamma)\leq
Cr^{1-1/d}+C$,

  * •

some $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $I(\Gamma)\geq
C^{-1}r^{1-1/d}-C$.

Moreover, we obtain the following bounds for sumcut and minimal linear
arrangement. For each $J\in\\{\operatorname{sc},\operatorname{mla}\\}$ there
is a constant $C=C(X,J)$ such that for every $r\geq 1$

  * •

each $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $J(\Gamma)\leq
Cr^{2-1/d}+C$,

  * •

some $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $J(\Gamma)\geq
C^{-1}r^{2-1/d}-C$.

Examples of such graphs include products $P\times H$ where $P$ is a vertex
transitive graph of polynomial growth of degree $k$, $H$ is quasi-isometric to
a rank one symmetric space $\mathbb{H}^{m}_{\mathbb{K}}$ and
$d:=k+(m+1)\dim_{\mathbb{R}}\mathbb{K}-2\geq 2$ [HMT20, HMT22]. Other examples
of graphs with separation profiles as above include certain fractal
approximations [GS21] and more general classes of graphs with polynomial
growth [GLC23].

######  Corollary 1.7.

Let $Y$ be a bounded degree graph such that $\operatorname{sep}_{Y}(r)\simeq
r/\log(1+r)$. For each
$I\in\\{\operatorname{tw},\operatorname{pw},\operatorname{cw},\operatorname{sn},\operatorname{tbw}\\}$
there is a constant $C=C(Y,I)$ such that for every $r\geq 1$

  * •

each $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $I(\Gamma)\leq
Cr/\log(1+r)+C$,

  * •

some $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $I(\Gamma)\geq
C^{-1}r/\log(1+r)-C$.

Moreover, for each $J\in\\{\operatorname{sc},\operatorname{mla}\\}$ there is a
constant $C=C(Y,J)$ such that for every $r\geq 1$

  * •

each $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $J(\Gamma)\leq
Cr^{2}/\log(1+r)+C$,

  * •

some $\Gamma\leq X$ with $|\Gamma|\leq r$ satisfies $J(\Gamma)\geq
C^{-1}r^{2}/\log(1+r)-C$.

Examples of such graphs include all Cayley graphs of polycyclic groups with
exponential growth and all uniform lattices in semisimple Lie groups whose
noncompact factor has rank at least $2$, these and further examples can be
found in [HMT22]. More generally, any graph $Y$ which contains a Diestel-
Leader graph and has finite Assouad-Nagata dimension will also satisfy
$\operatorname{sep}_{Y}(r)\simeq r/\log(1+r)$ [Hum17].

When $a=0$ we still find upper bounds and they are optimal in the case of the
$3$-regular tree. However, we suspect that they are not optimal in the
following case.

######  Corollary 1.8.

Let $Z$ be the graph of the tessellation of the hyperbolic plane by right-
angled octagons. For each
$I\in\\{\operatorname{tw},\operatorname{pw},\operatorname{cw},\operatorname{sn},\operatorname{tbw}\\}$
there is a constant $C=C(Z,I)$ such that for every $r\geq 1$, each $\Gamma\leq
X$ with $|\Gamma|\leq r$ satisfies $I(\Gamma)\leq C\log(1+r)^{2}+C$.

Note that when $\Gamma$ is a metric ball in $Z$, then a stronger upper bound
$I(\Gamma)\leq C\log(1+r)+C$ is proved in [KMP01, Proposition 2.3].

More generally, upper and lower bounds can be found in all cases where such
bounds exist for the separation profile, see for instance [HM20, Coz20] for
cases where the separation profile is very small, and very large respectively.

###  1.4 Acknowledgements

This research was conducted during various summer research programmes held at
the University of Bristol under the supervision of the second author. The
first author was participating in a STEM Research Project from Global Summer,
the third and fourth authors were participating in Summer Research Projects
funded by the University of Bristol. The fourth author also gratefully
acknowledges the support of the Bei Shan Tang Foundation through the Lee Hysan
Memorial Scholarship for Overseas Studies.

The second author was supported by the EPSRC grant EP/V027360/1 “Coarse
geometry of groups and spaces”.

The authors would like to thank David Ellis for pointing out several
references, Alice Kerr for bringing the reference [AST90] to their attention,
and Romain Tessera for helpful comments on a draft version of the paper.

##  2 Defining and comparing invariants

###  2.1 Graph decompositions

######  Definition 2.1.

Let $G$ and $\Gamma$ be graphs. A $G$-decomposition of $\Gamma$ is a
collection $\left\\{X_{g}\ \left|\ g\in VG\right.\right\\}$ of subsets of
$V\Gamma$ satisfying the following three conditions:

  1. 1.

$\bigcup_{g\in VG}X_{g}=V\Gamma$,

  2. 2.

for every edge $vw\in E\Gamma$ there is some $g\in VG$ such that
$\\{v,w\\}\subseteq X_{g}$,

  3. 3.

for each $v\in V\Gamma$, the full subgraph of $\left\\{g\in VG\ \left|\ v\in
X_{g}\right.\right\\}$ is connected.

We now introduce a cost associated to $G$-decompositions.

######  Definition 2.2.

For $p\in[1,\infty]$, the $p$-width of a $G$-decomposition of $\Gamma$ is the
$\ell^{p}$ norm of the function $VG\to\mathbb{R}$ given by $g\mapsto|X_{g}|$,
i.e. for $p\in[1,\infty)$, the $p$-width is

$\displaystyle\left(\sum_{g\in VG}|X_{g}|^{p}\right)^{\frac{1}{p}},$

and the $\infty$-width is $\max_{g\in VG}|X_{g}|$.

######  Remark 2.3.

It would be more consistent with the literature to consider the cost function
$g\mapsto|X_{g}|-1$. Our reasons for not doing this are that in the
$\infty$-case the difference of $1$ does not change the cost up to $\simeq$,
and in the case $p\in[1,\infty)$ we do not need to exclude “small”
decompositions (where $|X_{g}|=1$ occurs for “most” $g\in VG$) in the
monotonicity result.

Now we present the first collection of invariants in $\mathcal{I}$.

######  Definition 2.4.

Let $G$ be any graph. The $(G,p)$-width of a graph $\Gamma$ is the minimal
$p$-width over the set of all $G$-decompositions of $\Gamma$. We denote this
by $\operatorname{wid}^{G,p}(\Gamma)$.

Commonly studied examples include treewidth
$\operatorname{tw}(\Gamma)=\operatorname{wid}^{T,\infty}(\Gamma)-1$ and
pathwidth $\operatorname{pw}(\Gamma)=\operatorname{wid}^{P,\infty}(\Gamma)-1$,
where $T$ is the disjoint union of all finite trees, and $P$ is the disjoint
union of all finite paths.

######  Remark 2.5.

We note that for any $G$ and any $\Gamma$,
$\operatorname{wid}^{G,1}(\Gamma)=|V\Gamma|$. The lower bound is a consequence
of the requirement that $\bigcup_{g\in VG}X_{g}=V\Gamma$, and the upper bound
is obtained from any decomposition where $X_{g}=V\Gamma$ for some $g\in VG$
and $X_{g^{\prime}}=\emptyset$ for all other $g^{\prime}\in VG$. For other
finite values of $p$ the invariants are more interesting. For instance, if
$\Gamma$ is the subgraph of $\mathbb{Z}^{3}$ with vertex set
$\\{1,\ldots,k\\}^{3}$ and edges $(a,b,c)(a^{\prime},b^{\prime},c^{\prime})$
whenever $|a-a^{\prime}|+|b-b^{\prime}|+|c-c^{\prime}|=1$, then

$X_{(x,y)}=\left\\{\begin{array}[]{ll}\left\\{(a,b,c)\ \left|\ |a-x|+|b-y|\leq
1\right.\right\\}&\textup{if}\ 1\leq x,y\leq k,\\\
\emptyset&\textup{otherwise}\end{array}\right.$

defines a $\mathbb{Z}^{2}$-decomposition of $\Gamma$ such that

$\left(\sum_{(x,y)\in\mathbb{Z}^{2}}|X_{(x,y)}|^{p}\right)^{1/p}\leq
5k^{1+2/p}=5|V\Gamma|^{\frac{1}{3}+\frac{2}{3p}}.$

###  2.2 Linear arrangements

######  Definition 2.6.

A linear arrangement of a finite graph $\Gamma$ is a bijective function
$f:V\Gamma\to\\{1,\ldots,|V\Gamma|\\}$.

We will associate three cost functions to a linear arrangement.

######  Definition 2.7.

We define the following functions $\\{1,\ldots,|V\Gamma|\\}\to\mathbb{R}$:

  * •

edge cut: $i\mapsto\operatorname{ec}_{f}(i)=|\left\\{vw\in E\Gamma\ \left|\
f(v)\leq i<f(w)\right.\right\\}|$,

  * •

vertex cut: $i\mapsto\operatorname{vc}_{f}(i)=|\left\\{v\in V\Gamma\ \left|\
\exists vw\in E\Gamma,\ f(v)\leq i<f(w)\right.\right\\}|$.

We also define a function $E\Gamma\to\mathbb{R}$ called length:
$vw\mapsto|f(v)-f(w)|$.

Note that edge cut and vertex cut are related in the following way.

######  Lemma 2.8.

Let $\Gamma$ be a finite graph with maximal degree $\Delta$. For every linear
arrangement $f$ and every $i$,

$\displaystyle\frac{1}{\Delta}\operatorname{vc}_{f}(i)\leq\operatorname{ec}_{f}(i)\leq\Delta\operatorname{vc}_{f}(i)$

As with graph decompositions, for each finite graph $\Gamma$ and each
$p\in[1,\infty]$ we define the $p$-edge cut $\operatorname{ec}^{p}(\Gamma)$
and $p$-length $\ell^{p}(\Gamma)$ to be the minimal $\ell^{p}$ norm of the
respective function over all linear arrangements of $\Gamma$.

######  Definition 2.9.

Let $X$ be a graph and let $p\in[1,\infty]$. We define

$\displaystyle\operatorname{ec}^{p}_{X}(r)=\max\left\\{\operatorname{ec}^{p}(\Gamma)\
\left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\\}$
$\displaystyle\operatorname{vc}^{p}_{X}(r)=\max\left\\{\operatorname{vc}^{p}(\Gamma)\
\left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\\}$
$\displaystyle\ell^{p}_{X}(r)=\max\left\\{\ell^{p}(\Gamma)\ \left|\ \Gamma\leq
X,\ |V\Gamma|\leq r\right.\right\\}.$

and call these the $p$-edge cut, $p$-vertex cut and $p$-length profiles of $X$
respectively.

######  Remark 2.10.

As noted in the introduction, the $\ell^{1}$ and $\ell^{\infty}$ versions of
the above invariants are typically known by other names. $\infty$-length is
known as bandwidth $\operatorname{bw}$, $1$-length is minimal linear
arrangement, $\infty$-edge cut is cutwidth $\operatorname{cw}$,
$\infty$-vertex cut is vertex separation, $1$-vertex cut is sumcut (which is
itself equal to profile) and $1$-edge cut is equal to $1$-bandwidth, cf.
[DPS02, §2].

###  2.3 Modified cutwidth

Another cost associated to a linear arrangement is modified cutwidth
($\operatorname{mcw}$). This invariant is not part of our collection
$\mathcal{I}$, but is naturally comparable to $\operatorname{ec}^{1}$ in the
following way.

######  Lemma 2.11.

For any finite graph $\Gamma$,

$\operatorname{ec}^{1}(\Gamma)=\operatorname{mcw}(\Gamma)+|E\Gamma|$

where $\operatorname{mcw}(\Gamma)$ is the modified cutwidth - the minimal
$1$-norm of the function $i\mapsto|\left\\{vw\in E\Gamma\ \left|\
f(v)<i<f(w)\right.\right\\}|$ over all linear arrangements $f$.

###### Proof.

For any linear arrangement $f$:

$\displaystyle\sum_{i}\left|\left\\{vw\in E\Gamma\ \left|\ f(v)\leq
i<f(w)\right.\right\\}\setminus\left\\{vw\in E\Gamma\ \left|\
f(v)<i<f(w)\right.\right\\}\right|$ $\displaystyle=$
$\displaystyle\sum_{i}|\left\\{vw\in E\Gamma\ \left|\
f(v)=i<f(w)\right.\right\\}|=|E\Gamma|.\qed$

##  3 Monotonicity theorems

The goal of this section is to prove Theorem 1.1.

###  3.1 Width of graph decompositions

We begin with a useful lemma.

######  Lemma 3.1.

Let $\left\\{X_{g}\ \left|\ g\in VG\right.\right\\}$ be a $G$-decomposition of
$\Gamma$. For every subset $A\subseteq V\Gamma$ which induces a connected
subgraph of $\Gamma$,

$\bigcup_{a\in A}\left\\{g\in VG\ \left|\ a\in X_{g}\right.\right\\}$

induces a connected subgraph of $G$.

###### Proof.

Set $G_{a}=\left\\{g\in VG\ \left|\ a\in X_{g}\right.\right\\}$. As
$\left\\{X_{g}\ \left|\ g\in VG\right.\right\\}$ be a $G$-decomposition of
$\Gamma$, each $G_{a}$ induces a connected subgraph of $G$. Now for each
distinct pair $b,b^{\prime}\in\bigcup_{a\in A}\left\\{g\in VG\ \left|\ a\in
X_{g}\right.\right\\}$ there exist $a,a^{\prime}\in A$ such that $b\in G_{a}$
and $b^{\prime}\in G_{a^{\prime}}$. Let
$a=a_{0},a_{1},\ldots,a_{k}=a^{\prime}$ be the vertex set of a path in $A$.
Since $a_{i-1}a_{i}\in E\Gamma$ for all $i$, there is some $g\in VG$ such that
$\\{a_{i-1},a_{i}\\}\subseteq X_{g}$. Thus, $g\in G_{a_{i-1}}\cap G_{a_{i}}$.
Therefore,

$\bigcup_{i=0}^{k}G_{a_{i}}\subseteq\bigcup_{a\in A}\left\\{g\in VG\ \left|\
a\in X_{g}\right.\right\\}$

induces a connected subgraph of $G$ which contains $b,b^{\prime}$. As this
holds for each pair $b,b^{\prime}$, the lemma follows. ∎

Now we prove that, for any graph $G$ and any $p\in[1,\infty]$, the
$(G,p)$-width profile behaves monotonically under regular maps.

######  Proposition 3.2.

Let $X$ and $Y$ be bounded degree graphs. If there is a $\kappa$-regular map
$\phi:VX\to VY$ then for every graph $G$ and every $p\in[1,\infty]$,

$\operatorname{wid}^{G,p}_{X}(r)\lesssim\operatorname{wid}^{G,p}_{Y}(r).$

###### Proof.

Let $\Gamma\leq X$ with $|V\Gamma|\leq r$. For each $xy\in E\Gamma$, let
$P_{xy}$ be a path of length at most $2\kappa$ in $Y$ connecting $\phi(x)$ to
$\phi(y)$. Define

$\Gamma^{\prime}=\phi(V\Gamma)\cup\bigcup_{xy\in E\Gamma}P_{xy}\leq Y$

Given $x\in V\Gamma$, we denote by $\overline{\phi}(x)$ the set of all
vertices in

$\left\\{\phi(x)\right\\}\cup\bigcup_{\left\\{vw\in E\Gamma\ \left|\
x\in\\{v,w\\}\right.\right\\}}P_{xy}.$

We have
$|V\Gamma^{\prime}|\leq|V\Gamma|+2\kappa|E(\Gamma)|\leq|V\Gamma|(1+\kappa\Delta(X))$

Fix a $G$-decomposition $\left\\{X^{\prime}_{g}\ \left|\ g\in
G\right.\right\\}$ of $\Gamma^{\prime}$ with $p$-width at most
$\operatorname{wid}^{G,p}_{Y}((1+\kappa\Delta(X))r)$.

Now define $X_{g}=\left\\{x\in V\Gamma\ \left|\ \overline{\phi}(x)\cap
X^{\prime}_{g}\neq\emptyset\right.\right\\}$. We now prove that $\\{X_{g}\\}$
is a $G$-decomposition of $\Gamma$. For every $x\in V\Gamma$ $\phi(x)\in
V\Gamma^{\prime}$, so there is some $g\in G$ such that $\phi(x)\in
X^{\prime}_{g}$. Therefore, $x\in X^{\prime}_{g}$, so condition (i) holds. Now
let $xy\in V\Gamma$ and let $w$ be any vertex on the path $P_{xy}$. There is
some $g\in G$ such that $w\in X^{\prime}_{g}$ and
$w\in\overline{\phi}(x)\cap\overline{\phi}(y)$, so $x,y\in X_{g}$ for the same
$g$. Thus $(ii)$ holds. By construction, for each $x\in V\Gamma$,

$\left\\{g\in VG\ \left|\ x\in
X_{g}\right.\right\\}=\bigcup_{y\in\overline{\phi}(x)}\left\\{g\in VG\ \left|\
y\in X^{\prime}_{g}\right.\right\\}.$ (3.3)

As $\overline{\phi}(v)$ is connected, by Lemma 3.1, the full subgraph of $G$
with vertex set (3.3) is connected, so $\\{X_{g}\\}$ is a $G$-decomposition of
$\Gamma$.

Finally, for a fixed $y\in V\Gamma^{\prime}$, if $y\in\overline{\phi}(x)$ then
$\phi(x)$ is contained in the ball of radius $2\kappa$ centred at $y$. As
$|\phi^{-1}(z)|\leq\kappa$ for every $z\in VY$, we deduce that there are at
most $\kappa(1+\Delta(X))^{2\kappa}$ possibilities for $x\in V\Gamma$. Thus,
for each $g\in G$,

$|X_{g}|\leq\kappa(1+\Delta(X))^{2\kappa}|X^{\prime}_{g}|$

so, for all $p\in[1,\infty]$,

$\operatorname{wid}^{G,p}(\Gamma)\leq\kappa(1+\Delta(X))^{2\kappa}\operatorname{wid}^{G,p}(\Gamma^{\prime}).$

As this holds for all finite $\Gamma\leq X$, we have

$\operatorname{wid}^{G,p}_{X}(r)\leq K\operatorname{wid}^{G,p}_{Y}(Kr)$

where $K=\kappa(1+\Delta(X))^{2\kappa}$. ∎

###  3.2 Linear arrangement costs

######  Proposition 3.4.

Let $X,Y$ be bounded degree graphs where $Y$ has infinitely many edges. If
there is a regular map $VX\to VY$ then for every $p\in[1,\infty]$,

$\displaystyle\ell^{p}_{X}(r)\lesssim\ell^{p}_{Y}(r)$ (3.5)
$\displaystyle\operatorname{ec}^{p}_{X}(r)\lesssim\operatorname{ec}^{p}_{Y}(r).$
(3.6)

###### Proof.

Note that as $Y$ has infinitely many edges, then for every $r$ there is a
subgraph $\Gamma_{r}\leq Y$ with at most $r$ vertices and at least
$\lfloor\frac{r}{2}\rfloor$ edges. Thus,

$\displaystyle\min\\{\ell^{p}_{Y}(r),\operatorname{ec}^{p}_{Y}(r)\\}\geq\left\lfloor\frac{r}{2}\right\rfloor^{1/p}.$
(3.7)

Therefore, we may assume that $\ell^{p}_{Y}(r)\gtrsim r^{1/p}$ and
$\operatorname{ec}^{p}_{Y}(r)\gtrsim r^{1/p}$.

Since there is a regular map $\phi:VX\to VY$, there is some $\kappa\geq 1$
such that

  * •

$d_{Y}(\phi(x),\phi(x^{\prime}))\leq\kappa(1+d_{X}(x,x^{\prime}))$ for all
$x,x^{\prime}\in VX$, and

  * •

$|\phi^{-1}(y)|\leq\kappa$ for all $y\in VY$.

Let $\Gamma\leq X$ with $|V\Gamma|\leq r$. Define a subgraph
$\Gamma^{\prime}\leq Y$ which contains $\phi(V\Gamma)$ and such that whenever
$xy\in E\Gamma$, there is a path of length at most $2\kappa$ connecting
$\phi(x)$ to $\phi(y)$ in $\Gamma^{\prime}$. We may ensure that
$\frac{1}{\kappa}|V\Gamma|\leq|V\Gamma^{\prime}|\leq
2\kappa|E\Gamma|\leq\kappa\Delta(X)|V\Gamma|$.

Given a proper numbering
$g:V\Gamma^{\prime}\to\\{1,\ldots,|V\Gamma^{\prime}|\\}$, choose a proper
numbering $f:V\Gamma\to\\{1,\ldots,|V\Gamma|\\}$ with the property that
$f(v)\leq f(v^{\prime})$ implies $g(\phi(v))\leq g(\phi(v^{\prime}))$. In
particular, this means that the sequence $a_{i}=g(\phi(f^{-1}(i)))$ is
monotonically non-decreasing.

We claim that for every edge $vv^{\prime}\in E\Gamma$ such that
$|f(v)-f(v^{\prime})|>2\kappa^{2}$, there is some edge $ww^{\prime}\in
E\Gamma^{\prime}$ satisfying

  * •

$d_{Y}(\phi(v),w))\leq 2\kappa$, and

  * •

$|f(v)-f(v^{\prime})|\leq 2\kappa^{2}|g(w)-g(w^{\prime})|$.

Given the claim we complete the proof as follows. By the first condition above
there is a uniform bound (call it $C$) on the number of edges $vv^{\prime}$
which yield the same edge $ww^{\prime}$. Thus for $p\in[1,\infty)$,

$\displaystyle\ell^{p}(\Gamma)$
$\displaystyle=\min_{f}\left(\sum_{vv^{\prime}\in
E\Gamma}|f(v)-f(v^{\prime})|^{p}\right)^{1/p}$
$\displaystyle\leq\min_{g}\left(C\sum_{ww^{\prime}\in
E\Gamma^{\prime}}(2\kappa^{2}|g(w)-g(w^{\prime})|)^{p}\right)^{1/p}+\left(\sum_{vv^{\prime}\in
E\Gamma}(2\kappa^{2})^{p}\right)^{1/p}$ $\displaystyle\leq
2\kappa^{2}\left(C^{1/p}\ell^{p}(\Gamma^{\prime})+|E\Gamma|^{1/p}\right)$
$\displaystyle\lesssim\ell^{p}_{Y}(\max\\{|V\Gamma^{\prime}|,|E\Gamma|\\}).$

Note that the last step uses the assumption that $\ell^{p}_{Y}(r)\gtrsim
r^{1/p}$. For $p=\infty$,

$\displaystyle\ell^{\infty}(\Gamma)$
$\displaystyle=\min_{f}\max_{vv^{\prime}\in E\Gamma}|f(v)-f(v^{\prime})|$
$\displaystyle\leq\min_{g}\max_{ww^{\prime}\in
E\Gamma^{\prime}}2\kappa^{2}|g(w)-g(w^{\prime})|+2\kappa^{2}$
$\displaystyle\leq 2\kappa^{2}\left(\ell^{\infty}(\Gamma^{\prime})+1\right).$

It remains to prove the claim. Suppose $|f(v)-f(v^{\prime})|>2\kappa^{2}$.
Without loss of generality, assume $k=f(v)<f(v^{\prime})=k+l$. Since $f$ and
$g$ are injective, we have

$\left\lvert
g(\phi(\\{f^{-1}(k),\ldots,f^{-1}(k+\ell)\\}))\right\rvert\geq\ell/\kappa$

and $g(\phi(f^{-1}(k)))\leq\ldots\leq g(\phi(f^{-1}(k+\ell)))$, so
$g(\phi(f^{-1}(k+\ell)))-g(\phi(f^{-1}(k)))\geq\ell/\kappa$. In particular,
$\phi(v)\neq\phi(v^{\prime})$.

Since $vv^{\prime}\in E\Gamma$, $d_{Y}(\phi(v),\phi(v^{\prime}))\leq 2\kappa$.
Let $\phi(v)=w_{0},w_{1},\ldots,w_{m}=\phi(v^{\prime})$ be the vertices of a
path in $\Gamma^{\prime}$ with $m\leq 2\kappa$. Since
$g(w_{m})-g(w_{0})\geq\ell/\kappa$, there is some $i$ such that
$|g(w_{i+1})-g(w_{i})|\geq\ell/(2\kappa^{2})$. We choose $w=w_{i}$ and
$w^{\prime}=w_{i+1}$. By construction $ww^{\prime}\in E\Gamma^{\prime}$,
$d_{Y}(\phi(v),w)\leq 2\kappa$ and $|f(v)-f(v^{\prime})|\leq
2\kappa^{2}|g(w)-g(w^{\prime})|$ completing the claim.

For edge cut we use the same proper numbering $f$. Fix $1<k\leq|V\Gamma|$. For
convenience define

$\displaystyle F_{k}=\left\\{vv^{\prime}\in E\Gamma\ \left|\ f(v)\leq
k<f(v^{\prime})\right.\right\\}$ $\displaystyle G_{l}=\left\\{ww^{\prime}\in
E\Gamma^{\prime}\ \left|\ g(w)\leq l<g(w^{\prime})\right.\right\\}$

and write $f_{k}=|F_{k}|$, $g_{l}=|G_{l}|$. We claim that $f_{k}\leq
Cg_{a_{k}}+\kappa\Delta(X)$ for some constant $C$ which depends only on
$\kappa$ and $\Delta(Y)$. We recall that $a_{k}=g(\phi(f^{-1}(k)))$.

Given the claim, we see that for $p=\infty$,

$\displaystyle\operatorname{ec}^{\infty}(\Gamma)$
$\displaystyle=\min_{f}\max_{k}f_{k}$
$\displaystyle\leq\min_{g}\max_{l}Cg_{l}+\kappa\Delta(X)$ $\displaystyle\leq
C\operatorname{ec}^{\infty}(\Gamma^{\prime})+\kappa\Delta(X).$

When $p\in[1,\infty)$, using the fact that for any $l$ there are at most
$\kappa$ values of $k$ such that $a_{k}=l$, we have

$\displaystyle\operatorname{ec}^{p}(\Gamma)$
$\displaystyle=\min_{f}\left(\sum_{k}f_{k}^{p}\right)^{1/p}$
$\displaystyle\leq\min_{g}\left(\sum_{l}\kappa\left(Cg_{l}+\kappa\Delta(X)\right)^{p}\right)^{1/p}$
$\displaystyle\leq
C\kappa^{1/p}\min_{g}\left(\sum_{l}\left(g_{l}\right)^{p}\right)^{1/p}+C\kappa^{1+1/p}\Delta(X)|V\Gamma^{\prime}|^{1/p}$
$\displaystyle\leq
2C\kappa^{1/p}\max\left\\{\min_{g}\left(\sum_{l}\left(g_{l}\right)^{p}\right)^{1/p},\kappa\Delta(X)|V\Gamma^{\prime}|^{1/p}\right\\}$
$\displaystyle\lesssim\operatorname{ec}^{p}_{Y}(|V\Gamma^{\prime}|).$

Note that the final step uses the assumption made at the start of the proof
that $\operatorname{ec}^{p}_{Y}(r)\gtrsim r^{1/p}$.

Now we prove the claim. For each edge in the set $F_{k}$, we have
$g(\phi(v))\leq a_{k}\leq g(\phi(v^{\prime}))$. Since $\phi$ has preimages of
cardinality at most $\kappa$ there are at most $\kappa\Delta(X)$ edges in
$E\Gamma$ with an end vertex $w$ such that $g(\phi(w))=a_{k}$.

If $vv^{\prime}\in F_{k}$ is not one of these edges, then $g(\phi(v))\leq
a_{k}<g(\phi(v^{\prime}))$. There is a path in $\Gamma^{\prime}$ connecting
$\phi(v)$ to $\phi(v^{\prime})$ with length at most $2\kappa$, and there is
some edge $ww^{\prime}$ on this path such that $g(w)\leq a_{k}<g(w^{\prime})$.

As in the previous argument, since $d_{Y}(\phi(v),w))\leq 2\kappa$ there is a
uniform bound $C$ on the number of edges $vv^{\prime}$ which yield the same
edge $vv^{\prime}$ via this process. Thus,

$g_{a_{k}}\geq\frac{f_{k}-\kappa\Delta(X)}{C},$

as required. ∎

##  4 Calculations

###  4.1 Proof of Theorems 1.4 and 1.5

We briefly recall the definition of the separation profile.

######  Definition 4.1.

Let $\Gamma$ be a finite graph and let $\varepsilon\in(0,1)$. A subset
$C\subseteq V\Gamma$ is a $\varepsilon$-cutset if every connected component of
$\Gamma\setminus C$ contains at most $\varepsilon|V\Gamma|$ vertices. The
$\varepsilon$-cutsize of a finite graph $\Gamma$,
$(\operatorname{cut}^{\varepsilon}(\Gamma))$ is the minimal cardinality of a
$\varepsilon$-cutset.

The $\varepsilon$-separation profile of a graph $X$ is the function

$\operatorname{sep}_{X}^{\varepsilon}(r)=\max\left\\{\operatorname{cut}^{\varepsilon}(\Gamma)\
\left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\\}$

One important result from [BST12] is that for all
$\varepsilon,\varepsilon^{\prime}\in(0,1)$,

$\
\operatorname{sep}_{X}^{\varepsilon}(r)\simeq\operatorname{sep}_{X}^{\varepsilon^{\prime}}(r).$

The key observation here is the following. A similar argument appears in
[DV03].

######  Lemma 4.2.

Let $X$ be a bounded degree graph and let $\varepsilon\in(0,1)$. Then

$\operatorname{ec}^{\infty}_{X}(r)\leq\operatorname{ec}^{\infty}_{X}(\varepsilon
r)+\Delta(X)\operatorname{sep}^{\varepsilon}_{X}(r).$

###### Proof.

Let $\Gamma\leq X$ with $|\Gamma|\leq r$. Let $C$ be a $\varepsilon$-cutset of
$\Gamma$ satisfying $|\Gamma|\leq\operatorname{sep}^{\varepsilon}_{X}(r)$, and
let $A_{1},\ldots,A_{k}$ be the connected components of $\Gamma-C$. Choose
bijections $\sigma_{i}:A_{i}^{0}\to\\{1,\ldots,|A_{i}|\\}$ such that
$\max_{i}|\\{vw\in EA_{i}:\ \sigma_{i}(v)\leq
i<\sigma_{i}(w)\\}|=\operatorname{ec}^{\infty}(A_{i})$. Now we define a linear
arrangement $\sigma$ of $V\Gamma^{\prime}$. For each $v\in A_{i}$, define

$\sigma(v)=|A_{1}|+\ldots+|A_{i-1}|+\sigma_{i}(v)$

and map the vertices in $C$ to
$\\{\sum_{i=0}^{k}|A_{i}|+1,\ldots,|V\Gamma|\\}$ in any bijective way.

For all $|A_{1}|+\ldots+|A_{i-1}|\leq j<|A_{1}|+\ldots+|A_{i}|$, we have

$\displaystyle|\\{vw\in E\Gamma:\ \sigma(v)\leq j<\sigma(w)\\}|$
$\displaystyle\leq\operatorname{ec}^{\infty}(A_{i})+|\\{vw\in
E\Gamma:\\{v,w\\}\cap C\neq\emptyset\\}|$
$\displaystyle\leq\operatorname{ec}^{\infty}(A_{i})+\Delta(X)\operatorname{sep}^{\varepsilon}_{X}(r).$

Moreover, for $j>|A_{1}|+\ldots+|A_{k}|$,

$|\\{vw\in E\Gamma:\ \sigma(v)\leq
j<\sigma(w)\\}|\leq\Delta(X)\operatorname{sep}^{\varepsilon}_{X}(r).$

As this holds for all $\Gamma$, and $|A_{i}|\leq\varepsilon r$ for all $i$, we
see that

$\operatorname{cw}_{X}(r)\leq\operatorname{ec}^{\infty}_{X}(\varepsilon
r)+\Delta(X)\operatorname{sep}^{\varepsilon}_{X}(r).\qed$

Repeatedly applying the above lemma (with $\varepsilon=\frac{1}{2}$) we get a
strong control on $\operatorname{ec}^{\infty}$ in terms of separation.

######  Corollary 4.3.

Let $X$ be a bounded degree graph. Then

$\operatorname{ec}^{\infty}_{X}(r)\leq\Delta(X)\sum_{i=0}^{\lceil\log_{2}(r)\rceil}\operatorname{sep}(2^{-i}r)\leq\Delta(X)(1+\lceil\log_{2}(r)\rceil)\operatorname{sep}_{X}(r).$

###### Proof.

Repeatedly applying Lemma 4.2, we see that

$\operatorname{ec}^{\infty}_{X}(r)\leq\operatorname{ec}^{\infty}_{X}\left(\frac{r}{2^{\lceil\log_{2}(r)\rceil}}\right)+\Delta(X)\sum_{i=0}^{\lceil\log_{2}(r)\rceil}\operatorname{sep}(2^{-i}r).$

As $2^{\lceil\log_{2}(r)\rceil}\geq r$ and the cutwidth of a graph with at
most $1$ vertex is $0$, the result follows. ∎

When the separation profile is known to be sufficiently nice, the above bound
can be improved.

######  Corollary 4.4.

Let $X$ be a bounded degree graph such that $\operatorname{sep}_{X}(r)\lesssim
r^{a}\log(r)^{b}$ where $a\in[0,1]$ and $b\in\mathbb{R}$. Then

$\operatorname{ec}^{\infty}_{X}(r)\lesssim\left\\{\begin{array}[]{ccc}r^{a}\log(r)^{b}&\textup{if}&a>0,\\\
\log(r)^{b+1}&\textup{if}&a=0.\end{array}\right.$

###### Proof.

By Corollary 4.3

$\displaystyle\operatorname{ec}^{\infty}_{X}(r)$
$\displaystyle\leq\Delta(X)\sum_{i=0}^{\lceil\log_{2}(r)\rceil}\operatorname{sep}(2^{-i}r)$
$\displaystyle\leq\Delta(X)\sum_{i=0}^{\lceil\log_{2}(r)\rceil}C(C2^{-i}r)^{a}\log(C2^{-i}r)^{b}$
$\displaystyle\leq\Delta(X)C^{1+a}\log(Cr)^{b}\sum_{i=0}^{\lceil\log_{2}(r)\rceil}(2^{-i}r)^{a}.$

If $a>0$, then
$\sum_{i=0}^{\lceil\log_{2}(r)\rceil}(2^{-i}r)^{a}\leq\frac{r^{a}}{1-2^{-a}}$,
so

$\operatorname{ec}^{\infty}_{X}(r)\leq C^{\prime}r^{a}\log(Cr)^{b}.$

If $a=0$, then
$\sum_{i=0}^{\lceil\log_{2}(r)\rceil}(2^{-i}r)^{a}=1+\lceil\log_{2}(r)\rceil$,
so

$\operatorname{ec}^{\infty}_{X}(r)\leq\Delta(X)C\log(Cr)^{b}(1+\lceil\log_{2}(r)\rceil)\lesssim\log(r)^{b+1}.\qed$

###### Proof of Theorem 1.4.

By Corollary 4.4, if $\operatorname{sep}_{X}(r)\lesssim r^{a}\log(r)^{b}$,
then

$\operatorname{cw}_{X}(r)\simeq\operatorname{ec}^{\infty}_{X}(r)\lesssim
r^{a}\log(r)^{b}.$

If, in addition $\operatorname{sep}_{X}(r)\lesssim r^{a}\log(r)^{b}$, then by
Theorem 1.3

$r^{a}\log(r)^{b}\lesssim\operatorname{sep}_{X}(r)\lesssim\operatorname{cw}_{X}(r)\lesssim
r^{a}\log(r)^{b}.\qed$

Finally, we prove Theorem 1.5, which immediately follows from the following:

######  Proposition 4.5.

Let $\Gamma$ be a finite graph and let $p\in[1,\infty)$. We have

$\displaystyle\operatorname{vc}^{p}(\Gamma)$
$\displaystyle\geq\left\lfloor\frac{|V\Gamma|}{3}\right\rfloor^{\frac{1}{p}}\operatorname{cut}^{\frac{2}{3}}(\Gamma).$

###### Proof.

Choose a bijection $f:V\Gamma\to\\{1,\ldots,|V\Gamma|\\}$, and note that for
each $\frac{|V\Gamma|}{3}\leq i\leq\frac{2|V\Gamma|}{3}$,

$C_{i}:=\left\\{v\in V\Gamma\ \left|\ \exists vw\in E\Gamma,\ f(v)\leq
i<f(w)\right.\right\\}$

is a $\frac{2}{3}$ cutset of $\Gamma$, since no connected component of
$\Gamma\setminus C_{i}$ can contain a vertex in both
$f^{-1}(\\{1,\ldots,i\\})$ and $f^{-1}(\\{i+1,\ldots,|V\Gamma|\\})$. As there
are at least $\left\lfloor\frac{|V\Gamma|}{3}\right\rfloor$ such values of
$i$, we have

$\operatorname{vc}^{p}(\Gamma)\geq\left\lfloor\frac{|V\Gamma|}{3}\right\rfloor^{\frac{1}{p}}\operatorname{cut}^{\frac{2}{3}}(\Gamma).\qed$

###  4.2 Coarse wirings and graph width

We recall the definition of coarse wirings and the coarse wiring profile from
[BH21]. The definition given here is slightly different to allow situations
where the image graph does not have bounded degree. In the bounded degree
case, the two definitions are equivalent up to a multiplicative error
depending only on maximal degree.

######  Definition 4.6.

Let $\Gamma,\Gamma^{\prime}$ be graphs. A wiring of $\Gamma$ into
$\Gamma^{\prime}$ is a continuous map $f:\Gamma\to\Gamma^{\prime}$ which maps
vertices to vertices and each edge $xy$ to a walk $W_{xy}$ which starts at
$f(x)$ and ends at $f(y)$.

A wiring $f$ is a coarse $k$-wiring if the preimage of each vertex of
$V\Gamma^{\prime}$ contains at most $k$ vertices in $V\Gamma$, and each vertex
$v\in V\Gamma^{\prime}$ is contained in at most $k$ of the walks in
$\mathcal{W}=\left\\{W_{xy}\ \left|\ xy\in E\Gamma\right.\right\\}$.

We consider the image of a wiring $\operatorname{im}(f)$ to be the graph

$\phi(V\Gamma)\cup\bigcup_{xy\in E\Gamma}W_{xy}\leq\Gamma^{\prime}.$

The volume of a wiring $\operatorname{vol}(f)$ is the number of vertices in
its image.

Let $\Gamma$ be a finite graph and let $Y$ be a graph. We denote by
$\operatorname{wir}^{k}(\Gamma\to Y)$ the minimal volume of a coarse
$k$-wiring of $\Gamma$ into $Y$. If no such coarse $k$-wiring exists, we say
$\operatorname{wir}^{k}(\Gamma\to Y)=+\infty$.

######  Remark 4.7.

The definition of a coarse $k$-wiring in [BH21] requires that each edge $e\in
E\Gamma^{\prime}$ is contained in at most $k$ of the walks in
$\mathcal{W}=\left\\{W_{xy}\ \left|\ xy\in E\Gamma\right.\right\\}$. Any
$k$-coarse wiring in the sense of [BH21] is a $2k$-coarse wiring as defined
here. When $\Gamma^{\prime}$ has bounded degree, any $k$-coarse wiring as
defined here is a $k\Delta(\Gamma^{\prime})$-coarse wiring in the sense of
[BH21]. We write the definition in this way here as we will want to allow
$\Gamma^{\prime}$ to have unbounded degree.

We associate two cost functions to the difficulty of coarse wiring one graph
into another.

######  Definition 4.8.

Let $X$ and $Y$ be graphs. We define $\operatorname{par}_{X\to Y}(r)$ to be
the minimal $k$ such that every $\Gamma\leq X$ with $|V\Gamma|\leq r$ admits a
$k$-coarse wiring into $Y$.

For each $k$, we define $\operatorname{wir}^{k}_{X\to
Y}(r)=\max\left\\{\operatorname{wir}^{k}(\Gamma\to Y)\ \left|\ \Gamma\leq X,\
|V\Gamma|\leq r\right.\right\\}$.

Note that when $X$ has bounded degree, the upper bound
$\operatorname{par}_{X\to Y}(r)\leq\Delta(X)r$ is obtained by mapping all of
$\Gamma$ to a single vertex.

Given a graph $G$, coarse wiring costs can be compared with
$\operatorname{wid}^{G,\infty}$ in the following way:

######  Proposition 4.9.

For any bounded degree graph $X$ and any graph $G$,

$\operatorname{wid}^{G,\infty}_{X}(r)\leq 2\operatorname{par}_{X\to G}(r).$

###### Proof.

Let $\Gamma\leq X$ with $|V\Gamma|\leq r$ and let $f:\Gamma\to G$ be a
$k$-coarse wiring with $k\leq\operatorname{par}_{X\to G}(r)$.

For each $x\in V\Gamma$, set $\overline{f}(x)$ to be the set of all vertices
in $\bigcup_{xy\in E\Gamma}W_{x,y}$. We claim that $X_{g}=\left\\{x\in
V\Gamma\ \left|\ g\in\overline{f}(x)\right.\right\\}$ defines a
$G$-decomposition of $\Gamma$.

For each edge $xy\in E\Gamma$, $\\{x,y\\}\subset X_{g}$ for any $g\in
VW_{xy}\neq\emptyset$. Next, by construction, for each $x\in V\Gamma$,

$\left\\{g\in G\ \left|\ x\in X_{g}\right.\right\\}=\overline{f}(x)$

which induces a connected subgraph ($\bigcup_{xy\in E\Gamma}W_{x,y}$) of $G$.

Finally, for each $g$, there are at most $k$ edges $xy\in E\Gamma$ such that
$g\in W_{x,y}$ and therefore at most $2k$ vertices $x\in E\Gamma$, such that
$g\in\overline{f}(x)$. ∎

We define one more informative variation of $\operatorname{wid}^{G,p}$ which
is more closely related to the volume of coarse wirings.

######  Definition 4.10.

Fix $\ell$. Given a graph $X$ and a graph $G$, we define
$\operatorname{wid}^{G,p,\ell}(\Gamma)$ to be the minimal $p$-norm of a
$G$-decomposition $(X_{g})$ of $\Gamma$ with $\max_{g}|X_{g}|\leq\ell$.

Now, given a graph $X$ and a function $f:\mathbb{N}\to\mathbb{N}$, we define

$\operatorname{wid}^{G,p,f}_{X}(r)=\max\left\\{\operatorname{wid}^{G,p,f(r)}(\Gamma)\
\left|\ \Gamma\leq X,\ |V\Gamma|\leq r\right.\right\\}.$

Repeating the proof of Proposition 3.2 we get the following:

######  Proposition 4.11.

If there is a $\kappa$-regular map $VX\to VY$ then there is a constant
$C=C(\kappa,\Delta(X))$ such that for every graph $G$ and function $f$,

$\operatorname{wid}^{G,p,f}_{X}(r)\lesssim\operatorname{wid}^{G,p,Cf}_{Y}(r).$

We can also compare this variant of $1$-width with the coarse wiring profile
by repeating the argument of Proposition 4.9.

######  Proposition 4.12.

Let $X$ be a bounded degree graph and let $G$ be a graph. For every
$k\in\mathbb{N}$ there is some $\ell\in\mathbb{N}$ such that

$\operatorname{wid}^{G,1,\ell}_{X}(r)\lesssim\operatorname{wir}^{k}_{X\to
G}(r).$

We note that the $\simeq$-class of $\operatorname{wir}^{k}_{X\to G}(r)$ can
vary depending on the parameter $k$, as demonstrated in [Rai23].

##  5 Questions

Here we list a few questions which naturally arise from this work.

######  Question 5.1.

Is there a bounded degree graph $X$ such that
$\operatorname{sep}_{X}(r)\not\simeq\operatorname{tw}_{X}(r)$?

In addition to those situations where
$\operatorname{sep}_{X}(r)\simeq\operatorname{tw}_{X}(r)$ given by this paper,
Benjamini-Schramm-Timár prove that $\operatorname{sep}_{X}(r)\simeq 1$ if and
only if $\operatorname{tw}_{X}(r)\simeq 1$ [BST12]. We are also unaware of any
bounded degree graphs with any of the following properties:

######  Question 5.2.

For $I\in\\{\operatorname{ec},\ell\\}$, is there a bounded degree graph $X$
and $p\in[1,+\infty)$ such that $I^{p}_{X}(r)\not\simeq
r^{1/p}I^{\infty}_{X}(r)$?

More generally, the only examples we know of the following phenomenon are for
$I=\operatorname{wid}^{G}$, $p=1$ and $q=\infty$.

######  Question 5.3.

For $I\in\\{\operatorname{ec},\ell,\operatorname{wid}^{G}\\}$, are there
bounded degree graphs $X$ and $Y$, and $p,q\in[1,+\infty]$ such that
$I^{p}_{X}(r)\simeq I^{p}_{Y}(r)$ but $I^{q}_{X}(r)\not\simeq I^{q}_{Y}(r)$?

We give one natural example of a graph where the cutwidth profile is not
known.

######  Question 5.4.

Let $X$ be the graph of a tesselation of the hyperbolic plane (say by regular
right-angled octagons). Is $\operatorname{cw}_{X}(n)\simeq\log(n)$?

From the results of this paper we know that
$\log(n)\lesssim\operatorname{cw}_{X}(n)\lesssim\log(n)^{2}$ and by [KMP01,
Proposition 2.3] all balls in planar hyperbolic graphs have cutwidth which
grows at most logarithmically in the number of vertices contained in the ball.

It is natural to ask under which circumstances a converse to Proposition 4.12
holds.

######  Question 5.5.

For which graphs $X$ and $G$ is it true that for every $\ell\in\mathbb{N}$
there is some $k\in\mathbb{N}$ such that

$\operatorname{wir}^{k}_{X\to G}(r)\lesssim\operatorname{wid}^{G,1,f}_{X}(r)?$

## References

  * [ACP87] Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski.  Complexity of finding embeddings in a k-tree.  SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, 1987\.
  * [AST90] Noga Alon, Paul Seymour, and Robin Thomas.  A separator theorem for nonplanar graphs.  Journal of the American Mathematical Society, 3(4):801–808, 1990\.
  * [BH21] B. Barrett and D. Hume.  Thick embeddings of graphs into symmetric spaces via coarse geometry.  Preprint, arXiv:2112.05305, 2021.
  * [Bod88] Hans Bodlaender.  Some classes of graphs with bounded treewidth.  Bulletin of the European Association for Theoretical Computer Science (EATCS), 36, 01 1988.
  * [Bod06] Hans L. Bodlaender.  Treewidth: Characterizations, applications, and computations.  In Fedor V. Fomin, editor, Graph-Theoretic Concepts in Computer Science, pages 1–14, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [BST12] Itai Benjamini, Oded Schramm, and Ádam Timár.  On the separation profile of infinite graphs.  Groups Geom. Dyn., 6(4):639–658, 2012.
  * [Coz20] Corentin Le Coz.  Poincaré profiles of lamplighter diagonal products.  Preprint, arXiv:2007.04709, 2020.
  * [CS89] Fan R. K. Chung and Paul D. Seymour.  Graphs with small bandwidth and cutwidth.  Discrete Mathematics, 75(1):113–119, 1989.
  * [DPS02] Josep Díaz, Jordi Petit, and Maria Serna.  A survey of graph layout problems.  ACM Comput. Surv., 34(3):313–356, sep 2002.
  * [DV03] Hristo N. Djidjev and Imrich Vrto.  Crossing numbers and cutwidths.  J. Graph Algorithms Appl., 7:245–251, 2003.
  * [GJ79] Michael R. Garey and David S. Johnson.  Computers and intractability. A guide to the theory of NP-completeness.  A Series of Books in the mathematical Sciences. San Francisco: W. H. Freeman and Company. X, 338 p. (1979)., 1979.
  * [GLC23] Antoine Gournay and Corentin Le Coz.  Separation profile, isoperimetry, growth and compression.  Annales de l’Institut Fourier, 73(4):1627–1675, 2023.
  * [GS21] Valeriia Gladkova and Verna Shum.  Separation profiles of graphs of fractals.  Journal of Topology and Analysis, 13(04):1111–1123, 2021.
  * [HM20] David Hume and John M. Mackay.  Poorly connected groups.  Proc. Amer. Math. Soc., 148(11):4653–4664, 2020.
  * [HMT20] David Hume, John M. Mackay, and Romain Tessera.  Poincaré profiles of groups and spaces.  Rev. Mat. Iberoam., 36(6):1835–1886, 2020.
  * [HMT22] David Hume, John M. Mackay, and Romain Tessera.  Poincaré profiles of Lie groups and a coarse geometric dichotomy.  Geom. Funct. Anal., 32:1063–1133, 2022.
  * [HMT23] David Hume, John M. Mackay, and Romain Tessera.  Asymptotic dimension for covers with controlled growth.  Preprint arXiv:2303.01969, 2023.
  * [Hum17] David Hume.  A continuum of expanders.  Fund. Math., 238:143–152, 2017.
  * [KMP01] C. Kenyon, E. Mossel, and Y. Peres.  Glauber dynamics on trees and hyperbolic graphs.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 568–578, 2001.
  * [MPS83] Fillia Makedon, Christos H Papadimitriou, and Ivan Sudborough.  Topological bandwidth.  Proceedings on the Colloquium on Trees in Algebra and Programming, pages 317–331, 01 1983.
  * [MS89] Fillia Makedon and Ivan Hal Sudborough.  On minimizing width in linear layouts.  Discrete Applied Mathematics, 23(3):243–265, 1989.
  * [Rai23] R. Raistrick.  Dependence of the coarse wiring profile on the choice of parameter.  Preprint, arxiv:2311.08436, 2023.