# On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings,
and other applications

Arnold Filtser
Bar-Ilan University Email<EMAIL_ADDRESS>This research was
supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1042/22).

###### Abstract

Given a metric space $(X,d_{X})$, a $(\beta,s,\Delta)$-sparse cover is a
collection of clusters $\mathcal{C}\subseteq P(X)$ with diameter at most
$\Delta$, such that for every point $x\in X$, the ball
$B_{X}(x,\frac{\Delta}{\beta})$ is fully contained in some cluster
$C\in\mathcal{C}$, and $x$ belongs to at most $s$ clusters in $\mathcal{C}$.
Our main contribution is to show that the shortest path metric of every
$K_{r}$-minor free graphs admits $(O(r),O(r^{2}),\Delta)$-sparse cover, and
for every $\epsilon>0$, $(4+\epsilon,O(\frac{1}{\epsilon})^{r},\Delta)$-sparse
cover (for arbitrary $\Delta>0$). We then use this sparse cover to show that
every $K_{r}$-minor free graph embeds into
$\ell_{\infty}^{\tilde{O}(\frac{1}{\epsilon})^{r+1}\cdot\log n}$ with
distortion $3+\varepsilon$ (resp. into
$\ell_{\infty}^{\tilde{O}(r^{2})\cdot\log n}$ with distortion $O(r)$).
Further, we provide applications of these sparse covers into padded
decompositions, sparse partitions, universal TSP / Steiner tree, oblivious buy
at bulk, name independent routing, and path reporting distance oracles.

###### Contents

  1. 1 Introduction
    1. 1.1 Low dimensional metric embeddings into $\ell_{\infty}$
    2. 1.2 Padded Decompositions
    3. 1.3 Further Applications
    4. 1.4 Related Work
  2. 2 Preliminaries
  3. 3 Technical Overview
  4. 4 Sparse Covers for Minor Free Graphs
    1. 4.1 Buffered cop decomposition.
    2. 4.2 Additional properties of buffered cop decomposition
    3. 4.3 Sparse Covers Construction
  5. 5 Metric Embedding into $\ell_{\infty}$ from Sparse Partition Cover
    1. 5.1 Prefix Free Codes
    2. 5.2 Embedding into $\ell_{\infty}$ from sparse partition cover scheme
    3. 5.3 Removing the dependence on the aspect ratio
    4. 5.4 Improved distortion for minor free graphs
  6. 6 From sparse covers to padded decompositions
  7. 7 Further applications
    1. 7.1 Sparse Partitions
    2. 7.2 Universal TSP and Universal Steiner Tree
    3. 7.3 Oblivious Buy-at-Bulk
    4. 7.4 Name-Independent Routing
    5. 7.5 Path-Reporting Distance Oracle
  8. 8 Conclusion and Open Problems
  9. A Proof of Lemma 5

##  1 Introduction

Given a metric space $(X,d_{X})$ a $(\beta,s,\Delta)$-sparse cover is a
collection of clusters $\mathcal{C}\subseteq P(X)$ all with diameter at most
$\Delta$, such that every point belongs to at most $s$ clusters, and every
ball $B_{X}(x,\frac{\Delta}{\beta})$ is fully contained in some cluster
$C\in\mathcal{C}$. Sparse covers are very useful for algorithmic design, and
in particular for divide and concur. Since their introduction by Awerbuch and
Peleg [AP90b], sparse covers found numerous applications. A partial list of
which includes: compact routing schemes [PU89, Pel00, TZ01, AGM+08, AGM05,
AGMW10, BLT14], distant-dependent distributed directories [AP91, Pel93, Pel00,
BLT14], network synchronizers [AW04, AP90a, Lyn96, Pel00, BLT14], distributed
deadlock prevention [AKP94], construction of spanners and ultrametric covers
[HIS13, FN22, LS23, HMO23, FL22a, FGN23], metric embeddings [Rao99, KLMN05],
universal TSP and Stiner tree constructions [JLN+05, BDR+12, Fil20b, BCF+23],
and Oblivious buy-at-bulk [SBI11].

We will study sparse covers in weighted graphs, where we distinguish between
two different types of diameter. The _weak_ diameter of a cluster $A\subseteq
V$ in a weighted graph $G=(V,E,w)$ is the maximum pairwise distance
$\max_{u,v\in A}d_{G}(u,v)$ w.r.t. the original shortest path distance, while
the _strong_ diameter is the maximum pairwise distance $\max_{u,v\in
A}d_{G[A]}(u,v)$ in the induced subgraph. We continue with a formal
definition:

######  Definition 1 (Sparse Cover).

Given a weighted graph $G=(V,E,w)$, a collection of clusters
$\mathcal{C}=\\{C_{1},...,C_{t}\\}$ is called a weak/strong $(\beta,s,\Delta)$
sparse cover if the following conditions hold.

  1. 1.

Bounded diameter: The weak/strong diameter of every cluster
$C_{i}\in\mathcal{C}$ is bounded by $\Delta$.

  2. 2.

Padding: For each $v\in V$, there exists a cluster $C_{i}\in\mathcal{C}$ such
that $B_{G}(v,\frac{\Delta}{\beta})\subseteq C_{i}$.

  3. 3.

Sparsity: For each $v\in V$, there are at most $s$ clusters in $\mathcal{C}$
containing $v$.

If the clusters $\mathcal{C}$ can be partitioned into $s$ partitions
$\mathcal{P}_{1},\dots,\mathcal{P}_{s}$ s.t.
$\mathcal{C}=\cup_{i=1}^{s}\mathcal{P}_{i}$, than
$\\{\mathcal{P}_{1},\dots,\mathcal{P}_{s}\\}$ is called a weak/strong
$(\beta,s,\Delta)$ sparse partition cover. We say that a graph $G$ admits a
weak/strong $(\beta,s)$ sparse (partition) cover scheme, if for every
parameter $\Delta>0$ it admits a weak/strong $(\beta,s,\Delta)$ sparse
(partition) cover that can be constructed in expected polynomial time. Sparse
partition cover scheme is abbreviated SPCS.

The notion of sparse cover scheme is the more common in the literature.
However, SPCS provides additional structure that is crucial for different
applications. 111In this paper we require the partition property of SPCS for
metric embeddings into $\ell_{\infty}$, and for the oblivious buy-at-bulk.
This property is also crucial in the construction of ultrametric covers
[FL22a, Fil23, FGN23]. Obtaining strong diameter guarantee is also
considerably more challenging, however it is frequently required in “subgraph
based” applications. 222In this paper we use the strong diameter guarantee for
routing, buy-at-bulk, and path reporting distance oracle.

Sparse covers were introduced by Awerbuch and Peleg [AP90b] who showed that
for every $k\in\mathbb{N}$, every $n$ vertex graph admits a strong
$(4k-2,2k\cdot n^{\frac{1}{k}})$-SPCS. Klein, Plotkin, and Rao [KPR93]
constructed a celebrated weak padded decomposition 333Roughly, padded
decomposition with padding parameter $\rho$ is a random partition into
clusters of diameter at most $\Delta$ such that every ball of radius
$\frac{\Delta}{\rho}$ is fully contained in a single cluster with probability
at least $\frac{1}{2}$. See Definition 2. for $K_{r}$-minor free graphs with
padding parameter $O(r^{3})$ (later improved to $O(r^{2})$ [FT03]). It is
folklore that padded decomposition with padding parameter $\rho$ implies a
$(\rho,O(\log n))$-SPCS (by taking the union of $O(\log n)$ independent
partitions). Thus [KPR93, FT03] implied a weak $(O(r^{2}),O(\log n))$-SPCS for
$K_{r}$-minor free graphs. Krauthgamer et al. [KLMN05] observed that one can
use [KPR93, FT03] padded decomposition to construct a weak
$(O(r^{2}),2^{r})$-SPCS for $K_{r}$-minor free graphs (see [Fil20b] for an
explicit proof). This was the first sparse cover where all the parameters are
independent from the cardinality of the vertex set $n$. Busch et al. [BLT14]
used shortest path separators to obtain a strong $(8,f(r)\cdot\log n)$-SPCS.
444$f(r)$ is the enormous constant hiding in the Robertson Seymour [RS03]
structure theorem. Johnson [Joh87] estimated $f(r)\geq
2\Uparrow(2\Uparrow(2\Uparrow\frac{r}{2}))+3)$ where $2\Uparrow t$ is the
exponential tower function ($2\Uparrow 0=1$ and $2\Uparrow
t=2^{2\Uparrow(t-1)}$) . Abraham et al. [AGMW10] constructed a strong sparse
cover. Specifically, they made some adaptations to [KPR93] to obtain a strong
$(O(r^{2}),2^{O(r)}\cdot r!)$-sparse cover scheme (not a SPCS). The final
major piece in our story is a weak padded decomposition for $K_{r}$-minor free
graphs with padding parameter $O(r)$ by Abraham et al. [AGG+19]. Which was
later improved to strong padded decomposition with the same parameter by
Filtser [Fil19a]. In particular, this implies a strong $(O(r),O(\log
n))$-sparse cover scheme. Interestingly, it was unknown how to turn this
padded decomposition into a sparse cover with sparsity independent of $n$.
Indeed, Filtser explicitly asked whether it is possible to construct
$(O(r),g(r))$-sparse cover scheme [Fil19a] . The main result of this paper is
an affirmative answer to this question. A decade after the publication of
[AGG+14] we finally managed to turn this padded decomposition into a sparse
cover.

######  Theorem 1 (Cover for Minor Free Graphs).

Every $K_{r}$-minor free graph admits the following:

  * •

Strong $\left(O(r),O(r^{2})\right)$-SPCS.

  * •

For $\varepsilon\in(0,\frac{1}{2})$, strong
$\left(4+\varepsilon,O(\frac{1}{\varepsilon})^{r}\right)$-SPCS.

The first bullet in Theorem 1 improves over the previous SPCS state of the art
[FT03, KLMN05, Fil20b] in a threefold manner: (1) the padding is improved
quadratically from $O(r^{2})$ to $O(r)$, (2) the sparsity is improved
exponentially from $2^{r}$ to $O(r^{2})$, (3) the diameter guarantee is now
strong. Alternately, the second bullet improves the stretch from $O(r^{2})$ to
$O(1)$ while keeping a similar sparsity. See Table 1 for a comparison of ours
and previous work.

Family | Padding | Sparsity |  SPCS? | Diameter | Ref
---|---|---|---|---|---
General | $4k-2$ | $2k\cdot n^{\frac{1}{k}}$ | yes | strong | [AP90b]
Planar | $32$ | $18$ | yes (implicit) | strong | [BLT14]
$K_{r}$-minor free | $O(r^{3})$ | $O(\log n)$ | yes | weak | [KPR93]
$O(r^{2})$ | $O(\log n)$ | yes | weak | [FT03]
$O(r)$ | $O(\log n)$ | yes | weak | [AGG+19]
$O(r)$ | $O(\log n)$ | yes | strong | [Fil19a]
$8$ |  $f(r)\cdot\log n$ ${}^{(\ref{foot:RS})}$ | yes (implicit) | strong | [BLT14]
$O(r^{2})$ | $2^{r}$ | yes | weak | [FT03, KLMN05]
$O(r^{2})$ | $2^{O(r)}\cdot r!$ | no | strong | [AGMW10]
$O(r)$ | $O(r^{2})$ | yes | strong | Theorem 1
$4+\varepsilon$ | $O(\frac{1}{\varepsilon})^{r}$ | yes | strong
Table 1: Summery of new and previous work on sparse covers.

###  1.1 Low dimensional metric embeddings into $\ell_{\infty}$

Metric embedding is a map between two metric spaces that approximately
preserves pairwise distances. Given a (finite) metric space $(X,d_{X})$, a map
$\phi:V\to\mathbb{R}^{k}$, and a norm $\|\cdot\|$, the _contraction_ and
_expansion_ of the map $\phi$ are the smallest $\xi,\rho\geq 1$, respectively,
such that for every pair $x,y\in X$,

$\frac{1}{\xi}\cdot d(x,y)\leq\|\phi(x)-\phi(y)\|\leq\rho\cdot
d(x,y)\leavevmode\nobreak\ \leavevmode\nobreak\ .$

The _distortion_ of the map is then $\xi\cdot\rho$. The expansion $\rho$ is
also called the Lipschitz constant of the embedding $\phi$. Metric embeddings
into norm spaces were thoroughly studied [Bou85, LLR95, Mat96, ABN11], and
have a plethora of applications.

There is a special interest for metric embeddings into $\ell_{\infty}$. From
an algorithmic viewpoint, there is a significant advantage in the additional
structure the norm space is providing. One example being nearest neighbor
search (NNS) [Ind98, BG19], where $\ell_{\infty}$ enjoys succinct data
structures. NNS for many other spaces works by first embedding the space into
$\ell_{\infty}$, and then using the $\ell_{\infty}$ NNS data structure to
answer queries in the original metric space (see e.g. [FI99, Ind02]). From a
geometric view point, $\ell_{\infty}$ is a special norm as it is a universal
host metric space. That is, every finite metric spaces embeds isometrically
(that is with distortion $1$) into $\ell_{\infty}$ (the so called Fréchet
embedding). However, there are $n$-point metric spaces of which every
isometric embedding into $\ell_{\infty}$ requires $\Omega(n)$ dimensions
[LLR95]. It is desirable to have low dimensional metric embeddings, as these
are much more useful for algorithmic design. Matoušek [Mat96] showed that for
every integer $t\geq 2$, every metric space embeds with distortion $2t-1$ into
$\ell_{\infty}$ of dimension $O(n^{1/t}\cdot t\cdot\log n)$ (which is almost
tight assuming the Erdős girth conjecture [Erd64]). For distortion $O(\log
n)$, Abraham et al. [ABN11] later improved the dimension to $O(\log n)$.

For more restrictive metric spaces better results are known. Linial et al.
[LLR95] showed that every $n$-point tree metric embeds isometrically into
$\ell_{\infty}^{O(\log n)}$, while Neiman [Nei16] showed that every metric
space with doubling dimension $d$ embeds into
$\ell_{\infty}^{\varepsilon^{-O(d)}\cdot\log n}$ with distortion
$1+\varepsilon$. Krauthgamer et al. [KLMN05] showed that every $n$-point
$K_{r}$-minor free graph $G$ embeds into
$\ell_{\infty}^{\tilde{O}(3^{r}\cdot\log n)}$ with distortion $O(r^{2})$.
Their embedding follows from a SPCS based on [KPR93, FT03]. However, their
construction uses additional properties of that cover, and we cannot simply
plug in our SPCS to get an improved embedding. We show that under very general
conditions, 555In fact the reduction hold in general with no condition, while
the dimension slightly increases. See Lemma 8. one can use SPCS in a black box
manner to obtain a metric embedding into $\ell_{\infty}$ (see Theorem 6). As a
corollary, we improve both the distortion and dimension compared to [KLMN05].
We than slightly tailor the embedding for minor free graphs to push the
distortion down all the way to $3+\varepsilon$. See Table 2 for a comparison
of new and old results.

######  Corollary 1.

Every $n$ vertex $K_{r}$-minor free graph embeds into
$\ell_{\infty}^{O(r^{2}\cdot\log r\cdot\log n)}$ with distortion $O(r)$.

######  Theorem 2.

For every $\varepsilon\in(0,\frac{1}{2})$, every $n$ vertex $K_{r}$-minor free
graph $G$ can be embedded into
$\ell_{\infty}^{O(\frac{1}{\varepsilon})^{r+1}\cdot\log\frac{1}{\varepsilon}\cdot\log\frac{n}{\varepsilon}}$
with distortion $3+\varepsilon$.

Family | Distortion | Dimension | Ref
---|---|---|---
General Metric | $1$ | $n-1$ | Fréchet
$2k-1$ | $O(k\cdot n^{\nicefrac{{1}}{{k}}}\cdot\log n)$ | [Mat96]
$O(\log n)$ | $O(\log n)$ | [ABN11]
Tree | $1$ | $\Theta(\log n)$ | [LLR95]
$K_{r}$-Minor Free | $O(r^{2})$ | $\tilde{O}(3^{r})\cdot\log n$ | [KLMN05]
$O(r)$ | $\tilde{O}(r^{2})\cdot\log n$ | Corollary 1
$3+\varepsilon$ | $\tilde{O}(\frac{1}{\varepsilon})^{r+1}\cdot\log n$ | Theorem 2
Table 2: Summery of new and previous work on metric embeddings into
$\ell_{\infty}$.

###  1.2 Padded Decompositions

Padded decomposition is a random partition of the vertices of a graph such
that nearby vertices are likely to be clustered together. We begin with a
formal definition:

######  Definition 2 (Padded Decomposition).

A distribution $\mathcal{D}$ over partitions of a graph $G=\left(V,E,w\right)$
is strong (resp. weak) $(\beta,\delta,\Delta)$-padded decomposition if every
$\mathcal{P}\in\mathrm{supp}(\mathcal{D})$ is strongly (resp. weakly)
$\Delta$-bounded and for any $0\leq\gamma\leq\delta$, and $z\in V$,
$\Pr[B_{G}(z,\gamma\Delta)\subseteq P(z)]\geq e^{-\beta\gamma}$. We say that
$G$ admits $(\beta,\delta)$-padded decomposition scheme if for every
$\Delta>0$, it admits a $(\beta,\delta,\Delta)$-padded decomposition.

One can think of padded decompositions as bring “dual” to sparse partitions.
Indeed, given a $(\beta,\delta,\Delta)$-padded decomposition, for
$\gamma<\delta$, by taking the union of $e^{-\beta\gamma}\cdot O(\log n)$
independent samples from the padded decomposition we will obtain a
$(\gamma,e^{-\beta\gamma}\cdot O(\log n))$-SPCS. However, no similar statement
in the other direction was ever made. Here we show that in general, given a
sparse cover one can construct a padded decomposition (alas only with a weak
diameter guarantee).

######  Theorem 3 (From sparse covers to padded decompositions).

Consider a weighted graph $G=(V,E,w)$ that admits a $(\beta,s,\Delta)$-sparse
cover. Then $G$ admits weak $(O(\beta\cdot\log
s),\frac{1}{4\beta},\Delta)$-padded decomposition.

By plugging in our sparse cover from Theorem 1 (with constant $\varepsilon$)
we recover the state of the art result [AGG+19].

######  Corollary 2.

Every $K_{r}$-minor free graph admits a weak
$\left(O(r),\Omega(1)\right)$-padded decomposition scheme.

The proof in [AGG+19] is non-intuitive, and uses complicated and sophisticated
probabilistic analysis based on a potential function. From the other hand, the
proof of Theorem 3 is short and elementary. Thus we obtain a simplified proof
of this core-stone result. The only known lower bound on the padding parameter
is $\Omega(\log r)$ which holds due to the fact that expanders are
$K_{n}$-minor free and have padding parameter $\Omega(\log n)$ [Bar96].
Abraham et al. [AGG+19] conjectured that $K_{r}$-minor free graphs admit
padded decomposition with padding parameter $O(\log r)$. Theorem 3 now
provides a natural avenue for solving this conjecture: construct better
covers!

###  1.3 Further Applications

#### Sparse partition and universal TSP / Steiner tree

Given a weighted graph $G=(V,E,w)$, a $(\alpha,\tau,\Delta)$-sparse partition
is a partition $\mathcal{C}$ of $V$ into clusters with weak diameter at most
$\Delta$, such that every ball of radius $\frac{\Delta}{\alpha}$ intersects at
most $\tau$ clusters from $\mathcal{C}$. $G$ admits a $(\alpha,\tau)$-sparse
partition scheme if it admits $(\alpha,\tau,\Delta)$-sparse partition for
every $\Delta>0$. Using our Theorem 1, we construct
$\left(O(r),O(r^{2})\right)$-sparse partition scheme for $K_{r}$ minor free
graphs, improving over the previous state of the art of
$\left(O(r^{2}),2^{r}\right)$-sparse partition scheme [JLN+05, Fil20b]. See
Corollary 3 in Section 7.1 for further details.

In the universal TSP problem, we are given a metric space $(X,d_{X})$ and the
goal is to choose a single permutation $\pi$ (a universal TSP) of $X$, such
that given a subset $S\subseteq X$, we visit the points in $S$ w.r.t. the
order in $\pi$. This is the induced TSP tour by $\pi$. The permutation $\pi$
has stretch $\rho$, if the length of the induced tour for every subset $S$ is
at most $\rho$ times larger than the optimal tour for $S$. There is a general
reduction from sparse partition scheme to universal TSP. Using this reduction
and our sparse partitions (Corollary 3), given a shortest path metric of an
$n$ point $K_{r}$ minor free graph, we construct universal TSP with stretch
$O(r^{4})\cdot\log n$ (Corollary 4), exponentially improving the dependence on
$r$ compared with previous results ($O(1)^{r}\cdot\log n$). The same phenomena
occurs also for the universal Steiner tree problem. See Section 7.2 for
further details.

#### Oblivious buy-at-bulk

Given a weighted graph $G=(V,E,w)$ and a _canonical fusion function_
$f:\mathbb{N}\rightarrow\mathbb{R}_{\geq 0}$ (see Section 7.3 for definition),
in the oblivious buy-at-bulk problem, the goal is to pick a route $P_{i}$ for
every possible demand pair $\delta_{i}=(s_{i},t_{i})\in{V\choose 2}$. Then,
given a specific set of demands $A=\\{\delta_{1},\dots,\delta_{k}\\}$, the
cost of our oblivious solution $\mathcal{P}=\\{P_{1},\dots,P_{k}\\}$ is
$\operatorname{cost}(\mathcal{P})=\sum_{e\in E}f(\varphi_{e})\cdot w(e)$,
where $\varphi_{e}$ is the number of paths in $\mathcal{P}$ using $e$. The
solution is said to have approximation ratio $\rho$ if for every subset of
demands, the induced cost of the oblivious solution is at most $\rho$ times
the optimal solution. Due to the concavity of the canonical fusion function
$f$, it is advantageous for the chosen paths to intersect as much as possible.
Srinivasagopalan et al. [SBI11], implicitly showed that if a graph $G$ admits
a strong $(\beta,s)$-sparse cover scheme, where each cover is $k$-colorable
(see Definition 6), than one can efficiently compute a solution for the
oblivious buy-at-bulk problem with approximation ratio $O(s\cdot\beta^{2}\cdot
k\cdot\log n)$. We observe that our sparse cover scheme from Theorem 1 is
$O(r^{2})$-colorable, and conclude that $K_{r}$ minor free graphs admit a
solution with approximation ratio $O(r^{6}\cdot\log n)$ (see Corollary 5),
answering an open problem from [SBI11]. Note that nothing better for minor
free graphs compared with general graphs was previously known. This is a
previous covers were either not strong [KPR93, FT03], or not colorable
[AGMW10, AGG+19, Fil19a].

#### Name Independent Routing

Here we are given an unweighted graph $G=(V,E)$ where the names (and ports) of
all nodes are fixed. The goal is to design a compact routing scheme that will
allow sending packages in the network, where routing decisions are made using
small local routing tables, and the resulting routing paths are approximate
shortest paths. This regime is considered more challenging and practical from
the regime where nodes names and ports could be chosen by the routing scheme
designer. Given a hereditary graph family that has $\alpha$-orientation (see
Section 7.4), where each graph possess strong $(\tau,\beta)$-sparse cover
scheme, Abraham et al. [AGMW10] constructed name independent compact routing
scheme with stretch $O(\beta)$, $O(\log n+\log\tau)$-bit headers and tables of
$O(\frac{\log^{3}n}{\log\log n}+\alpha\cdot\log n)\cdot\tau\cdot\log D$ bits.
We use our strong sparse covers (Theorem 1) to construct name independent
compact routing scheme significantly improving over previous work. See
Corollary 6, and Table 3 for a comparison.

#### Path reporting distance oracle

A path reporting distance oracle (PRDO) for a weighted graph $G=(V,E,w)$ is a
succinct data structure that given a query $\\{s,t\\}$, efficiently returns an
approximate $s$-$t$ shortest path $P$. We say that a PRDO has stretch $k$ and
query time $t$, if for every query $(s,t)$, the oracle returns a path $P$ of
weight at most $k\cdot d_{G}(s,t)$ in $O(|P|)+t$ time. PRDO were first studied
for general graphs. Later, Elkin et al. [ENW16] constructed a PRDO for
$K_{r}$-minor free graphs based on strong sparse covers. We plug in our strong
sparse cover from Theorem 1 to obtain improvements in both space and stretch,
see Corollary 7 (and Section 7.5).

###  1.4 Related Work

We provided background on sparse covers in the introduction. We refer to the
cited papers for additional background on sparse partitions, UTSP, UST,
routing and distance oracles. Here we provide additional background on metric
embeddings in order to put our results (Corollary 1, Theorem 2) in a wider
context. We begin with metric embeddings into $\ell_{p}$ spaces. Every $n$
point metric space embeds into $\ell^{O(\log n)}_{2}$ with distortion $O(\log
n)$ [Bou85], which is also tight [LLR95]. Planar graphs, and more generally
fixed minor free graphs, embed into $\ell^{O(\log n)}_{2}$ with distortion
$O(\sqrt{\log n})$ [Rao99, AFGN22], which is also tight [NR02]. The big open
question here is regarding the embedding of such graphs into $\ell_{1}$. The
upper bounds are the same as for $\ell_{2}$, while the only lower bound is $2$
[LR10]. A long standing conjecture by Gupta et al. [GNRS04] states that every
graph family excluding a fixed minor, and in particular planar graphs, can be
embedded into $\ell_{1}$ with constant distortion. Some partial progress for
planar graph was made in the cases where we care only about vertices laying on
a small number of faces [KLR19, Fil20a], or only about vertex pairs laying on
the same face [OS81, Kum22].

Refined notion of distortion in metric embeddings were studied, such as
scaling distortion [ABN11, BFN19b], and terminal/prioritized distortion
[EFN17, EFN18]. In particular, there been study of prioritized low dimensional
embeddings into $\ell_{\infty}$ [FGK23, EN22]. Online metric embeddings into
normed spaces were also studied [IMSZ10, NR20, BFT24].

A different venue of research is metric embeddings into trees, or more
generally low treewidth graphs. Every $n$-point metric space stochastically
embeds into trees with expected distortion $O(\log n)$ [Bar96, FRT04]. This
result is tight even when the metric is the shortest path metric of a planar
graph [AKPW95]. Every planar graph with diameter $\Delta$ can be
(deterministically) embedded into a graph with treewidth
$\tilde{O}(\varepsilon^{-3})$ with additive distortion
$\varepsilon\cdot\Delta$ [FKS19, FL22b, CCL+23]. Every $K_{r}$-minor free
graphs stochastically embeds into graphs with treewidth $f(r)\cdot
O(\frac{\log\log n}{\varepsilon})^{2}$ with expected additive distortion
$\varepsilon\cdot\Delta$ [CFKL20, FL22b]. Clan embeddings and Ramsey-type
embeddings of $K_{r}$-minor free graphs were also studied [FL22a]. Finally,
recently it was shown that every $K_{r}$-minor free graphs stochastically
embeds into graphs with treewidth
$f(r)\cdot\tilde{O}(\frac{1}{\varepsilon})\cdot\mathrm{poly}(\log(n\cdot\Phi))$
with multiplicative expected distortion $1+\varepsilon$ [CLPP23] (here $\Phi$
is the aspect ratio).

##  2 Preliminaries

$\tilde{O}$ notation hides poly-logarithmic factors, that is
$\tilde{O}(g)=O(g)\cdot\mathrm{polylog}(g)$. All logarithms are at base $2$
(unless specified otherwise), $\ln$ stand for the natural logarithm. Given a
set $A$, ${A\choose 2}=\left\\{\\{x,y\\}\mid x,y\in A,x\neq y\right\\}$
denotes all the subsets of size $2$. For a number $k\in\mathbb{N}$,
$[k]=\\{1,2,\dots,k\\}$.

We consider connected undirected graphs $G=(V,E,w)$ with edge weights
$w:E\to\mathbb{R}_{\geq 0}$. We say that vertices $v,u$ are neighbors if
$\\{v,u\\}\in E$. Let $d_{G}$ denote the shortest path metric in $G$.
$B_{G}(v,r)=\\{u\in V\mid d_{G}(v,u)\leq r\\}$ is the closed ball of radius
$r$ around $v$. For a vertex $v\in V$ and a subset $A\subseteq V$, let
$d_{G}(x,A):=\min_{a\in A}d_{G}(x,a)$, where $d_{G}(x,\emptyset)=\infty$. For
a subset of vertices $A\subseteq V$, $G[A]$ denotes the induced graph on $A$,
and $G\setminus A:=G[V\setminus A]$. The _diameter_ of a graph $G$ is
$\mathrm{diam}(G)=\max_{v,u\in V}d_{G}(v,u)$, i.e. the maximal distance
between a pair of vertices. Given a subset $A\subseteq V$, the _weak_
-diameter of $A$ is $\mathrm{diam}_{G}(A)=\max_{v,u\in A}d_{G}(v,u)$, i.e. the
maximal distance between a pair of vertices in $A$, w.r.t. to $d_{G}$. The
_strong_ -diameter of $A$ is $\mathrm{diam}(G[A])$, the diameter of the graph
induced by $A$.

The _aspect ratio_ of a metric space $(X,d_{X})$ is usually defined as the
ratio between the maximum and minimum distances. However, here we mainly work
with the shortest path distance in graphs, where we allow $0$-weights.
Formally, here the shortest path metric is actually a pseudometric.
Accordingly, we will define aspect ratio of a graph $G=(V,E,w)$ as the ratio
between the maximum distance to the minimum non zero distance:
$\Phi(G)=\frac{\max_{u,v\in V}d_{G}(u,v)}{\min_{u,v\in V\leavevmode\nobreak\
\rm{s.t.\leavevmode\nobreak\ }d_{\footnotesize G}(u,v)>0}d_{G}(u,v)}$.

A graph $H$ is a _minor_ of a graph $G$ if we can obtain $H$ from $G$ by edge
deletions/contractions, and isolated vertex deletions. A graph family
$\mathcal{G}$ is _$H$ -minor-free_ if no graph $G\in\mathcal{G}$ has $H$ as a
minor. Some examples of minor free graphs are planar graphs ($K_{5}$ and
$K_{3,3}$ minor-free), outer-planar graphs ($K_{4}$ and $K_{3,2}$ minor-free),
series-parallel graphs ($K_{4}$ minor-free) and trees ($K_{3}$ minor-free).

The $\ell_{\infty}$-norm of a vector $x=(x_{1},\dots,x_{k})\in\mathbb{R}^{k}$
is $\|x\|_{\infty}:=\max_{i\in[k]}|x_{i}|$. An embedding from a metric space
$(X,d_{X})$ into $\ell_{\infty}$ is a function $f:X\rightarrow\mathbb{R}^{k}$.
The embedding $f$ has distortion $c\cdot t$ if for every $x,y\in X$,
$\frac{1}{c}\cdot d_{X}(x,y)\leq\|f(x)-f(y)\|_{\infty}\leq t\cdot d_{X}(x,y)$.
$t$ is the _expansion_ (also known as a _Lipschitz_ constant) of $f$, while
$c$ is that _contraction_ of $f$. An embedding with distortion $1$ (where
$c=t=1$) is called _isometric_. Embedding $f:X\rightarrow\ell_{\infty}^{k}$
can be viewed as a collection of embeddings $\\{f_{i}\\}_{i=1}^{k}$ into the
line $\mathbb{R}$, where $f_{i}(x)$ equals to the $i$’th coordinate of $f(x)$.
We will also denote $(f(x))_{i}=f_{i}(x)$. Using this notation, $f$ has
expansion $t$ if for every $x,y\in X$ and $i\in[k]$, $|f_{i}(x)-f_{i}(y)|\leq
t\cdot d_{X}(x,y)$. Similarly, $f$ has contraction $c$ if for every $x,y\in X$
there is some $i\in[k]$ such that $|f_{i}(x)-f_{i}(y)|\geq\frac{1}{c}\cdot
d_{X}(x,y)$. In this case, we will say that the pair $x,y$ is _satisfied_ by
the coordinate $i$.

##  3 Technical Overview

#### Cop Decomposition.

Abraham et al. [AGG+19] constructed a padded decomposition for $K_{r}$-minor
free graphs based on the cops-and-robbers game [And86]. Fix the scale
parameter $\Delta>0$. The process works as follows: pick arbitrary $x_{1}$,
and let the ball $B_{G}(x_{1},r_{1})$ be the first cluster $\eta_{1}$, where
$r_{1}\in[0,\Delta]$ is sampled using truncated exponential distribution. To
construct the second cluster, pick an arbitrary connected component $C_{2}$ of
$G\setminus\eta_{1}$, and arbitrary $x_{2}\in C_{2}$. Let $T_{2}$ be a
shortest path from $x_{2}$ to some vertex $y$ with a neighbor in $\eta_{1}$.
Then the second cluster $\eta_{2}=B_{G[C_{2}]}(T_{2},r_{2})$ is a ball around
$T_{2}$ in the graph induced by the connected component, where the radius
$r_{2}\in[0,\Delta]$ is sampled using truncated exponential distribution. In
general, suppose that we already constructed clusters
$\eta_{1},\dots,\eta_{k-1}$. Let $C_{k}$ be an arbitrary connected component
of $G\setminus\cup_{i<k}\eta_{i}$, and $x_{k}\in C_{k}$ arbitrary vertex. Let
$\mathcal{K}_{C_{k}}\subseteq\\{\eta_{1},\dots,\eta_{k-1}\\}$ be all the
previously created clusters $\eta_{i}$, such that there is an edge from
$\eta_{i}$ to $C_{k}$. Let $T_{k}$ be a shortest path tree in $C_{k}$, with
$x_{k}$ as a root, and such that for every $\eta_{i}\in\mathcal{K}_{C_{k}}$,
there is an edge from a vertex in $T_{k}$ to $\eta_{i}$. In particular,
$T_{k}$ will have at most $|\mathcal{K}_{C_{k}}|$ leaves. The $k$’th cluster
$\eta_{k}=B_{G[C_{k}]}(T_{k},r_{k})$ is a ball around $T_{k}$ in the induced
graph $G[C_{k}]$, where $r_{k}\in[0,\Delta]$ is sampled using truncated
exponential distribution. See Figure 1 for illustration.

One can run the cop decomposition on general graphs without getting any
interesting structure. What makes it particularly interesting for
$K_{r}$-minor free graphs is the fact that the size of the set
$\mathcal{K}_{C_{k}}$ of neighboring previously created clusters is always
bounded by $r-2$. Indeed, one can argue that if $|\mathcal{K}_{C_{k}}|\geq
r-1$, than one can contract all the internal edges inside each cluster in
$\mathcal{K}_{C_{k}}$, and the connected component $C_{k}$, and obtain $K_{r}$
as a minor. Thus $T_{k}$ is a shortest path tree (w.r.t. $G[C_{k}]$) with at
most $r-2$ leaves, and the cluster $C_{k}$ is a ball of radius at most
$\Delta$ around this tree. We will call each such cluster a _supernode_ , and
the shortest path tree $T_{k}$ it’s _skeleton_. In addition, we construct a
tree $\mathcal{T}$ over the supernodes. Here each supernode $\eta_{k}$ will be
the child in $\mathcal{T}$ of the last created supernode
$\eta_{i}\in\mathcal{K}_{C_{k}}$. Note that the only outgoing edges from
$\eta_{k}$ are either to its descendants or ancestors in $\mathcal{T}$.
Furthermore, $\eta_{k}$ have at most $r-2$ “neighbor” ancestors. We will call
the connected component $C_{k}$ where we constructed the supernode $\eta_{k}$
(with skeleton $T_{k}$) the _domain_ of $\eta_{k}$, denoted
$\mathrm{dom}(\eta_{k})$. Note that the vertices in $\mathrm{dom}(\eta_{k})$
will either belong to $\eta_{k}$, or to the descendants of $\eta_{k}$ w.r.t.
$\mathcal{T}$. See Figure 1 for illustration.

Due to the truncated exponential distribution, Abraham et al. [AGG+19] showed
that a small ball $B_{G}(x,\gamma\Delta)$ is likely to be fully contained in a
single supernode. 666Specifically, using a sophisticated argument, based on a
potential function, Abraham et al. [AGG+19] showed that with probability at
least $e^{-O(r)\cdot\gamma}$, the ball $B_{G}(x,\gamma\Delta)$ is fully
contained in a single supernode. Unfortunately, the supernodes
$\\{\eta_{i}\\}_{i\geq 1}$ do not have a bounded diameter. Nevertheless,
following [Fil19a], using the skeleton $T_{k}$, one can partition each
supernode $\eta_{k}$ into clusters of diameter $O(\Delta)$, while cutting each
small ball only with a small probability. Combining these two processes
together, one obtains a strong $(O(r),\Omega(\frac{1}{r}),O(\Delta))$-padded
decomposition. However, it is unclear if it is possible to use the cop
decomposition to create a sparse cover. Indeed, the “dependence tree”
$\mathcal{T}$ does not have a bounded depth, and the entire process looks very
chaotic. Indeed, every small change in the sampling of the radii leads to a
completely different outcome. In contrast, the [KPR93] (as well as [AGMW10])
clustering process had only a depth of $r$, and thus [KLMN05] enumerated all
the possible choices in the process leading to a sparse cover of exponential
sparsity.

#### Buffered Cop Decomposition.

In a recent work, Chang et al. [CCL+24] obtained a new “separation”-property
in the cop-decomposition. Instead of growing a ball with a random radius
around the skeleton $T_{k}$, Chang et al. constructed the supernode $T_{K}$
deterministically. The new separation property is the following, consider a
supernode $\eta$, and a vertex $v\in\mathrm{dom}(\eta)$ such that $v$ belongs
to a supernode $\eta^{\prime}$, which is descendant of $\eta$, but there is no
edge from $\eta$ to $\eta^{\prime}$. Then
$d_{G[\mathrm{dom}(\eta)]}(\eta,v)>\frac{\Delta}{r}=\gamma$. In other words,
for every descendant $\eta^{\prime}$ of $\eta$, either they are neighbors, or
every path in $\mathrm{dom}(\eta)$ from $\eta$ to $\eta^{\prime}$ is of length
at least $\gamma$. 777Roughly speaking, [CCL+24] begin with the supernode
$\eta_{k}$ being equal to the skeleton $T_{k}$. Then, as the algorithm
progresses, each time the buffer property is violated we add the violating
vertices to a previously created supernode. One can argue that the depth of
this process is bounded by $r$ (once for each neighboring ancestor supernode),
and thus the cluster vertices are all within $\Delta$ distance from the
skeleton. Chang et al. called the new partition _Buffered Cop Decomposition_ ,
because there is now a buffer between non-neighboring clusters. They used the
new buffered cop decomposition to construct a _shortcut-partition_ (which is a
generalization of scattering partition [Fil20b]). Roughly, a shortcut-
partition is a partition of the vertices into clusters of diameter at most
$\varepsilon\cdot D$, such that for every pair of vertices $u,v$ at distance
at most $D$, there is an approximate shortest path going through at most
$O_{r}(\frac{1}{\varepsilon})$ clusters. Chang et al. used their shortcut-
partitions to construct tree covers [BFN19a, CCL+23], distance oracles
[Tho04b, Kle02, AG06], to solve the Steiner point removal problem [Fil19b,
Fil20b, KKN15, Che18, FKT19], and to construct additive embedding of apex
minor free graphs into low treewidth graphs [FKS19, CFKL20, FL21, FL22b,
CCL+23].

#### Sparse Covers.

The starting point of this paper is the buffered cop decomposition of
[CCL+24]. We begin by observing some additional properties. Let
$\overrightarrow{G}_{\mathcal{C}}$ be a digraph where the supernodes are the
vertices, and there is a directed edge from a supernode $\eta$ to its ancestor
$\eta^{\prime}$ (w.r.t. $\mathcal{T}$) iff there is an edge between vertices
in $\eta$ and $\eta^{\prime}$. $\overrightarrow{G}_{\mathcal{C}}$ is a DAG
(directed acyclic graph) with maximum out-degree $r-2$, and it has additional
crucial property: if $v$ has outgoing edges towards $u,z$ than there has to be
an edge between $u$ and $z$ (in one way or another). We call a graph with this
property a _transitive DAG_ (see Definition 4). In transitive DAG’s,
neighboring vertices tend to share many of their neighbors. Denote by
$B_{\overrightarrow{G}_{\mathcal{C}}}(\eta,q)$ the set of supernodes towards
which there is a directed path from $\eta$ of length at most $q$. We use the
transitive DAG property to show that the size of
$B_{\overrightarrow{G}_{\mathcal{C}}}(\eta,q)$ is bounded by ${r+q\choose r}$
(Lemma 1). Note that crucially, for $q\geq r$, ${r+q\choose r}\approx
O(q)^{r}$ the growth rate is sub-exponential in $q$. Next, we generalize the
buffer property to argue that for every ancestor supernode $\eta^{\prime}$ of
$\eta$ such that $\eta^{\prime}\notin
B_{\overrightarrow{G}_{\mathcal{C}}}(\eta,2q+1)$ it holds that the distance
from every vertex $v\in\eta$ to $\eta^{\prime}$ in
$\mathrm{dom}(\eta^{\prime})$ is at least $(q+1)\cdot\frac{\Delta}{r}$ (Lemma
2). Combining these two properties together, it follows that for every vertex
$v$ there are at most ${r+q\choose r}$ ancestor supernodes at distance
$q\cdot\frac{\Delta}{r}$.

Similar to the process of padded decomposition [AGG+19, Fil19a], our sparse
cover is constructed in two steps. First we cover the vertices using
_enlarged_ supernodes, and then we separately cover each enlarged supernode.
Fix $q\geq 0$, and for every supernode $\eta$, let
$\hat{\eta}=B_{G[\mathrm{dom}(\eta)]}(\eta,q\cdot\frac{\Delta}{r})$ be all the
vertices at distance at most $q\cdot\frac{\Delta}{r}$ from $\eta$ in
$\mathrm{dom}(\eta)$. In particular, a vertex $v\in\eta$ can join only to the
enlarged supernodes which are ancestors of $\eta$ at distance at most
$q\cdot\frac{\Delta}{r}$. Consider the ball
$B=B_{G}(v,\frac{q}{2}\cdot\frac{\Delta}{r})$, and let $\eta$ be the first
supernode containing some vertex from $B$. By the minimality of $\eta$, and
the triangle inequality, it will follow that the ball $B\subseteq\hat{\eta}$
is contained in the enlarged supernode. From the other hand, due to the
properties discussed above, each vertex $v$ will belong to at most
${r+q\choose r}$ enlarged supernodes. Thus we get both the sparsity and the
padding properties we wanted. The only missing property at this point is the
bounded diameter. Next we cover each enlarged supernode $\hat{\eta}$ using the
skeleton $T_{\eta}$. $T_{\eta}$ consist of at most $r$ shortest path. We go
over these shortest paths, and choose a $\Delta$-net $N$. Specifically, a set
such that every two net points are at distance at least $\Delta$, and every
point has a net point at distance at most $\Delta$. Fix
$R=2\Delta+q\cdot\frac{\Delta}{r}$. Due to the properties of shortest paths,
every point has at most $O(r+q)$ net points at distance $2R$. Now taking all
the balls of radius $R$ around net points provides us the desired sparse cover
for the enlarged supernode. Taking the union of all the covers for all the
enlarged supernodes we obtain the sparse cover for the graph. Fixing $q=1$ we
obtain padding $O(r)$ and sparsity $O(r^{2})$, while by taking
$q=\Theta(\frac{r}{\varepsilon})$ we obtain padding $4+\varepsilon$ and
sparsity $O(\frac{1}{\varepsilon})^{r}$.

#### Metric embedding into $\ell_{\infty}$.

Our metric embedding into $\ell_{\infty}$ is based on our SPCS. The first to
construct a sparse cover based metric embedding was Rao [Rao99], who used the
[KPR93] padded decomposition to embed $K_{r}$ minor free graphs into
$\ell_{2}$ with distortion $O(r^{3}\cdot\sqrt{\log n})$. Given a partition
$\mathcal{P}$, for a vertex $v$ belonging to cluster $v\in
C_{v}\in\mathcal{P}$, let $\partial_{\mathcal{P}}(v)=d_{X}(v,V\setminus
C_{v})$ be the distance between $v$ to the boundary of the cluster $C_{v}$.
Note that if $v$ is padded $B_{G}(v,\frac{\Delta}{\beta})\subseteq C_{v}$,
then $\partial_{\mathcal{P}}(v)>\frac{\Delta}{\beta}$. For each cluster
$C\in\mathcal{P}$, sample $\alpha_{C}\in\\{\pm 1\\}$ u.a.r. . For every vertex
$v$, send $v$ to $\alpha_{C_{v}}\cdot\partial_{\mathcal{P}}(v)$. By the
triangle inequality, it follows that the expansion is at most $2$. But for
which vertex pairs can we guarantee small contraction?

Consider a pair $u,v$ at distance $d_{G}(v,u)\in(\Delta,2\Delta]$, and suppose
that $\mathcal{P}$ has diameter at most $\Delta$, and $v$ is padded in
$\mathcal{P}$. Then $u$ and $v$ must belong to different clusters
$C_{u},C_{v}$. If it so happened that $\alpha_{C_{u}}\neq\alpha_{C_{v}}$, then
$\left|\alpha_{C_{v}}\cdot\partial_{\mathcal{P}}(v)-\alpha_{C_{u}}\cdot\partial_{\mathcal{P}}(u)\right|=\partial_{\mathcal{P}}(v)+\partial_{\mathcal{P}}(u)\geq\frac{\Delta}{\beta}\geq\frac{d_{G}(u,v)}{2\beta}$,
and we obtain a bound on the contraction! Rao took $O(\log n)$ independent
samples of the coefficients $\\{\alpha_{C}\\}_{C\in\mathcal{P}}$, and gets the
contraction guarantee in a constant fraction of the samples. Next, Rao also
took $O(\log n)$ independent partitions to get that $v$ is padded in a
constant fraction of them. Finally, Rao sampled partitions for all possible
distance scales, concatenated the resulting embeddings of them all, and
obtained the desired $O(r^{3}\cdot\sqrt{\log n})$ distortion. Assuming all the
distances are in $[1,\mathrm{poly}(n)]$, there are $O(\log n)$ different
distances scales, and the resulting dimension is $O(\log^{3}n)$: one $\log$
for the number of scales, one $\log$ to sample many partitions for each scale,
and one $\log$ to sample the coefficients
$\\{\alpha_{C}\\}_{C\in\mathcal{P}}$. Nevertheless, in $\ell_{2}$, using
dimension reduction [JL84], one can reduce the dimension to $O(\log n)$
without significantly increasing the distortion.

The focus of our paper is embeddings into $\ell_{\infty}$. One can repeat
Rao’s embedding exactly as is, and get embedding into
$\ell_{\infty}^{O(\log^{3}n)}$ with distortion $O(r^{3})$ (or $O(r)$ using the
improved padding parameter from [AGG+19]). Unfortunately, there is no general
dimension reduction in $\ell_{\infty}$ (ala [JL84]). Nevertheless, the
dimension still can be dramatically improved. First, observe that when
embedding into $\ell_{\infty}$, we don’t need to succeed on a constant
fraction of the partitions (or the $\alpha$ coefficients), it is enough to be
successful only once! Thus, instead taking $O(\log n)$ independent samples
from a padded decomposition, one can use a SPCS. Indeed, Krauthgamer et al.
[KLMN05] constructed an $(O(r^{2}),3^{r})$-SPCS for $K_{r}$ minor free graphs.
Using this SPCS immediately leads to an embedding into
$\ell_{\infty}^{\tilde{O}(3^{r})\cdot\log^{2}n}$ with distortion $O(r^{2})$.
To remove additional $\log n$ factor, [KLMN05] used an additional property of
the [KPR93] based SPCS that does not holds in general: it is possible to
create $3^{r}$ partitions such that for every pair $u,v$, there will be a
single partition where both $u$ and $v$ will be padded simultaneously.
[KLMN05] heavily relied on this property, while our SPCS (and actually all the
others as well) lacking it. Hence we cannot apply [KLMN05] as is.

Our solution follow similar lines to [KLMN05], but avoids using the additional
special structure of [KPR93]. Consider a graph $G$ with a $(\beta,\tau)$-SPCS.
First, for every scale $\Delta_{i}=\rho^{i}$, for
$\rho=O(\frac{\beta}{\varepsilon})$, create $\tau$ partitions
$\mathcal{P}_{i}^{1},\mathcal{P}_{i}^{2},\dots,\mathcal{P}_{i}^{\tau}$, all
with diameter $\Delta_{i}$, and such that every vertex is $\beta$-padded in
one of them (that is $\forall v,\leavevmode\nobreak\
B_{G}(v,\frac{\Delta}{\beta})$ is contained in some cluster). Next, create,
laminar partitions that closely resemble the original partitions.
Specifically, we create
$\\{\tilde{\mathcal{P}}_{i}^{1}\\}_{i\in\mathbb{Z}},\\{\tilde{\mathcal{P}}_{i}^{2}\\}_{i\in\mathbb{Z}},\dots,\\{\tilde{\mathcal{P}}_{i}^{\tau}\\}_{i\in\mathbb{Z}}$,
where for every $i,j$, $\mathcal{P}_{i}^{j}$ refines $\mathcal{P}_{i+1}^{j}$,
$\mathcal{P}_{i}^{j}$ has radius at most $(1+\varepsilon)\cdot\Delta_{i}$, and
for every $v\in V$, and $i\in\mathbb{Z}$,
$B_{G}(v,\frac{\Delta}{(1+\varepsilon)\cdot\beta})$ is fully contained in a
cluster of one of
$\tilde{\mathcal{P}}_{i}^{1},\dots,\tilde{\mathcal{P}}_{i}^{\tau}$. In other
words, for every $v\in V$, and $i\in\mathbb{Z}$,
$\max_{j\in[\tau]}\partial_{\mathcal{P}_{i}^{j}}(v)>\frac{\Delta_{i}}{(1+\varepsilon)\cdot\beta}$.
Similar laminar partitions were also created in [KLMN05].

Next, our goal is to embed w.r.t. each laminar partition
$\\{\tilde{\mathcal{P}}_{i}^{j}\\}_{i\in\mathbb{Z}}$ independently, such that
for every pair $u,v$ which is separated in partition
$\tilde{\mathcal{P}}_{i}^{j}$ it will hold that
$\|f(u)-f(v)\|_{\infty}\geq\partial_{\tilde{\mathcal{P}}_{i}^{j}}(v)+\partial_{\tilde{\mathcal{P}}_{i}^{j}}(u)$.
888For comparison, [KLMN05] used the simultaneous padding property of [KPR93]
and only guaranteed
$\|f(u)-f(v)\|_{\infty}\geq\min\left\\{\partial_{\tilde{\mathcal{P}}_{i}^{j}}(v),\partial_{\tilde{\mathcal{P}}_{i}^{j}}(u)\right\\}$.
In fact, the proof in [KLMN05] in insufficient even for that. Nevertheless,
the authors of [KLMN05] communicated to us a corrected proof of their claim.
Note that given such embedding for all the laminar partitions, we can
concatenate them all to obtain the desired distortion. Indeed, constant
expansion follows by triangle inequality, while for every $u,v$,
$\|f(u)-f(v)\|_{\infty}\geq\max_{i,j}\left(\partial_{\tilde{\mathcal{P}}_{i}^{j}}(v)+\partial_{\tilde{\mathcal{P}}_{i}^{j}}(u)\right)=\Omega(\frac{d_{G}(u,v)}{\beta})$.
To create the embedding w.r.t. to the laminar partition
$\\{\tilde{\mathcal{P}}_{i}^{j}\\}_{i\in\mathbb{Z}}$, let $i_{0}\in\mathbb{Z}$
be a the maximum index such that $\tilde{\mathcal{P}}_{i_{0}}^{j}$ is
partition into singletons, and let $k\in\mathbb{N}$ be the maximum such that
$\tilde{\mathcal{P}}_{i_{0}+k}^{j}$ is not the trivial partition into a single
cluster $\\{V\\}$. Clearly it is enough to embed only w.r.t. the laminar
partition $\\{\tilde{\mathcal{P}}_{i}^{j}\\}_{i=i_{0}}^{i_{0}+k}$. Let
$\tilde{\mathcal{P}}_{i_{0}+k}^{j}=\\{A_{1},\dots,A_{m}\\}$ be the clusters in
the top partition in our hierarchy. We create a prefix free code
$\alpha:\tilde{\mathcal{P}}_{i_{0}+k}^{j}\rightarrow\\{\pm 1\\}^{*}$.
Specifically, each cluster $A_{q}$ is assigned a string of $\pm 1$ of length
at most $2\cdot\left\lceil\log\frac{|V|}{|A_{q}|}\right\rceil$. The strings of
different clusters might be of different length. However, for every
$A_{q},A_{q^{\prime}}$ there is an index $s$ such that
$\alpha_{s}(A_{q}),\alpha_{s}(A_{q^{\prime}})$ exist and differ. Then the
embedding of each vertex $v\in A_{q}$ defined by concatenating the coordinates
$\left(\alpha_{1}(A_{q})\cdot\partial_{\tilde{\mathcal{P}}_{i_{0}+k}^{j}}(v),\alpha_{2}(A_{q})\cdot\partial_{\tilde{\mathcal{P}}_{i_{0}+k}^{j}}(v),\dots\right)$
with an embedding created inductively for $A_{q}$ w.r.t. the induced partition
by $\\{\tilde{\mathcal{P}}_{i}^{j}\\}_{i=i_{0}}^{i_{0}+k-1}$. To bound the
contraction, consider a pair $u,v$ and suppose that they are first separated
in level $k^{\prime}\in[i_{0},i_{0}+k]$. Then the embeddings of $u$ and $v$
are “aligned” in scales $[k^{\prime}+1,i_{0}+k]$, while in scale $k^{\prime}$
they belong to respective clusters
$A_{v},A_{u}\in\tilde{\mathcal{P}}_{k^{\prime}}^{j}$. The respective codes
$\alpha(A_{v}),\alpha(A_{u})$ will differ in some coordinate $s$ and thus
$\|f(u)-f(v)\|_{\infty}\geq\left|\alpha_{s}(A_{u})\cdot\partial_{\tilde{\mathcal{P}}_{k^{\prime}}^{j}}(u)-\alpha_{s}(A_{v})\cdot\partial_{\tilde{\mathcal{P}}_{k^{\prime}}^{j}}(v)\right|=\partial_{\tilde{\mathcal{P}}_{k^{\prime}}^{j}}(u)+\partial_{\tilde{\mathcal{P}}_{k^{\prime}}^{j}}(v)$.
To conclude a bound on the contraction it remains to observe that for every
partition $\tilde{\mathcal{P}}_{l}^{j}$ that refines
$\tilde{\mathcal{P}}_{k^{\prime}}^{j}$ it holds that
$\partial_{\tilde{\mathcal{P}}_{k^{\prime}}^{j}}(v)+\partial_{\tilde{\mathcal{P}}_{k^{\prime}}^{j}}(u)\geq\partial_{\tilde{\mathcal{P}}_{l}^{j}}(v)+\partial_{\tilde{\mathcal{P}}_{l}^{j}}(u)$.

The overall number of coordinates used for the embedding of the laminar
partition $\\{\tilde{\mathcal{P}}_{i}^{j}\\}_{i=i_{0}}^{i_{0}+k}$ is
$2\cdot\lceil\log n\rceil+2(k+1)$, where $k$ have to be bounded by a logarithm
of the aspect ratio $O(\log\Phi)$. If we started from a $(\beta,\tau)$-SPCS,
there are $\tau$ laminar partitions and thus the overall dimension is
$O(\tau\cdot\log(n\cdot\Phi))$. We remove the dependence on the aspect ratio
using fairly standard techniques. Specifically, by observing that for far
enough scales, we can use the same coordinate. For this to hold, when treating
scale $\rho^{i}$, we need to “contract” all vertex pairs at distance at most
$\frac{\rho^{i}}{n^{2}}$ (as otherwise a pair can accumulate error in
unbounded number of scales). Hence we can remove the dependence on the aspect
ratio only if the contracted graph still admits a SPCS.

##  4 Sparse Covers for Minor Free Graphs

This section is devoted to proving a meta-theorem (Theorem 5) that given a
buffered cop decomposition, constructs a sparse cover in a black box manner.
Afterwards, our main Theorem 1 will follow as a corollary of this meta
theorem, and the buffered cop decomposition of $K_{r}$ minor free graphs from
[CCL+24]. We begin in Section 4.1 with recalling the definition of buffered
cop decomposition from [CCL+24]. Then, in Section 4.2 we prove some properties
of buffered cop decomposition (mainly bounding the possible number of
supernodes at a certain distance, see Lemmas 1 and 2). Finally, in Section
4.3, we construct a sparse cover from a buffered cop decomposition.

###  4.1 Buffered cop decomposition.

Let $G=(V,E,w)$ be a weighted graph. A _supernode $\eta\subseteq V$_ with
_skeleton $T_{\eta}$_ and _radius $\Delta$_ is an induced subgraph $G[\eta]$
of $G$ containing a tree $T_{\eta}$ where every vertex in $\eta$ is within
distance $\Delta$ of $T_{\eta}$ w.r.t. induced shortest path metric, that is
$\eta=B_{G[\eta]}(T_{\eta},\Delta)$. A _buffered cop decomposition_ for $G$ is
a partition of $G$ into vertex-disjoint supernodes, together with a tree
_$\mathcal{T}$_ called the _partition tree_ , whose nodes are the supernodes
of $G$. For any supernode $\eta$, the _domain $\mathrm{dom}(\eta)$_ denotes
the subgraph induced by the union of all vertices in supernodes in the subtree
of $\mathcal{T}$ rooted at $\eta$. See Figure 1 for an illustration of
supernodes, their domain, and a buffered cop decomposition.

######  Definition 3.

A _$(\Delta,\gamma,w)$ -buffered cop decomposition_ for $G$ is a buffered cop
decomposition $\mathcal{T}$ that satisfies the following properties:

  * •

[Supernode radius.] Every supernode $\eta$ has radius at most $\Delta$.

  * •

[Shortest-path skeleton.] For every supernode $\eta$, let $\mathcal{A}_{\eta}$
be the set of ancestor supernodes $\eta^{\prime}$ of $\eta$ such that there is
an edge from $\mathrm{dom}(\eta)$ to $\eta^{\prime}$. Then
$|\mathcal{A}_{\eta}|\leq w$. The skeleton $T_{\eta}$ is an SSSP tree in
$\mathrm{dom}(\eta)$, with at most $w$ leaves (the root is not counted). In
particular, for every $\eta^{\prime}\in\mathcal{A}_{\eta}$, there is an edge
from $T_{\eta}$ to $\eta^{\prime}$. 999In the original definition of buffered
cop decomposition in [CCL+24] there were no explicit requirement for edges
between $T_{\eta}$ to $\mathcal{A}_{\eta}$. However it is holds in their
construction.

  * •

[Supernode buffer.] Let $\eta$ be a supernode, and let $\eta^{\prime}$ be
another supernode that is an ancestor of $\eta$ in the partition tree
$\mathcal{T}$. Then either $\eta$ and $\eta^{\prime}$ are adjacent in $G$, or
for every vertex $v$ in $\mathrm{dom}(\eta)$, we have
$d_{\mathrm{dom}(\eta^{\prime})}(v,\eta^{\prime})>\gamma$.

Figure 1: Illustration of an $(\Delta,\gamma,w)$-buffered cop decomposition of
the unweighted grid graph (left) together with the associated tree
$\mathcal{T}$. There are $9$ different supernodes $\eta_{1},\dots,\eta_{9}$,
all colored with different colors. Each supernode $\eta$ contains a shortest
path tree $T_{\eta}$ (the bold lines) with at most $3$ leaves, where all the
vertices $x\in\eta$ in the super node are at distance at most $\Delta=6$ from
$T_{\eta}$. The domain of each supernode consist of all the supernodes in its
subtree. For example
$\mathrm{dom}(\eta_{5})=G\left[\eta_{5}\cup\eta_{7}\cup\eta_{8}\cup\eta_{9}\right]$,
and $\mathrm{dom}(\eta_{3})=G\left[V\setminus(\eta_{1}\cup\eta_{2})\right]$.
As $\eta_{3}$ and $\eta_{9}$ are not adjacent, the distance from $\eta_{3}$ to
any vertex in $\eta_{9}$ (w.r.t. $\mathrm{dom}(\eta_{3})$) is at least
$\gamma$.

Chang et al. [CCL+24] constructed a buffered cop decomposition for
$K_{r}$-minor free graphs based on the classic cop decomposition (see [And86,
AGG+19, Fil19a]).

######  Theorem 4 (Buffered cop decompsition).

Let $G$ be a $K_{r}$-minor-free graph, and let $\Delta$ be a positive number.
Then $G$ admits a $(\Delta,\Delta/r,r-1)$-buffered cop decomposition
(efficiently computable).

###  4.2 Additional properties of buffered cop decomposition

Consider a $(\Delta,\gamma,w)$-buffered cop decomposition $\mathcal{T}$ of a
graph $G$. In this subsection we will prove some additional properties of the
buffered cop decomposition, that will later be useful in our construction of
the sparse covers. Let $\overrightarrow{G}_{\mathcal{C}}$ be a directed graph
with the supernodes $\mathcal{C}$ as vertices. For a supernode $\eta$, we add
a directed edge from $\eta$ to any adjacent ancestor supernode
$\eta^{\prime}$. See illustration on the right for the digraph
$\overrightarrow{G}_{\mathcal{C}}$ w.r.t. the decomposition from Figure 1.
Note that $\overrightarrow{G}_{\mathcal{C}}$ is a DAG as all edges are
directed towards the ancestors w.r.t. $\mathcal{T}$.
$\overrightarrow{G}_{\mathcal{C}}$ has another crucial property: suppose that
there are outgoing edges from $\eta$ to $\eta_{1}$ and $\eta_{2}$, where
$\eta_{1}$ is an ancestor of $\eta_{2}$ in $\mathcal{T}$. Then there is an
outgoing edge from $\eta_{2}$ to $\eta_{1}$. Indeed, as $\eta$ and $\eta_{1}$
are neighbors, there is an edge from $\mathrm{dom}(\eta)$ to $\eta_{1}$. As
$\mathrm{dom}(\eta)\subseteq\mathrm{dom}(\eta_{2})$, there is an edge from
$\mathrm{dom}(\eta_{2})$ to $\eta_{1}$. In particular,
$\eta_{1}\in\mathcal{A}_{\eta_{2}}$ and hence there is an edge from
$T_{\eta_{2}}$ (and in particular from $\eta_{2}$) to $\eta_{1}$. We call such
a graph a _Transitive DAG_.

######  Definition 4 (Transitive DAG).

A digraph $\overrightarrow{G}=(V,\overrightarrow{E})$ is called transitive DAG
if it contains no cycles, and for every $x,y,z\in V$ such that
$(x,y),(x,z)\in\overrightarrow{E}$ it holds that either
$(y,z)\in\overrightarrow{E}$ or $(z,y)\in\overrightarrow{E}$.

Another important property of $\overrightarrow{G}_{\mathcal{C}}$ is that the
maximum out degree of a vertex is $w$. Indeed, this just follows from the
definition of buffered cop decomposition. Give a digraph $\overrightarrow{G}$,
and a vertex $v\in V$, the directed ball $B_{\overrightarrow{G}}(v,q)$ is the
set of vertices $u$ such that there is a directed path from $v$ to $u$ in
$\overrightarrow{G}$ of length at most $q$. $v$ is called the center of the
directed ball, while $q$ is it’s radius. We next bound the size of directed
balls in a transitive DAG of bounded out degree.

######  Lemma 1.

Let $\overrightarrow{G}=(V,\overrightarrow{E})$ be a transitive DAG of maximum
out degree $w$. Then for every $v\in V$, and $q\in\mathbb{N}$,
$\left|B_{\overrightarrow{G}}(v,q)\right|\leq{w+q\choose w}$.

###### Proof.

The proof is by induction on $q$. The base case is when $q=0$, and indeed
every directed ball of radius $0$ is of size ${w+0\choose w}=1$ (containing
only the center). Let $v_{0},v_{1},v_{2},\dots,v_{n}$ be a topological
ordering of $\overrightarrow{G}$ vertices. That is for every edge
$(v_{i},v_{j})\in\overrightarrow{E}$ it holds that $i<j$. Denote $v=v_{i_{0}}$
We can assume that $v_{i_{0}}$ has exactly $w$ outgoing edges, as otherwise we
can just add artificial neighbors to the right of $v_{n}$, which will only
increase the size of the directed ball. Denote by
$v_{i_{1}},v_{i_{2}},\dots,v_{i_{w}}$ the endpoints of the $w$ edges going out
of $v$. For $s\in[0,w-1]$, let
$I_{s}=\\{v_{i_{s}},v_{i_{s}+1},\dots,v_{i_{s+1}-1}\\}$ be the “interval” of
vertices starting at $v_{i_{s}}$ and ending just before $v_{i_{s+1}}$. Denote
also $I_{w}=\\{v_{i_{w}},\dots,v_{n}\\}$.

For $s\in[0,w]$, denote by $B_{s}=I_{s}\cap
B_{\overrightarrow{G}}(v_{i_{0}},q)$ the intersection of $I_{s}$ with
$B_{\overrightarrow{G}}(v_{i_{0}},q)$. Clearly
$B_{s}=B_{\overrightarrow{G}[I_{s}]}(v_{i_{s}},q-1)$. That is, $v_{i_{s}}$ is
the only neighbor of $v$ in $I_{s}$, and as $\overrightarrow{G}$ is a DAG, all
the paths from $v_{i_{0}}$ to vertices in $I_{s}$ must go though $v_{i_{s}}$.
Next, we argue that for every vertex $u_{j}\in B_{s}$, $u_{j}$ has outgoing
edges towards $v_{i_{s+1}},v_{i_{s+2}},v_{i_{w}}$. The proof is by induction
w.r.t. the topological order. The base case is $v_{i_{s}}$, and it holds by
the transitive DAG rule as $v_{i_{0}}$ has outgoing edges towards
$v_{i_{s}},\dots,v_{i_{w}}$. By induction, consider $u_{j}\in B_{s}$ and
suppose that the last edge on it shortest paths from $v_{i_{s}}$ to $u_{j}$ is
$(u_{j^{\prime}},u_{j})$. By the inductive hypothesis, $u_{j^{\prime}}$ has
outgoing edges towards $v_{i_{s+1}},\dots,v_{i_{w}}$. According to the rule of
the transitive DAG, $u_{j}$ also has outgoing edges towards
$v_{i_{s+1}},\dots,v_{i_{w}}$, as required. We conclude that the induced
digraph $\overrightarrow{G}[B_{s}]$ has maximum outgoing degree of $s$ (as the
maximum out degree in $\overrightarrow{G}$ is $w$ and each such vertex has
already $w-s$ outgoing edges out of $B_{s}$). By the inductive hypothesis, we
conclude $|B_{s}|\leq{s+(q-1)\choose s}$.

For convenience denote $B_{0}=\\{v_{i_{0}}\\}$ (one can think of it as the
ball in the first interval, that contains only $v_{i_{0}}$ and has out degree
$0$). Then $|B_{0}|=1={q-1\choose 0}$. We conclude

$\left|B_{\overrightarrow{G}}(v,q)\right|=\sum_{s=0}^{w}|B_{s}|\leq\sum_{s=0}^{w}{s+q-1\choose
s}\overset{(*)}{=}{w+q\choose w}\leavevmode\nobreak\ .$

To argue why equality (∗) holds we will use a story. Denote by $A$ all the
subsets of $[w+q]$ of size $w$. Clearly $|A|={w+q\choose w}$. In addition, for
$s\in[0,w]$ note by $A_{s}$ all the subsets of $[w+q]$ where the maximum
number not chosen is $q+s$. That is, every subset in $A_{s}$ have to contain
all the number in $\\{q+s+1,w+s+2,\dots,w+q\\}$, and in addition $s$ number
from $\\{1,\dots,q+s-1\\}$. That is $|A_{s}|={s+q-1\choose s}$. As
$A=\cup_{s=0}^{w}A_{s}$, and all these sets are disjoint, it holds that
${w+q\choose w}=|A|=\sum_{s=0}^{w}|A_{s}|=\sum_{s=0}^{w}{s+q-1\choose s}$,
proving quality (∗), and thus the induction and the lemma follows. ∎

Next, we extend the supernode buffer property as a function of the distance in
$\overrightarrow{G}_{\mathcal{C}}$.

######  Lemma 2.

Consider a vertex $v\in V$ that belongs to a supernode
$v\in\eta\in\mathcal{C}$, and consider an ancestor supernode
$\eta^{\prime}\in\mathcal{C}$ of $\eta$ such that $\eta^{\prime}\notin
B_{\overrightarrow{G}_{\mathcal{C}}}(\eta,2q+1)$ for some $q\geq 0$. Then
$d_{\mathrm{dom}(\eta^{\prime})}(v,\eta^{\prime})>(q+1)\cdot\gamma$.

###### Proof.

The proof is by induction on $q$. The base case is when $q=0$, As
$\eta^{\prime}$ is an ancestor of $\eta$, $v\in\mathrm{dom}(\eta^{\prime})$.
However, as $\eta^{\prime}\notin
B_{\overrightarrow{G}_{\mathcal{C}}}(\eta,1)$, $\eta$ and $\eta^{\prime}$ are
not adjacent in $G$. By the definition of buffered cop decomposition, it
follows that $d_{\mathrm{dom}(\eta^{\prime})}(v,\eta^{\prime})>\gamma$.

For the inductive step, let $P$ be the shortest path in
$G[\mathrm{dom}(\eta^{\prime})]$ from $v$ to $\eta^{\prime}$. Let
$\eta_{1},\dots,\eta_{k}$ be the supernodes in
$B_{\overrightarrow{G}_{\mathcal{C}}}(\eta,1)$. Let $u$ be the first vertex
along $P$ out of $\mathrm{dom}(\eta)\cup\bigcup_{i=1}^{k}\eta_{i}$. $u$ belong
to some supernode $\tilde{\eta}$. Note that $\tilde{\eta}$ is an ancestor of
$\eta$. However, as $u\in\mathrm{dom}(\eta^{\prime})$ it holds that
$\eta^{\prime}$ is an ancestor of $\tilde{\eta}$. Clearly, $\tilde{\eta}\notin
B_{\overrightarrow{G}_{\mathcal{C}}}(\eta,1)$. However, as there is an edge
from a vertex in $\mathrm{dom}(\eta)\cup\bigcup_{i=1}^{k}\eta_{i}$ to
$\tilde{\eta}$, it holds that
$d_{\overrightarrow{G}_{\mathcal{C}}}(\eta,\tilde{\eta})=2$, and hence
$\tilde{\eta}\notin
B_{\overrightarrow{G}_{\mathcal{C}}}(\eta^{\prime},2(q-1)+1)$. Using the
induction hypothesis, it holds that
$d_{\mathrm{dom}(\eta^{\prime})}(u,\eta^{\prime})>q\cdot\gamma$. Using the
base of the induction, $d_{\mathrm{dom}(\tilde{\eta})}(v,u)>\gamma$. We
conclude that $w(P)>q\cdot(\gamma+\gamma=q+1)\cdot\gamma$, as required. ∎

###  4.3 Sparse Covers Construction

This subsection is devoted to proving a the following meta theorem, which
given a buffered cop decomposition constructs a sparse cover. As a corollary,
we will obtain our main Theorem 4.

######  Theorem 5 (From buffered cop decomposition to sparse covers).

Consider a graph $G=(V,E,w)$ that admits a $(\Delta,\gamma,w)$-buffered cop
decomposition where $\gamma\leq\Delta$. Then for every $q\geq 1$, $G$ admits a
strong $\left(4\cdot(\frac{2\Delta}{q\cdot\gamma}+1)\leavevmode\nobreak\
,\leavevmode\nobreak\ {w+2q-1\choose w}\cdot 4\cdot
w\cdot(2+\frac{q\cdot\gamma}{\Delta})\leavevmode\nobreak\
,\leavevmode\nobreak\ 2\cdot(2\Delta+q\cdot\gamma)\right)$-sparse partition
cover.

###### Proof.

Consider a $(\Delta,\gamma,w)$-buffered cop decomposition $\mathcal{T}$ of a
graph $G$. Let $q$ be the input parameter, and let $k={w+2q-1\choose w}$.
Consider two supernodes $\eta,\eta^{\prime}$, where $\eta^{\prime}$ is an
ancestor of $\eta$. We say that $\eta$ and $\eta^{\prime}$ are _nearby_ if
$d_{G_{\mathcal{C}}}(\eta,\eta^{\prime})\leq 2q-1$. Note that by Lemma 1, each
supernode $\eta\in\mathcal{C}$ has at most $k$ nearby nodes (including
itself). We first partition the supernodes into sets
$\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{k}$ such that no two
nearby supernodes belong to the same set. This can be done greedily w.r.t the
order induced by $\mathcal{T}$. Specifically, when we construct
$\mathcal{S}_{1}$ all the supernodes are active. The root $\eta$ joins
$\mathcal{S}_{1}$. We mark $\eta$ and all its nearby supernodes as inactive.
Then all the maximal supernode w.r.t. the order induced by $\mathcal{T}$ among
the remaining active supernodes join $\mathcal{S}_{1}$. We also mark the
nearby supernodes of the newly joining supernodes as inactive. We continue
with this process until no active supernodes remain. In general, to construct
$\mathcal{S}_{i}$, we begin by marking all the supernodes in
$\cup_{j=1}^{i-1}\mathcal{S}_{j}$ as inactive, and continue with the same
process. That is, all the maximal supernodes $\eta^{\prime}$ (w.r.t. order
induced by $\mathcal{T}$ among the remaining active supernodes) join
$\mathcal{S}_{i}$, we then mark all their nearby supernodes as inactive, and
so on.

We argue that every supernode $\eta$ joins one of
$\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{k}$. Indeed, the only way
$\eta$ might become inactive without joining $\mathcal{S}_{i}$ is if one of
its nearby ancestor supernodes joins $\mathcal{S}_{i}$. However, as $\eta$ has
only $k-1$ nearby ancestor clusters (not counting itself), if $\eta$ was
prevented from joining
$\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{k-1}$, it will necessarily
join $\mathcal{S}_{k}$. Consider $\mathcal{S}_{i}$. For every supernode
$\eta\in\mathcal{S}_{i}$, let
$\hat{\eta}=B_{G[\mathrm{dom}(\eta)]}(\eta,q\cdot\gamma)$ be the ball of
radius $q\cdot\gamma$ around $\eta$ in $\mathrm{dom}(\eta)$. We argue the
following:

######  Lemma 3.

Consider the collection
$\\{\hat{\eta}\\}_{\eta\in\mathcal{S}_{1}},\dots,\\{\hat{\eta}\\}_{\eta\in\mathcal{S}_{k}}$.
It holds that:

  1. 1.

For every $i\in[k]$, $\\{\hat{\eta}\\}_{\eta\in\mathcal{S}_{i}}$ is a partial
partition of $V$. That is for every $\eta_{1},\eta_{2}\in\mathcal{S}_{i}$,
$\hat{\eta}_{1}\cap\hat{\eta}_{2}=\emptyset$.

  2. 2.

For every $i\in[k]$ and $\eta\in\mathcal{S}_{i}$, $\hat{\eta}$ contains a
skeleton $T_{\eta}$ which is a shortest path tree in $G[\hat{\eta}]$ with at
most $w$ leafs.

  3. 3.

For every vertex $v\in V$, there is some index $i\in[k]$ and supernode
$\eta\in\mathcal{S}_{i}$ such that
$d_{G[\hat{\eta}]}(v,T_{\eta})\leq\Delta+\frac{q\cdot\gamma}{2}$, and
$B_{G}(v,\frac{q\cdot\gamma}{2})\subseteq\hat{\eta}$.

###### Proof.

We begin by proving the first point. Consider
$\eta_{1},\eta_{2}\in\mathcal{S}_{i}$. If $\eta_{1},\eta_{2}$ does not have
ancestry relationship, then $\mathrm{dom}(\eta_{1}),\mathrm{dom}(\eta_{2})$
are disjoint, which implies $\hat{\eta}_{1}\cap\hat{\eta}_{2}=\emptyset$. We
thus can assume w.l.o.g. that $\eta_{1}$ is an ancestor of $\eta_{2}$. Suppose
for the sake of contradiction that there is a vertex
$v\in\hat{\eta}_{1}\cap\hat{\eta}_{2}$. It holds that
$v\in\mathrm{dom}(\eta_{1})$, and
$d_{G[\mathrm{dom}(\eta_{1})]}(\eta_{1},v)\leq q\cdot\gamma$. From the other
hand, as $\eta_{1},\eta_{2}\in\mathcal{S}_{i}$ they are not nearby. In
particular, $d_{G_{\mathcal{C}}}(\eta_{1},\eta_{2})>2q-1$ which implies
$\eta_{1}\notin B_{\overrightarrow{G}}(\eta_{2},2q-1)$. But by Lemma 2,
$d_{G[\mathrm{dom}(\eta_{1})]}(\eta_{1},v)\geq
d_{G[\mathrm{dom}(\eta_{1})]}(\eta_{1},\eta_{2})>q\cdot\gamma$, a
contradiction.

The second point follows directly from the constriction. For the third point,
let $\eta$ be the first supernode w.r.t. the order induced by $\mathcal{T}$
that intersects the ball $B_{G}(v,\frac{q\cdot\gamma}{2})$. Suppose that
$\eta\in\mathcal{S}_{i}$. By the minimality of $\eta$, it holds that
$B_{G}(v,\frac{q\cdot\gamma}{2})\subseteq\mathrm{dom}(\eta)$. In particular,
as $\eta$ intersects $B_{G}(v,\frac{q\cdot\gamma}{2})$, by triangle inequality
it follows that
$d_{G[\hat{\eta}]}(v,T_{\eta})\leq\Delta+\frac{q\cdot\gamma}{2}$, and
$B_{G}(v,\frac{q\cdot\gamma}{2})\subseteq\hat{\eta}$. ∎

Next we argue that each enlarged supernode can be efficiently clustered.

######  Lemma 4.

Consider an enlarged supernode $\hat{\eta}$. There is set of partitions
$\mathcal{C}^{\hat{\eta}}_{1},\dots,\mathcal{C}^{\hat{\eta}}_{q}$ of size
$s\leq 4w\cdot(2+\frac{q\cdot\gamma}{\Delta})$ with strong diameter
$2\cdot(2\Delta+q\cdot\gamma)$ such that for every vertex $v\in\hat{\eta}$ at
distance at most $\Delta+\frac{q\cdot\gamma}{2}$ from $T_{\eta}$, the ball
$B_{G[\hat{\eta}]}(v,\frac{q\cdot\gamma}{2})$ is fully contained in some
cluster in some partition.

###### Proof.

Let $N\subseteq T_{\eta}$ be an $\Delta$-net. That is, a set of points in
$T_{\eta}$ at pairwise distance greater than $\Delta$, and such that for every
point $v\in T_{\eta}$, there is some net point $u\in N$ at distance at most
$d_{G[T_{\eta}]}(u,v)\leq\Delta$. Such a set can be constructed greedily. We
say that a pair of net points $u,v\in N$ is nearby if
$d_{G[\hat{\eta}]}(v,u)\leq 2\cdot\left(2\Delta+q\cdot\gamma\right)$.

######  Claim 1.

Every net point $v\in N$ has at most
$s=4w\cdot(2+\frac{q\cdot\gamma}{\Delta})$ nearby net points (including $v$).

###### Proof.

$T_{\eta}$ is a shortest path tree with at most $w$ leafs. In particular,
$T_{\eta}$ consist of the shortest paths $P_{1},\dots,P_{k}$ for $k\leq w$.
Fix some $P_{i}$. Let $u_{1},u_{2},\dots,u_{t}$ be the net points along
$P_{i}$ which are nearby $v$, sorted w.r.t. their position along $P_{i}$. As
$P_{i}$ is a shortest path, and the pairwise distance between every pair of
consecutive net points is at least $\Delta$, we have that
$d_{G[\hat{\eta}]}(u_{1},u_{t})>(t-1)\cdot\Delta$. From the other hand, as
both $u_{1},u_{t}$ are nearby $v$, by the triangle inequality it holds that
$d_{G[\hat{\eta}]}(u_{1},u_{t})\leq
d_{G[\hat{\eta}]}(u_{1},v)+d_{G[\hat{\eta}]}(v,u_{t})\leq
4\cdot(2\Delta+q\cdot\gamma)$. It follows that
$(t-1)\cdot\Delta<4\cdot(2\Delta+q\cdot\gamma)$ and thus $t\leq
4\cdot(2+\frac{q\cdot\gamma}{\Delta})$. The claim now follows as there are at
most $w$ such paths. ∎

Partition $N$ into subsets $N_{1},\dots,N_{s}$ such that no two nearby points
will belong to the same set $N_{i}$ (this can be done in a greedy manner). For
every subset $N_{i}$, consider the partition with the clusters
$\left\\{B_{G[\hat{\eta}]}(v,2\Delta+q\cdot\gamma)\mid v\in N_{i}\right\\}$,
and the rest of $\hat{\eta}$ vertices being singletons. Note that this is
indeed a partition as $N_{i}$ does not contain nearby net points and hence all
this balls are disjoint. Clearly the strong diameter of each cluster is at
most $2\cdot(2\Delta+q\cdot\gamma)$. Finally, consider a vertex
$v\in\hat{\eta}$ such that there is $x\in T_{\eta}$ with
$d_{G[\hat{\eta}]}(v,x)\leq\Delta+\frac{q\cdot\gamma}{2}$. Let $y\in N$ be the
closest net point to $x$. By the triangle inequality
$d_{G[\hat{\eta}]}(v,y)\leq d_{G[\hat{\eta}]}(v,x)+d_{G[\hat{\eta}]}(v,x)\leq
2\Delta+\frac{q\cdot\gamma}{2}$. Let $i$ be an index such that $y\in N_{i}$.
It follows that the ball $B_{G[\hat{\eta}]}(y,2\Delta+q\cdot\gamma)$, which
belongs to the respective partition of $N_{i}$ contains
$B_{G[\hat{\eta}]}(v,\frac{q\cdot\gamma}{2})$ as required. ∎

Our final set of partitions is constructed naturally. We first use Lemma 3 to
obtain the collections
$\\{\hat{\eta}\\}_{\eta\in\mathcal{S}_{1}},\dots,\\{\hat{\eta}\\}_{\eta\in\mathcal{S}_{k}}$
of enlarged supernodes. Then for every $i\in[k]$, and every
$\hat{\eta}\in\mathcal{S}_{i}$, we use Lemma 4 to obtain partitions
$\mathcal{C}^{\hat{\eta}}_{1},\dots,\mathcal{C}^{\hat{\eta}}_{s}$. Finally,
for every $i\in[k]$, and $j\in[s]$, we create the partition
$\left\\{\mathcal{C}_{j}^{\hat{\eta}}\right\\}_{\eta\in\mathcal{S}_{i}}$ of
$G$, and add all the non clustered vertices as singletons. Note that we
obtained $k\cdot s={w+2q-1\choose w}\cdot 4\cdot
w\cdot(2+\frac{q\cdot\gamma}{\Delta})$ partitions. Clearly, each cluster in
every partition has strong diameter at most $2\cdot(2\Delta+q\cdot\gamma)$.
Finally, we prove the cover property. Consider a vertex $v\in V$. By Lemma 3
there is some index $i\in[k]$ and supernode $\eta\in\mathcal{S}_{i}$ such that
$d_{G[\hat{\eta}]}(v,T_{\eta})\leq\Delta+\frac{q\cdot\gamma}{2}$, and
$B_{G}(v,\frac{q\cdot\gamma}{2})\subseteq\hat{\eta}$. By Lemma 4, the ball
$B_{G[\hat{\eta}]}(v,\frac{q\cdot\gamma}{2})=B_{G}(v,\frac{q\cdot\gamma}{2})$
is fully contained in some cluster in some partition. Thus our padding
parameter is
$\frac{2\cdot(2\Delta+q\cdot\gamma)}{\frac{q\cdot\gamma}{2}}=4\cdot(\frac{2\Delta}{q\cdot\gamma}+1)$,
as required. ∎

We are now ready to prove our main Theorem 1 (restated for convenience). See 1

###### Proof.

According to [CCL+24] (Theorem 4), every $K_{r}$ minor free graph $G$ admits
$(\Delta,\Delta/r,r-1)$-buffered cop decomposition for every $\Delta>0$. Using
Theorem 5 it follows that $G$ admits strong
$\left(4\cdot(\frac{2r}{q}+1)\leavevmode\nobreak\ ,\leavevmode\nobreak\
{r+2q-2\choose r-1}\cdot 4\cdot r\cdot(2+\frac{q}{r})\leavevmode\nobreak\
,\leavevmode\nobreak\ 2\cdot(2+\frac{q}{r})\cdot\Delta\right)$-sparse
partition cover, for arbitrary $\Delta>0$. It follows that every $K_{r}$ minor
free graph admits strong $\left(4\cdot(\frac{2r}{q}+1)\leavevmode\nobreak\
,\leavevmode\nobreak\ {r+2q-2\choose r-1}\cdot 4\cdot
r\cdot(2+\frac{q}{r})\right)$-SPCS.

Fixing $q=1$ we obtain that every $K_{r}$ minor free graph admits strong
$\left(4\cdot(2r+1)\leavevmode\nobreak\ ,\leavevmode\nobreak\ {r\choose
r-1}\cdot 4\cdot
r\cdot(2+\frac{1}{r})\right)=\left(O(r),O(r^{2})\right)$-SPCS. Next, fix
$q=\frac{8r}{\varepsilon}$, using the identity ${n\choose
k}\leq\left(\frac{n\cdot e}{k}\right)^{k}$, we have
${r+\frac{16r}{\varepsilon}-2\choose r-1}\cdot 4\cdot
r\cdot(2+\frac{8}{\varepsilon})\leq\left(\frac{(r+\frac{16r}{\varepsilon}-2)\cdot
e}{r-1}\right)^{r-1}\cdot
O(\frac{r}{\varepsilon})=O(\frac{1}{\varepsilon})^{r}$, and thus $G$ admits a
strong $\left(4+\varepsilon,O(\frac{1}{\varepsilon})^{r}\right)$-SPCS. The
theorem follows by scaling $\varepsilon$ accordingly. ∎

##  5 Metric Embedding into $\ell_{\infty}$ from Sparse Partition Cover

The main result of this section is a meta theorem (Theorem 6) that transforms
a SPCS into a low distortion/dimension metric embedding into $\ell_{\infty}$.
This reduction is applicable for graph families which are closed under re-
weighting (abbreviated CURW). A graph family $\mathcal{F}$ is CURW if for
every weighted graph $G=(V,E,w)\in{\cal F}$ in the family, it holds that for
every weight function $w^{\prime}:E\rightarrow\mathbb{R}_{\geq 0}$, the
reweighed graph $G^{\prime}=(V,E,w^{\prime})\in{\cal F}$ is also in the
family. Many graph families are CURW, some examples being general graphs,
planar graphs, graphs with bounded treewidth\pathwidth \genus, and most
importantly for us, $H$ minor free graphs. There are also well studied
families which are not CURW, such as graphs with bounded doubling dimension,
or bounded highway dimension.

######  Theorem 6 (From SPCS to Metric embedding).

Consider a CURW graph family ${\cal F}$, such that every $G\in{\cal F}$ admits
a $(\beta,\tau)$-SPCS. Then for every $\varepsilon>0$, every $n$-point graph
$G=(V,E,w)\in{\cal F}$ admits an efficiently computable embedding
$f:V\rightarrow\ell_{\infty}^{k}$ with distortion $(1+\varepsilon)\cdot
2\beta$ and dimension
$k=O\left(\frac{\tau}{\varepsilon}\cdot\log\frac{\beta}{\varepsilon}\cdot\log(\frac{n\cdot\beta}{\varepsilon})\right)$.

Using our Theorem 1 with $\varepsilon=1$, Corollary 1 follows. We restate it
for convenience: See 1

One can also use our
$\left(4+\varepsilon,O(\frac{1}{\varepsilon})^{r}\right)$-SPCS to obtain
embedding into
$\ell_{\infty}^{O(\frac{1}{\varepsilon})^{r+1}\cdot\log\frac{1}{\varepsilon}\cdot\log\frac{n}{\varepsilon}}$
with distortion $8+\varepsilon$. However, for the case of minor-free graphs,
we open the black box of Theorem 6 and obtain an improved embedding with
distortion $3+\varepsilon$ (see Theorem 2) .

The plan for the section is as follows: first in Section 5.1 we construct a
prefix free code, which will later be used in the construction of the
embedding. Then, in Section 5.2 we construct a reduction from SPCS into metric
embedding (see Lemma 8). Note that there is no assumption of a CURW graph
family here. The resulting dimension is
$O\left(\frac{\tau}{\varepsilon}\cdot\log\frac{\beta}{\varepsilon}\cdot\log(n\Phi)\right)$,
where $\Phi=\frac{\max_{u,v}d_{G}(u,v)}{\min_{u,v}d_{G}(u,v)}$ is the aspect
ratio. Then in Section 5.3 we use Lemma 8 to obtain our main Theorem 6.
Finally, in Section 5.4 we improve the result for minor free graph to obtain
distortion $3+\varepsilon$.

###  5.1 Prefix Free Codes

This sub-section is devoted to the construction of prefix free codes. $\\{\pm
1\\}^{*}$ stands for all finite sequences of $\\{\pm 1\\}$.

######  Definition 5.

A code for elements $X$ is a function $h:X\rightarrow\left\\{\pm
1\right\\}^{*}$. The code is prefix free if for every $x,y\in X$, $h(x)$ and
$h(y)$ are not the prefixes of each other. That is, there is no $L\in\\{\pm
1\\}^{*}$ such that either $h(x)\circ L=h(y)$, or $h(y)\circ L=h(x)$.

In the following lemma we construct a prefix free code where the length of the
code word of $x$ is bounded by
$2\cdot\left\lceil\log\frac{\mu(X)}{\mu(x)}\right\rceil$. This statement is
not new, and even better prefix free codes are known (see e.g. [KN76]).
Nevertheless, we provide a proof of Lemma 5 in Appendix A for the sake of
completeness.

######  Lemma 5.

Consider a set $X$ with a weight function $\mu:X\rightarrow\mathbb{R}_{>0}$.
Denote $\mu(X)=\sum_{x\in X}\mu(X)$. Then there is a prefix free code $h$,
such that for every $x\in X$, $|h(x)|\leq
2\cdot\left\lceil\log\frac{\mu(X)}{\mu(x)}\right\rceil$.

###  5.2 Embedding into $\ell_{\infty}$ from sparse partition cover scheme

In this subsection, given a SPCS, we construct a metric embedding into
$\ell_{\infty}$, where the dimension depans on the aspect ratio (Lemma 8). We
begin this subsection by showing that we can turn a collection of unrelated
partitions it different scales into laminar partitions (Lemma 6). This
statement was implicitly proved in [KLMN05], as well as in other
constructions. The following lemma is an adaptation from [FL22a]. We provide a
proof for the sake of completeness.

######  Lemma 6.

Consider a finite metric space $(X,d_{X})$ that admits a $(\beta,\tau)$-sparse
partition cover scheme. Then for every $a>0$, and $\varepsilon\in(0,1)$ there
is a collection of hierarchical partitions of $X$:
$\\{\mathcal{P}_{q}^{i}\\}_{q\in\mathbb{Z}}$, $i\in[\tau]$ with the following
properties:

  1. 1.

For each $j$, $\\{\mathcal{P}_{i}^{j}\\}_{i\in\mathbb{Z}}$ is a hierarchical
partition. That is $\forall i,j$, $\mathcal{P}_{i}^{j}$ is a refinement of
$\mathcal{P}_{i+1}^{j}$.

  2. 2.

Fix $\Delta_{i}=a\cdot(\frac{4\beta}{\epsilon})^{i}$. For every $j$ and
$i\in\mathbb{Z}$, $\mathcal{P}_{i}^{j}$ has diameter
$(1+\varepsilon)\cdot\Delta_{i}$.

  3. 3.

For every $x\in X$ and $i\in\mathbb{Z}$, there is some $j\in[\tau]$ such that
the ball $B_{X}(x,\frac{\Delta_{i}}{\beta(1+\varepsilon)})$ is fully contained
in some cluster of $\mathcal{P}_{i}^{j}$.

###### Proof.

Assume w.l.o.g. that the minimal pairwise distance in $X$ is $1$ (otherwise
one can scale accordingly), while the maximal pairwise distance is $\Phi$. Set
$I=\lceil\log_{\nicefrac{{4\beta}}{{\epsilon}}}\nicefrac{{\Phi}}{{a}}\rceil$.
For $i\in[0,I]$, let
$\mathbb{P}_{i}=\\{\mathcal{P}_{i}^{1},\dots,\mathcal{P}_{i}^{\tau}\\}$ be a
$(\beta,\tau,\Delta_{i})$-sparse partition cover (we assume that
$\mathcal{P}_{i}$ has exactly $\tau$ partitions, we can enforce this
assumption by duplicating partitions if necessary). Fix some $j$. For $i<0$,
let $\mathcal{P}^{j}_{i}$ be the partition where each vertex is a singleton.
For $i>I$ let $\mathcal{P}^{j}_{i}$ be the trivial partition with a single
cluster $\\{X\\}$. Consider $\\{\mathcal{P}^{j}_{i}\\}_{i\geq 0}^{I}$. We will
inductively define a new set of partitions
$\\{\tilde{\mathcal{P}}^{j}_{i}\\}_{i\geq 0}^{I}$, enforcing it to be a
laminar system, while still closely resembling the original partitions.

Levels bellow $0$ and above $I$ stay as-is. Inductively, for any $i\geq 0$,
after constructing $\tilde{\mathcal{P}}^{j}_{i-1}$ from
$\mathcal{P}^{j}_{i-1}$, we will construct $\tilde{\mathcal{P}}^{j}_{i}$ from
$\mathcal{P}^{j}_{i}$ using $\tilde{\mathcal{P}}^{j}_{i-1}$. Let
$\mathcal{P}_{i}^{j}=\left\\{C_{1},\dots,C_{\phi}\right\\}$ be the clusters in
the partition $\mathcal{P}_{i}^{j}$. For each $q\in[1,\phi]$, let
$Y_{q}=X\setminus\cup_{a<q}\tilde{C}_{a}$ be the set of unclustered points
(w.r.t. level $i$, before iteration $q$). Let $C^{\prime}_{q}=C_{q}\cap Y_{q}$
be the cluster $C_{q}$ restricted to vertices in $Y_{q}$, and let
$S_{C^{\prime}_{q}}=\left\\{C\in\tilde{\mathcal{P}}_{i-1}^{j}\mid C\cap
C^{\prime}_{q}\neq\emptyset\right\\}$ be the set of new level-$(i-1)$ clusters
with non empty intersection with $C^{\prime}_{q}$. We set the new cluster
$\tilde{C}_{q}=\cup S_{C^{\prime}_{q}}$ to be the union of these clusters, and
continue iteratively. Clearly, $\tilde{\mathcal{P}}_{i-1}^{j}$ is a refinement
of $\tilde{\mathcal{P}}_{i}^{j}$. We conclude that
$\left\\{\tilde{\mathcal{P}}_{i}^{j}\right\\}_{i\geq-1}$ is a laminar
hierarchical set of partitions that refine each other.

We next argue by induction that $\tilde{\mathcal{P}}_{i}^{j}$ has diameter
$(1+\varepsilon)\cdot\Delta_{i}$. Consider
$\tilde{C}_{q}\in\tilde{\mathcal{P}}_{i}^{j}$. It consists of
$C^{\prime}_{q}\subseteq C_{q}\in\mathcal{P}_{i}^{j}$ and of clusters in
$\tilde{\mathcal{P}}_{i-1}^{j}$ intersecting $C^{\prime}_{q}$. As the diameter
of $C^{\prime}_{q}$ is bounded by $\mathrm{diam}(C_{q})\leq\Delta_{i}$, and by
the induction hypothesis, the diameter of each cluster
$C\in\tilde{\mathcal{P}}_{i-1}^{j}$ is bounded by
$(1+\varepsilon)\cdot\Delta_{i-1}$, we conclude that the diameter of
$\tilde{C}_{q}$ is bounded by

$\Delta_{i}+2\cdot(1+\epsilon)\Delta_{i-1}=\Delta_{i}\cdot\left(1+\frac{2(1+\epsilon)}{4\beta}\cdot\epsilon\right)\leq(1+\varepsilon)\cdot\Delta_{i}\leavevmode\nobreak\
,$

since $\beta\geq 1$ and $\varepsilon<1$.

Finally, we argue that every ball is fully contained in some cluster. Fix,
$x\in X$ and $i\in\mathbb{Z}$. If $i<0$ or $i>I$ then there is nothing to
prove. We will thus assume $i\in[0,I]$. Set

$R=\frac{\Delta_{i}}{\beta}-(1+\varepsilon)\cdot\Delta_{i-1}=\frac{\Delta_{i}}{\beta}\cdot\left(1-(1+\varepsilon)\cdot\frac{\epsilon}{4}\right)\geq\frac{\Delta_{i}}{(1+\varepsilon)\cdot\beta}\leavevmode\nobreak\
.$

By construction, there is some index $j$ such that the ball
$B_{X}(x,\frac{\Delta_{i}}{\beta})$ is fully contained in a single cluster
$C_{q}$ in the partition $\mathcal{P}_{i}^{j}$. It will be enough to show that
the ball $B_{X}(x,R)$ is fully contained in the cluster $\tilde{C}_{q}$ of
$\tilde{\mathcal{P}}_{i}^{j}$. Suppose for the sake of contradiction
otherwise, then there have to be a vertex $y\in B_{X}(x,R)\setminus Y_{q}$. In
particular, $y$ belongs to a cluster $Q\in\tilde{\mathcal{P}}_{j}^{i-1}$ that
intersected $C_{q^{\prime}}\in\mathcal{P}_{i}^{j}$ for $q^{\prime}<q$. Let
$z\in C_{q^{\prime}}\cap Q$. As the maximum diameter of
$\tilde{\mathcal{P}}_{j}^{i-1}$ cluster is $(1+\varepsilon)\cdot\Delta_{i-1}$,
it follows that

$d_{X}(z,x)\leq
d_{X}(z,y)+d_{X}(y,x)\leq(1+\varepsilon)\cdot\Delta_{i-1}+R=\frac{\Delta_{i}}{\beta}\leavevmode\nobreak\
.$

But this implies that $z\in C_{q}$ and not $C_{q^{\prime}}$, a contradiction.

∎

Consider a partition $\mathcal{P}$, and a point $x\in X$. Let
$C_{x}\in\mathcal{P}$ be the cluster containing $x$. We denote by
$\partial_{\mathcal{P}}(x)=d_{X}(x,X\setminus C_{x})$ the distance between $x$
and the boundary of it’s cluster $C_{x}$. The following embedding will be the
core stone of our construction:

######  Lemma 7.

Consider a finite metric space $(X,d_{X})$, and a hierarchy of laminar
partitions $\mathcal{P}_{1},\dots,\mathcal{P}_{k}$ of $X$ (that is
$\mathcal{P}_{i}$ is a refinement of $\mathcal{P}_{i+1})$. Then there is an
embedding $f:X\rightarrow\ell_{\infty}^{2\log|X|+2k}$ such that:

  1. 1.

Lipschitz: $\forall x,y\in X,\leavevmode\nobreak\ \|f(x)-f(y)\|_{\infty}\leq
2\cdot d_{X}(x,y)$.

  2. 2.

For every pair of points $x,y\in X$ and partition $\mathcal{P}_{i}$ where
$x,y$ belong to different clusters, it holds that
$\|f(x)-f(y)\|_{\infty}\geq\partial_{\mathcal{P}_{i}}(x)+\partial_{\mathcal{P}_{i}}(y)$.

###### Proof.

The construction and proof is by induction on $|X|$, the number of metric
points. The base case where $|X|=1$ is trivial, as the empty embedding will
do. Suppose that the partition $\mathcal{P}_{k}$ is into the clusters
$X_{1},X_{2},\dots,X_{m}$. If $m=1$ (that is the trivial partition), then we
can simply ignore this partition (as we don’t guarantee anything w.r.t. this
partition). If all the partitions in the hierarchy are trivial, then again
there is nothing to prove (as no pair is ever separated) and the empty
embedding will do. We thus can assume that $m\geq 2$.

Using the induction hypothesis, we construct functions
$f_{j}:X_{j}\rightarrow\ell_{\infty}^{2\log|X_{j}|+2(k-1)}$ fulfilling the
conditions of the lemma. Let $Y$ be a set with the elements being
$X_{1},\dots,X_{m}$ and weight function $\mu(X_{j})=|X_{j}|$. Note that
$\mu(Y)=|X|$. Using Lemma 5 we obtain a prefix free code
$h:\\{X_{1},\dots,X_{m}\\}\rightarrow\\{\pm 1\\}^{*}$ such that for every
$j\in[1,m]$,
$|h(X_{j})|=2\cdot\left\lceil\log\frac{\mu(Y)}{\mu(X_{j})}\right\rceil=2\cdot\left\lceil\log\frac{|X|}{|X_{j}|}\right\rceil$
(we can obtain equality instead of weak inequality by padding with arbitrary
$\pm 1$). We define a new embedding $f:X\rightarrow\ell_{\infty}$, such that
for a point $x\in X_{j}$, for every $q\leq
2\cdot\left\lceil\log\frac{\mu(Y)}{\mu(X_{j})}\right\rceil$, the $q$‘th
coordinate equal to
$(f(x))_{q}=(h(X_{j}))_{q}\cdot\partial_{\mathcal{P}_{k}}(x)$. The rest of the
coordinates will be just a concatenation of $f_{j}(x)$. For every point $x\in
X_{j}$, the total number of coordinates is bounded by

$2\log|X_{j}|+2(k-1)+2\cdot\left\lceil\log\frac{|X|}{|X_{j}|}\right\rceil\leavevmode\nobreak\
\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \leavevmode\nobreak\
2\log|X_{j}|+2k+2\cdot\log\frac{|X|}{|X_{j}|}\leavevmode\nobreak\
\leavevmode\nobreak\ =\leavevmode\nobreak\ \leavevmode\nobreak\
2k+2\log|X|\leavevmode\nobreak\ \leavevmode\nobreak\ .$

We can pad with $0$ coordinates to get exactly $2k+2\log|X|$ coordinates.

Next we prove that our embeddings is expanding by at most a factor of $2$. The
proof follows the construction, and hence it is also by induction on $|X|$.
Consider a pair $x,y\in X$. Suppose first that $x,y$ belong to the same
cluster $X_{j}$ in the partition $\mathcal{P}_{k}$. For every coordinate $q$
among the first $2\cdot\left\lceil\log\frac{|X|}{|X_{j}|}\right\rceil$
coordinates, by the triangle inequality it holds that

$\displaystyle\left|(f(x))_{q}-(f(y))_{q}\right|$
$\displaystyle=\left|h_{q}(X_{j})\cdot\partial_{\mathcal{P}_{k}}(x)-h_{q}(X_{j})\cdot\partial_{\mathcal{P}_{k}}(y)\right|$
$\displaystyle=\left|d_{X}(x,X\setminus X_{j})-d_{X}(y,X\setminus
X_{j})\right|\leq d_{X}(x,y)\leavevmode\nobreak\ .$ (1)

The rest of the coordinates are a concatenation of $f_{j}(x),f_{j}(y)$ and the
upper bound follows by the induction hypothesis.

Next, suppose that $x\in X_{j}$, $y\in X_{j^{\prime}}$ for $j\neq j^{\prime}$.
Consider a coordinate $q$. Note that $(f(x))_{q}$ is either a $0$, or equals
to $\sigma_{x}\cdot\partial_{\mathcal{P}_{k^{\prime}}}(x)=\sigma_{x}\cdot
d_{X}(x,X\setminus Y_{j})$ where $\sigma_{x}\in\\{\pm 1\\}$,
$k^{\prime}\in[1,k]$, and $Y_{j}$ is the cluster containing $x$ in
$\mathcal{P}_{k^{\prime}}$. In particular, $Y_{j}\subset X_{j}$. Similarly
$(f(y))_{q}$ is either a $0$ or $\sigma_{y}\cdot d_{X}(x,X\setminus
Y_{j^{\prime}})$ for $\sigma_{y}\in\\{\pm 1\\}$ and $Y_{j^{\prime}}\subseteq
X_{j^{\prime}}$. It holds that

$\displaystyle\left|(f(x))_{q}-(f(y))_{q}\right|$
$\displaystyle\leq\left|(f(x))_{q}\right|+\left|(f(y))_{q}\right|\leq\left|d_{X}(x,X\setminus
Y_{j})\right|+\left|d_{X}(y,X\setminus Y_{j^{\prime}})\right|$
$\displaystyle\leq\left|d_{X}(x,y)\right|+\left|d_{X}(y,x)\right|=2\cdot
d_{X}(y,x)\leavevmode\nobreak\ ,$ (2)

where the third inequality holds as $y\notin Y_{j}$ and $x\notin
Y_{j^{\prime}}$.

It remains to prove the lower bound. Consider a pair $x,y\in X$ that belong to
different clusters in $\mathcal{P}_{i}$. Let
$X_{j},X_{j^{\prime}}\in\mathcal{P}_{i}$ be the clusters containing $x$ and
$y$ respectively. Let $i^{\prime}\in[i,k]$ be the maximal index such that
$x,y$ belong to different clusters in $\mathcal{P}_{i^{\prime}}$. Let
$Y_{j},Y_{j^{\prime}}\in\mathcal{P}_{i^{\prime}}$ be the clusters containing
$x$ and $y$ respectively. As $i\leq i^{\prime}$, $\mathcal{P}_{i}$ is a
refinement of $\mathcal{P}_{i^{\prime}}$. In particular, $X_{j}\subseteq
Y_{j}$ and $X_{j^{\prime}}\subseteq Y_{j^{\prime}}$. As $x$ and $y$ belong to
the same clusters in the partitions
$\mathcal{P}_{j^{\prime}+1},\dots,\mathcal{P}_{k}$, their first coordinates of
$f(x),f(y)$ correspond to these partitions and are “aligned”. Suppose that all
these embedding fill the first $s$ coordinates. Then we have the partition
w.r.t. $\mathcal{P}_{i^{\prime}}$. In particular, we used a prefix free code
$h$, and hence there is some $q$ such that both
$h_{q}(Y_{j}),h_{q}(Y_{j^{\prime}})$ are defined and different. We conclude

$\displaystyle\left\|f(x)-f(y)\right\|_{\infty}$
$\displaystyle\geq\left|(f(x))_{s+q}-(f(y))_{s+q}\right|$
$\displaystyle=\left|h_{q}(Y_{j})\cdot\partial_{\mathcal{P}_{j^{\prime}}}(x)-h_{q}(Y_{j^{\prime}})\cdot\partial_{\mathcal{P}_{j^{\prime}}}(y)\right|$
$\displaystyle=\left|\partial_{\mathcal{P}_{j^{\prime}}}(x)\right|+\left|\partial_{\mathcal{P}_{j^{\prime}}}(y)\right|\leavevmode\nobreak\
\leavevmode\nobreak\ \geq\leavevmode\nobreak\ \leavevmode\nobreak\
\left|\partial_{\mathcal{P}_{j}}(x)\right|+\left|\partial_{\mathcal{P}_{j}}(y)\right|\leavevmode\nobreak\
,$

where the last inequality holds as
$\partial_{\mathcal{P}_{j^{\prime}}}(x)=d_{X}(x,X\setminus Y_{j})\geq
d_{X}(x,X\setminus X_{j})=\partial_{\mathcal{P}_{j}}(x)$ because
$X_{j}\subseteq Y_{j}$. Similarly for $y$.

∎

######  Lemma 8.

Consider an $n$-point metric space $(X,d_{X})$ that admits a
$(\beta,\tau)$-sparse partition cover scheme, and such that all the pairwise
distances in $X$ are between $1$ and $\Phi$. Then for every
$\varepsilon\in(0,1)$, there is an (efficiently computable) embedding
$f:X\rightarrow\ell_{\infty}^{k}$ with distortion $(1+\varepsilon)\cdot
2\beta$, for
$k=O\left(\frac{\tau}{\varepsilon}\cdot\log\frac{\beta}{\varepsilon}\cdot\log(n\Phi)\right)$.

###### Proof.

We will construct embedding with distortion $(1+O(\varepsilon))\cdot\beta$,
afterwards one can obtain the lemma by scaling $\varepsilon$ accordingly. For
every
$q\in\left\\{1,2,\dots,\left\lceil\log_{1+\varepsilon}\frac{4\beta}{\varepsilon}\right\rceil\right\\}$
let $a_{q}=(1+\varepsilon)^{q}$. Using Lemma 6 with parameters $a_{q}$ and
$\varepsilon$, construct hierarchical partitions
$\\{\mathcal{P}_{i}^{1,q}\\}_{i\in\mathbb{Z}},\dots,\\{\mathcal{P}_{i}^{\tau,q}\\}_{i\in\mathbb{Z}}$.
Fix $I=\lceil\log_{\nicefrac{{4\beta}}{{\epsilon}}}\Phi\rceil$. For every
$q\in\left\lceil\log_{1+\varepsilon}\frac{4\beta}{\varepsilon}\right\rceil$
and $j\in[\tau]$, consider the hierarchical partition
$\\{\mathcal{P}_{i}^{j,q}\\}_{i=-1}^{I}$. Using Lemma 7, we construct an
embedding $f_{j,q}:X\rightarrow\ell_{\infty}^{2\log n+2(I+2)}$. Our final
embedding is simply a concatenation of all this embeddings:
$\circ_{j\in[\tau],q\in[\lceil\log_{1+\varepsilon}\frac{4\beta}{\varepsilon}\rceil]}f_{j,q}$.
The overall dimension is
$\tau\cdot\lceil\log_{1+\varepsilon}\frac{4\beta}{\varepsilon}\rceil\cdot\left(2\log
n+2(I+1)\right)=O\left(\frac{\tau}{\varepsilon}\cdot\log\frac{\beta}{\varepsilon}\cdot\log(n\Phi)\right)$.

Next we bound the distortion. Consider a pair $x,y\in X$. Let
$q\in[0,\lfloor\log_{1+\epsilon}\frac{4\beta}{\epsilon}\rfloor]$, and
$i\in[-1,I]$ be indices such that
$(1+\epsilon)^{q}(\frac{4\beta}{\epsilon})^{i}<\frac{d_{X}(x,y)}{1+\varepsilon}\leq(1+\epsilon)^{q+1}(\frac{4\beta}{\epsilon})^{i}$.
Fix $\Delta_{i}=a_{q}\cdot(\frac{4\beta}{\varepsilon})^{i}$, and note that
$(1+\varepsilon)\cdot\Delta_{i}=(1+\varepsilon)^{q+1}\cdot(\frac{4\beta}{\varepsilon})^{i}<d_{X}(x,y)$.
There is some $j\in[\tau]$ such that in the hierarchical partition
$\\{\mathcal{P}_{i^{\prime}}^{j,q}\\}_{i^{\prime}=-1}^{I}$, the ball
$B_{X}(x,\frac{\Delta_{i}}{\beta(1+\varepsilon)})$ is fully contained in some
cluster of $\mathcal{P}_{i}^{j,q}$. In particular,
$\partial_{\mathcal{P}^{j,q}_{i}}(x)>\frac{\Delta_{i}}{\beta(1+\varepsilon)}$.
According to Lemma 6, $\mathcal{P}_{i}^{j,q}$ is a
$(1+\varepsilon)\cdot\Delta_{i}$ bounded partition. It follows that $x$ and
$y$ have to belong to different clusters in $\mathcal{P}_{i}^{j,q}$. Using
Lemma 7 we conclude

$\displaystyle\left\|f(x)-f(y)\right\|_{\infty}$
$\displaystyle\geq\left\|f_{j,q}(x)-f_{j,q}(y)\right\|_{\infty}\geq\partial_{\mathcal{P}_{i}^{j,q}}(x)+\partial_{\mathcal{P}_{i}^{j,q}}(y)$
$\displaystyle\geq\frac{\Delta_{i}}{\beta(1+\varepsilon)}\geq\frac{d_{X}(x,y)}{\beta(1+\varepsilon)^{3}}=\frac{d_{X}(x,y)}{\beta(1+O(\varepsilon))}\leavevmode\nobreak\
.$ (3)

Furthermore, as all the embeddings created by Lemma 7 are $2$-Lipschitz, so is
$f$. The lemma now follows.

∎

###  5.3 Removing the dependence on the aspect ratio

In this section we prove Theorem 6. The following is the main lemma of the
subsection, where we show that in a metric embeddings from a CURW family to
$\ell_{\infty}$, one can remove the dependence on the aspect ratio. This is a
general phenomena, independent of SPCS.

######  Lemma 9.

Consider a CURW graph family ${\cal F}$, and suppose that every $n$ \- point
graph $G\in{\cal F}$ with aspect ratio $\Phi$ can be embedded into
$\ell_{\infty}^{k}$ with expansion $\rho$, contraction $\beta$, and dimension
$k=\varphi(n,\Phi,\rho,\beta)$, where
$\varphi:\mathbb{N}\times\mathbb{R}_{\geq 1}^{3}\rightarrow\mathbb{N}$ is some
coordinate-wise monotone function. Then for every
$\epsilon\in(0,\frac{1}{2})$, every $n$ \- point graph $G\in{\cal F}$ can be
embedded into $\ell_{\infty}^{k^{\prime}}$ with expansion
$(1+\delta)\cdot\rho$, contraction $(1+\epsilon)\cdot\beta$, and dimension
$3\cdot\varphi(n,\left(\frac{8\cdot\rho\cdot\beta}{\epsilon}\right)^{2}\cdot
n^{3},\rho,\beta)$.

Combining Lemmas 8 and 9 we get our main meta Theorem 6. The rest of this
section is devoted to the proof of Lemma 9.

###### Proof of Lemma 9.

Fix $s=\frac{8\cdot\rho\cdot\beta\cdot n}{\epsilon}$. For a parameter
$\alpha>0$, let $G^{\alpha}=(V,E,w_{\alpha})$ be the graph with the following
weight function for every $e\in E$,

$w^{\alpha}(e)=\begin{cases}\alpha&w(e)\geq\alpha\\\
w(e)&\frac{\alpha}{s^{2}}<w(e)<\alpha\\\ 0&\frac{\alpha}{s^{2}}\geq
w(e)\end{cases}\leavevmode\nobreak\ .$

That is we reduce all edge weights to be at most $\alpha$, and we nullified
(essentially contract) all edges of weight at most $\frac{\alpha}{s^{2}}$.
Note that as ${\cal F}$ is CURW, $G^{\alpha}\in{\cal F}$. We next analyze the
properties of $G^{\alpha}$.

######  Claim 2.

The graph $G^{\alpha}$ has the following properties:

  1. 1.

For every $x,y\in V$,
$d_{G^{\alpha}}(x,y)\leq\min\left\\{d_{G}(x,y),n\cdot\alpha\right\\}$.

  2. 2.

For every $x,y\in X$ such that $d_{G}(x,y)\in[\frac{\alpha}{s},\alpha]$,
$d_{G^{\alpha}}(x,y)\geq(1-\frac{n}{s})\cdot d_{G}(x,y)$.

  3. 3.

The induced shortest path metric has aspect ratio $n\cdot s^{2}$.

###### Proof.

(1). The edge weights only decreased, so clearly $d_{G^{\alpha}}(x,y)\leq
d_{G}(x,y)$. In addition, the shortest path from $x$ to $y$ in $G^{\alpha}$
consist of at most $n-1$ edges, all of weight at most $\alpha$, so it has
weight at most $n\cdot\alpha$. (2). Consider a pair $x,y$ such that
$d_{G}(x,y)\in[\frac{\alpha}{s},\alpha)$. Let $P$ be the shortest path from
$x$ to $y$ in $G^{\alpha}$. As $d_{G}(x,y)<\alpha$, we can assume that $P$
does not contain any edges of weight at least $\alpha$. It holds that

$d_{G^{\alpha}}(x,y)=w^{\alpha}(P)>w(P)-n\cdot\frac{\alpha}{s^{2}}\geq
d_{G}(x,y)-\frac{n}{s}\cdot d_{G}(x,y)\leavevmode\nobreak\ .$ (4)

(3). Recall that our definition of aspect ratio ignores $0$ distances:
$\Phi(G)=\frac{\max_{u,v\in V}d_{G}(u,v)}{\min_{u,v\in V\leavevmode\nobreak\
\rm{s.t.\leavevmode\nobreak\ }d_{\footnotesize G}(u,v)>0}d_{G}(u,v)}$ (see
Section 2). It follows that the minimal distance in $G^{\alpha}$ is
$\frac{\alpha}{s^{2}}$, and hence by point (1), the aspect ratio is bounded by
$\frac{n\cdot\alpha}{\frac{\alpha}{s^{2}}}=n\cdot s^{2}$. ∎

Let $\alpha_{i}=\Phi\cdot s^{-i}$. For every $i\geq 0$, construct an embedding
$f_{i}:X\rightarrow\ell_{\infty}$ w.r.t. $d_{G^{\alpha_{i}}}$ with expansion
$\rho$ and contraction $\beta$ and dimension $\varphi(n,n\cdot
s^{2},\rho,\beta)$. We will then reuse coordinates such that all the
embeddings $\left\\{f_{3i}\right\\}_{i\geq 0}$ all use the same coordinates.
Similarly for $\left\\{f_{3i+1}\right\\}_{i\geq 0}$ and
$\left\\{f_{3i+2}\right\\}_{i\geq 0}$. We will denote these embeddings by
$g_{0},g_{1},g_{2}$ respectively. This finishes the definition of our
embedding $f$. Clearly the overall number of coordinates is bounded by
$3\cdot\varphi(n,n\cdot
s^{2},\rho,\beta)=3\cdot\varphi(n,\left(\frac{8\cdot\rho\cdot\beta}{\epsilon}\right)^{2}\cdot
n^{3},\rho,\beta)$. Next we bound expansion and contraction (see Figure 2 for
illustration).

Figure 2: Illustration of the contraction and expansion proof in Lemma 9.

Consider $x,y\in X$, and assume w.l.o.g. that there is $i$ such that
$\alpha_{3i+1}<d_{G}(x,y)\leq\alpha_{3i}$ (the other cases is where there is
an $i$ such that either $\alpha_{3i+2}<d_{G}(x,y)\leq\alpha_{3i+1}$ or
$\alpha_{3i+3}<d_{G}(x,y)\leq\alpha_{3i+2}$ are treated symmetrically). For
every $j\leq 3i-2$ (if any), it holds that
$d_{G}(x,y)\leq\alpha_{3i}=\alpha_{j}\cdot s^{j-3i}\leq\alpha_{j}\cdot
s^{-2}$. Hence $d_{G^{\alpha_{j}}}(x,y)=0$, which implies
$\|f_{j}(x)-f_{j}(y)\|_{\infty}=0$. For every $j\geq 3i+2$,

$d_{G^{\alpha_{j}}}(x,y)\leq n\cdot\alpha_{j}=n\cdot
s^{(3i+1)-j}\cdot\alpha_{3i+1}\leq n\cdot s^{(3i+1)-j}\cdot
d_{G}(x,y)\leavevmode\nobreak\ .$

We conclude

$\displaystyle\|g_{0}(x)-g_{0}(y)\|_{\infty}$ $\displaystyle=\|\sum_{q\geq
0}f_{3q}(x)-\sum_{q\geq 0}f_{3q}(y)\|_{\infty}$
$\displaystyle\leq\|f_{3i}(x)-f_{3i}(y)\|_{\infty}+\sum_{q\geq
i+1}\|f_{3q}(x)-f_{3q}(y)\|_{\infty}$ $\displaystyle\leq\rho\cdot
d_{G}(x,y)+\rho\cdot\sum_{q\geq i+1}n\cdot s^{(3i+1)-3q}\cdot d_{G}(x,y)$
$\displaystyle=\rho\cdot
d_{G}(x,y)+\rho\cdot\frac{n}{s^{2}}\cdot\frac{1}{1-s^{-3}}\cdot
d_{G}(x,y)<\left(1+\frac{2n}{s^{2}}\right)\cdot\rho\cdot
d_{G}(x,y)\leavevmode\nobreak\ .$
$\displaystyle\|g_{1}(x)-g_{1}(y)\|_{\infty}$
$\displaystyle\leq\|f_{3i+1}(x)-f_{3i+1}(y)\|_{\infty}+\sum_{q\geq
i+1}\|f_{3q+1}(x)-f_{3q+1}(y)\|_{\infty}$ $\displaystyle\leq\rho\cdot
d_{G}(x,y)+\rho\cdot\sum_{q\geq i+1}n\cdot s^{(3i+1)-(3q+1)}\cdot d_{G}(x,y)$
$\displaystyle=\left(1+\frac{n}{s^{3}}\cdot\frac{1}{1-s^{-3}}\right)\cdot\rho\cdot
d_{G}(x,y)\leq\left(1+\frac{2n}{s^{3}}\right)\cdot\rho\cdot d_{G}(x,y)$

$\displaystyle\|g_{2}(x)-g_{2}(y)\|_{\infty}$
$\displaystyle\leq\|f_{3i-1}(x)-f_{3i-1}(y)\|_{\infty}+\sum_{q\geq
i}\|f_{3q+2}(x)-f_{3q+2}(y)\|_{\infty}$ $\displaystyle\leq\rho\cdot
d_{G}(x,y)+\rho\cdot\sum_{q\geq i}n\cdot s^{(3i+1)-(3q+2)}\cdot d_{G}(x,y)$
$\displaystyle=\left(1+\frac{n}{s}\cdot\frac{1}{1-s^{-3}}\right)\cdot\rho\cdot
d_{G}(x,y)\leq\left(1+\frac{2n}{s}\right)\cdot\rho\cdot d_{G}(x,y)$

From the other hand, according to 2,
$d_{G^{\alpha_{3i}}}(x,y)\geq(1-\frac{n}{s})\cdot d_{G}(x,y)$. It holds that

$\displaystyle\|g_{0}(x)-g_{0}(y)\|_{\infty}$
$\displaystyle\geq\|f_{3i}(x)-f_{3i}(y)\|_{\infty}-\sum_{q\geq
i+1}\|f_{3q}(x)-f_{3q}(y)\|_{\infty}$ $\displaystyle\geq\frac{1}{\beta}\cdot
d_{G^{\alpha_{3i}}}(x,y)-\rho\cdot\sum_{q\geq i+1}n\cdot s^{(3i+1)-3q}\cdot
d_{G}(x,y)$ $\displaystyle=\frac{1}{\beta}\cdot(1-\frac{n}{s})\cdot
d_{G}(x,y)-\rho\cdot\frac{n}{s^{2}}\cdot\frac{1}{1-s^{-3}}\cdot d_{G}(x,y)$
$\displaystyle>\left(1-\frac{n}{s}-\rho\cdot\beta\cdot\frac{2n}{s^{2}}\right)\cdot\frac{1}{\beta}\cdot
d_{G}(x,y)\leavevmode\nobreak\ .$

As $\|f(x)-f(y)\|_{\infty}=\max_{j\in{0,1,2}}\|g_{j}(x)-g_{j}(y)\|_{\infty}$,
and according to our choice of $s$ we conclude that

$\displaystyle\|f(x)-f(y)\|_{\infty}$
$\displaystyle\leq\left(1+\frac{2n}{s}\right)\cdot\rho\cdot
d_{G}(x,y)\leq\left(1+\epsilon\right)\cdot\rho\cdot d_{G}(x,y)$
$\displaystyle\|f(x)-f(y)\|_{\infty}$
$\displaystyle\geq\left(1-\frac{n}{s}-\rho\cdot\beta\cdot\frac{2n}{s^{2}}\right)\cdot\frac{1}{\beta}\cdot
d_{G}(x,y)\geq\frac{1}{(1+\epsilon)\cdot\beta}\cdot d_{G}(x,y)$

∎

###  5.4 Improved distortion for minor free graphs

This subsection is devoted to proving Theorem 2, which improves the distortion
of the $\ell_{\infty}$ embedding of $K_{r}$-minor free graphs to
$3+\varepsilon$. The following is our key lemma, which is parallel to Lemma 8.

######  Lemma 10.

Fix $\varepsilon\in(0,\frac{1}{2})$ and $\Phi\geq 1$, and consider a weighted
$n$ vertex $K_{r}$-minor free graph $G=(V,E,w)$ such that all the pairwise
distances in $X$ are between $1$ and $\Phi$. Then $G$ can be embedded into
$\ell_{\infty}^{O(\varepsilon)^{r+1}\cdot\log\frac{1}{\varepsilon}\cdot\log(n\Phi)}$
with distortion $3+\varepsilon$.

###### Proof.

The embedding is essentially the same as in the construction of Lemma 8, and
the main changes are in the analysis. Roughly speaking, first we subdivide all
the edges of our graph, this will reduce the expansion from $2$ to
$1+\varepsilon$. Then we will dive into the specific details of the sparse
cover, and show that the contraction is only $3+O(\varepsilon)$.

Consider our $K_{r}$ minor free graph $G=(V,E,w)$. Let
$\tilde{G}=(\tilde{V},\tilde{E},\tilde{w})$ be a graph, where we replace every
edge $e=(v,u)\in E$ with a path consisting of $\frac{1}{\varepsilon}$ edges of
length $\varepsilon\cdot w(e)$. Note that all the pairwise distances between
original vertices remained exactly the same, and that $\tilde{G}$ is still
$K_{r}$-minor free, thus it also admits the sparse covers from Theorem 1. We
will embed only the original vertices $V$ into $\ell_{\infty}$, however the
partitions will be created w.r.t. $\tilde{G}$. This small change will improve
our upper bound in Lemma 7 from expansion $2$ to expansion $1+\varepsilon$.
Indeed, consider a pair $x,y\in V$, and recall the proof of Lemma 7. The proof
is by induction on $|V|$. The case where $x,y$ belong to the same cluster in
$\mathcal{P}_{k}$ is treated in the same way (as eq. 1 guarantees
$\left|(f(x))_{q}-(f(y))_{q}\right|\leq d_{G}(x,y)$ ). In the second case, $x$
and $y$ correspond so different clusters, where according to eq. 2,
$\left|(f(x))_{q}-(f(y))_{q}\right|\leq d_{\tilde{G}}(x,\tilde{V}\setminus
Y_{j})+d_{\tilde{G}}(y,\tilde{V}\setminus Y_{j^{\prime}})$ where $x\in Y_{j}$,
$y\in Y_{j^{\prime}}$, and $Y_{j}\cap Y_{j^{\prime}}=\emptyset$ are disjoint.
In $\tilde{G}$, the shortest path $P$ from $x$ to $y$ in $\tilde{G}$ must go
though $x^{\prime}\notin Y_{j}$, and $y^{\prime}\notin Y_{j^{\prime}}$ such
that $x^{\prime},y^{\prime}$ are consecutive vertices of a subdivided edge $e$
(see two illustrations bellow). In particular,
$d_{\tilde{G}}(x^{\prime},y^{\prime})=\varepsilon\cdot
w(e)\leq\varepsilon\cdot w(P)$. It follows that

$\displaystyle\left|(f(x))_{q}-(f(y))_{q}\right|$ $\displaystyle\leq
d_{\tilde{G}}(x,\tilde{V}\setminus Y_{j})+d_{\tilde{G}}(y,\tilde{V}\setminus
Y_{j^{\prime}})$ $\displaystyle\leq
d_{\tilde{G}}(x,x^{\prime})+d_{\tilde{G}}(y,y^{\prime})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
d_{\tilde{G}}(x,y)+d_{\tilde{G}}(x^{\prime},y^{\prime})\leavevmode\nobreak\
<\leavevmode\nobreak\ (1+\varepsilon)\cdot
d_{\tilde{G}}(x,y)\leavevmode\nobreak\ .$

It follows that the embedding produced by Theorem 6 has expansion
$1+\varepsilon$.

Next we improve the contraction guarantee. The basis of our construction is
the $\left(4\cdot(1+\varepsilon),O(\frac{1}{\varepsilon})^{r}\right)$-SPCS of
Theorem 1. We begin by observing that the padding guarantee in Theorem 5 is
somewhat stronger that what is required by the definition of SPCS. Indeed, we
follow the construction (and notation) of Theorem 5. Note that here
$\gamma=\frac{\Delta}{r}$, and for the construction of our strong
$\left(4\cdot(1+\varepsilon),O(\frac{1}{\varepsilon})^{r}\right)$-SPCS we used
$q=\frac{2r}{\varepsilon}$. In Lemmas 3 and 4 it was shown that the cluster
satisfying a point $x$ consist of a ball
$B_{G[\hat{\eta}]}(v,2\Delta+q\cdot\gamma)=B_{G[\hat{\eta}]}(v,(1+\varepsilon)\cdot\frac{2\Delta}{\varepsilon})$
where
$B_{G}(x,\frac{q\cdot\gamma}{2})=B_{G}(x,\frac{\Delta}{\varepsilon})\subseteq\hat{\eta}$
and $d_{G[\hat{\eta}]}(v,x)\leq
2\Delta+\frac{q\cdot\gamma}{2}=(1+2\varepsilon)\cdot\frac{\Delta}{\varepsilon}$.
Note that the diameter of the corresponding partition is
$(1+\varepsilon)\cdot\frac{4\Delta}{\varepsilon}$, and that
$\partial_{\mathcal{P}}(x)\geq\frac{\Delta}{\varepsilon}$. In other words, fix
$\Psi=\frac{4\Delta}{\varepsilon}$, then there is a cluster
$C_{x}\in\mathcal{P}$ such that $B_{G}(x,\Psi)\subseteq C\subseteq
B_{G}(v,(1+\varepsilon)\cdot 2\Psi)$, and
$d_{G}(x,v)\leq(1+2\varepsilon)\cdot\Psi$. Next, in Lemma 6, the partition
$\mathcal{P}$ was slightly changed to into $\tilde{\mathcal{P}}$ in order to
become a part of an hierarchy. In particular, it holds that there is a cluster
$\tilde{C}\in\tilde{\mathcal{P}}$ such that
$B_{G}(x,\frac{\Psi}{1+\varepsilon})\subseteq\tilde{C}\subseteq
B_{G}(v,(1+\varepsilon)^{2}\cdot 2\Psi)$. Furthermore, for a vertex $y\in V$
such that $d_{G}(x,y)>(3+8\varepsilon)\cdot\Psi$ it holds that

$d_{G}(v,y)\geq
d_{G}(x,y)-d_{G}(v,x)>(3+8\varepsilon)\cdot\Psi-(1+2\varepsilon)\cdot\Psi=(1+3\varepsilon)\cdot
2\Psi>(1+\varepsilon)^{2}\cdot 2\Psi\leavevmode\nobreak\ ,$

and thus $y$ does not belong to $\tilde{C}$.

Fix a pair $x,y\in V$. In Lemma 8 we constructed partition for every possible
scale. Consider the scale $(i,q)$ such that
$(1+\epsilon)^{q}(\frac{4\beta}{\epsilon})^{i}<\frac{4}{3+8\cdot\varepsilon}\cdot
d_{G}(x,y)\leq(1+\epsilon)^{q+1}(\frac{4\beta}{\epsilon})^{i}$. Fix
$\Psi=\frac{1}{4}\cdot(1+\epsilon)^{q}(\frac{4\beta}{\epsilon})^{i}$.
Following the discussion above, for this scale, there was some partition
$\mathcal{P}_{i}^{j,q}$ with diameter at most $(1+\varepsilon)^{2}\cdot 4\Psi$
such that the ball $B_{G}(x,\frac{\Psi}{1+\varepsilon})$ was contained in a
single cluster, and every vertex at distance greater than
$(3+8\varepsilon)\cdot\Psi$ from $x$ belonged to a different cluster. In
particular, as
$d_{G}(x,y)>\frac{3+8\cdot\varepsilon}{4}\cdot(1+\epsilon)^{q}(\frac{4\beta}{\epsilon})^{i}=(3+8\cdot\varepsilon)\cdot\Psi$,
$y$ belongs to a different cluster. Using Lemma 7 we conclude

$\displaystyle\left\|f(x)-f(y)\right\|_{\infty}$
$\displaystyle\geq\left\|f_{j,q}(x)-f_{j,q}(y)\right\|_{\infty}\geq\partial_{\mathcal{P}_{i}^{j,q}}(x)+\partial_{\mathcal{P}_{i}^{j,q}}(y)$
$\displaystyle\geq\frac{\Psi}{1+\varepsilon}=\frac{(3+8\varepsilon)\cdot\Psi}{(1+\varepsilon)\cdot(3+8\varepsilon)}>\frac{d_{G}(x,y)}{3\cdot(1+O(\varepsilon))}\leavevmode\nobreak\
.$

Thus we indeed obtained distortion $3+O(\varepsilon)$ as promised. Similarly
to Lemma 8, the overall dimension is bounded by
$O\left(\frac{\tau}{\varepsilon}\cdot\log\frac{\beta}{\varepsilon}\cdot\log(n\Phi)\right)=O(\frac{1}{\varepsilon})^{r+1}\cdot\log\frac{1}{\varepsilon}\cdot\log(n\Phi)$.
∎

Finally, we apply Lemma 9 on Lemma 10 to get Theorem 2, restated bellow for
convenience. See 2

##  6 From sparse covers to padded decompositions

This section is devoted to proving our meta Theorem 3 (restated bellow for
convenience) that reduces sparse covers into padded decomposition. As a
corollary, we recover the state of the art padded decomposition for $K_{r}$
minor-free graphs (Corollary 2) via a much simpler proof (compared with
[AGG+19]). More importantly, every further improvement on sparse covers will
now immediately lead to an improved padded decomposition! See 3

###### Proof.

Given a cover $\mathcal{C}$, we will. sample a partition $\mathcal{P}$ with
the desired padding properties. To avoid confusion, the sets of $\mathcal{C}$
(resp. $\mathcal{P}$) will be called $\mathcal{C}$-clusters (resp.
$\mathcal{P}$-clusters). Our decomposition is morally [MPX13]-based, and
closely follows [Fil19a]. Filtser [Fil19a] proved that the existence of a
“sparse net” implies padded decomposition. Specifically, if there is a net $N$
such that every vertex $v$ has a net point at distance at most
$d_{G}(v,N)\leq\Delta$, and the number of net points in the ball
$B_{G}(v,3\Delta)$ is at most $\tau$, then $G$ admits a strong
$\left(O(\ln\tau),\frac{1}{16},4\Delta\right)$-padded decomposition. One can
notice that by taking balls of radius $2\Delta$ around the sparse net $N$, we
will get a $(\frac{1}{4},\tau,4\Delta)$-sparse cover, and thus our Theorem 3
is in a sense generalization of [Fil19a] to arbitrary sparse covers (alas only
with a weak diameter guarantee).

For a $\mathcal{C}$-cluster $C\subseteq V$, and a vertex $v\in V$. Denote by
$\partial_{C}(v)=d_{G}(v,V\setminus C)$ the distance between $v$ and the
boundary of the $\mathcal{C}$-cluster $C$. Note that if $v\notin C$,
$\partial_{C}(v)=0$, while $B_{G}(v,r)\subseteq C$ implies
$\partial_{C}(v)>r$. Furthermore, for every pair of vertices $u,v\in V$,
$|\partial_{C}(v)-\partial_{C}(v)|=\left|d_{G}(v,V\setminus
C)-d_{G}(u,V\setminus C)\right|\leq d_{G}(u,v)$.

To create a padded decompositions, following previous works, we will use
truncated exponential distribution. That is, exponential distribution
conditioned on the event that the outcome lays in a certain interval. The
_$[0,1]$ -truncated exponential distribution_ with parameter $\lambda$ is
denoted by $\mathsf{Texp}(\lambda)$, the density function is then
$g(y)=\frac{\lambda\cdot e^{-\lambda\cdot y}}{1-e^{-\lambda}}$, for
$y\in[0,1]$.

Consider a $(\beta,s,\Delta)$-sparse cover $\mathcal{C}$. For every
$\mathcal{C}$-cluster $C$ we sample $\delta_{C}\sim\mathsf{Texp}(\lambda)$
using truncated exponential distribution with parameter $\lambda=2+2\ln s$.
For a $\mathcal{C}$-cluster $C$, we define a function
$f_{C}:V\rightarrow\mathbb{R}_{\geq 0}$, as follows:
$f_{C}(v)=\delta_{C}\cdot\frac{\Delta}{\beta}+\partial_{C}(v)$. We next create
a partition $\mathcal{P}=\\{P_{C}\\}_{C\in\mathcal{C}}$ where each vertex
$v\in V$ joins the $\mathcal{P}$-cluster $P_{C}$ associated with the
$\mathcal{C}$-cluster $C$ that maximizes $f_{C}(v)$.

Fix a vertex $v\in V$. As $\mathcal{C}$ is a sparse cover, there is some
$\mathcal{C}$-cluster $C_{v}\in\mathcal{C}$ such that
$B_{G}(v,\frac{\Delta}{\beta})\subseteq C_{v}$, implying
$f_{C_{v}}(v)>\frac{\Delta}{\beta}$. From the other hand, for every
$\mathcal{C}$-cluster $C$ which does not contain $v$, it holds that
$f_{C}(v)\leq\delta_{C}\cdot\frac{\Delta}{\beta}+0\leq\frac{\Delta}{\beta}$.
It follows that $f_{C}(v)<f_{C_{v}}(v)$. Hence $v$ can only join a
$\mathcal{P}$-cluster in $P_{C}$ that associated with a $\mathcal{C}$-cluster
$C$ that contains it. In particular, for every $C\in\mathcal{C}$,
$P_{C}\subseteq C$. As every $\mathcal{C}$-cluster has diameter at most
$\Delta$, we conclude that $\mathcal{P}$ has diameter at most $\Delta$. Note
that the diameter guarantee in $\mathcal{P}$ is weak, regardless of the
diameter guarantee in $\mathcal{C}$.

######  Claim 3.

Consider a vertex $v$, and let $C_{(1)},C_{(2)},\dots$ be an ordering of the
$\mathcal{C}$-clusters w.r.t. the values $\\{f_{C}(v)\\}_{C\in\mathcal{C}}$.
That is $f_{C_{(1)}}(v)\geq f_{C_{(2)}}(v)\geq\dots$ . Set
$\Upsilon=f_{C_{(1)}}(v)-f_{C_{(2)}}(v)$. Then for every
$r<\frac{\Upsilon}{2}$, it holds that $B_{G}(v,r)\subseteq P_{C_{(1)}}$.

###### Proof.

Fix $r<\frac{\Upsilon}{2}$. For every $u\in B_{G}(v,r)$, and every center
$C\neq C_{(1)}$ it holds that,

$\displaystyle f_{C_{(1)}}(u)$
$\displaystyle=\delta_{C_{(1)}}\cdot\frac{\Delta}{\beta}+\partial_{C_{(1)}}(u)\leavevmode\nobreak\
>\leavevmode\nobreak\
\delta_{C_{(1)}}\cdot\frac{\Delta}{\beta}+\partial_{C_{(1)}}(v)-d_{G}(u,v)$
$\displaystyle=f_{C_{(1)}}(v)-d_{G}(u,v)\leavevmode\nobreak\
\geq\leavevmode\nobreak\ f_{C}(v)+\Upsilon-d_{G}(u,v)$
$\displaystyle=\delta_{C}\cdot\frac{\Delta}{\beta}+\partial_{C}(v)+\Upsilon-
d_{G}(u,v)$
$\displaystyle\geq\delta_{C}\cdot\frac{\Delta}{\beta}+\partial_{C}(u)+\Upsilon-2\cdot
d_{G}(u,v)\leavevmode\nobreak\ >\leavevmode\nobreak\
f_{C}(u)\leavevmode\nobreak\ .$

In particular, $u\in C_{(1)}$, and thus $B_{G}(v,r)\subseteq P_{C_{(1)}}$ as
required. ∎

Next we analyzing the padding probability. Consider some vertex $v\in V$, and
parameter $\gamma\leq\frac{1}{4}$. We will first argue that the ball
$B=B_{G}(v,\gamma\cdot\frac{\Delta}{\beta})$ is fully contained in a single
$\mathcal{P}$-cluster with probability at least $e^{-4\gamma\cdot\lambda}$.
The theorem will then follow due to scaling. Let
$\mathcal{C}=\\{C_{1},C_{2},\dots\\}$ by an arbitrarily ordering of the
$\mathcal{C}$-clusters. Denote by $\mathcal{F}_{i}$ the event that $v$ joins
the cluster associated with $C_{i}$, i.e. $v\in P_{C_{i}}$. Denote by
$\mathcal{Q}_{i}$ the event that $v\in P_{C_{i}}$, but not all of the vertices
in $B$ joined $P_{C_{i}}$, that is $v\in P_{C_{i}}\cap B\neq B$. Let
$\mathcal{C}_{v}\subseteq\mathcal{C}$ be the clusters containing $v$. Note
that for every $C_{i}\notin\mathcal{C}_{v}$,
$\Pr[\mathcal{F}_{i}]=\Pr[\mathcal{Q}_{i}]=0$. To prove our assertion, it is
enough to show that $\Pr\left[\cup_{i}\mathcal{Q}_{i}\right]\leq
1-e^{-4\gamma\cdot\lambda}$. Set $\alpha=e^{-2\gamma\cdot\lambda}$.

######  Claim 4.

For every $i$,
$\Pr\left[\mathcal{Q}_{i}\right]\leq\left(1-\alpha\right)\left(\Pr\left[\mathcal{F}_{i}\right]+\frac{1}{e^{\lambda}-1}\right)$.

###### Proof.

As the order in $\mathcal{C}$ is arbitrary, assume w.l.o.g. that
$i=|\mathcal{C}|$ and denote $C=C_{|\mathcal{C}|}$,
$\mathcal{Q}=\mathcal{Q}_{i}$, $\mathcal{F}=\mathcal{F}_{i}$, and
$\delta=\delta_{C_{i}}$. Let $X\in[0,1]^{|\mathcal{C}|-1}$ be the vector where
the $j$’th coordinate equals $\delta_{x_{j}}$. Set
$\rho_{X}=\max\left\\{0,\frac{\beta}{\Delta}\cdot\left(\max_{C^{\prime}\neq
C}\left\\{\delta_{C^{\prime}}\cdot\frac{\Delta}{\beta}+\partial_{C^{\prime}}(v)\right\\}-\partial_{C}(v)\right)\right\\}$.
Note that $\rho_{X}$ is the minimal value of $\delta$ such that if
$\delta>\rho_{X}$, then $C$ has the maximal value $f_{C}(v)$, and therefore
$v$ will join $P_{C}$. Note that it is possible that $\rho_{X}>1$.
Conditioning on all the other samples having values $X$, and assuming first
that $\rho_{X}\leq 1$, it holds that

$\Pr\left[\mathcal{F}\mid
X\right]=\Pr\left[\delta>\rho_{X}\right]=\int_{\rho_{X}}^{1}\frac{\lambda\cdot
e^{-\lambda
y}}{1-e^{-\lambda}}dy=\frac{e^{-\rho_{X}\cdot\lambda}-e^{-\lambda}}{1-e^{-\lambda}}\leavevmode\nobreak\
.$

If $\delta>\rho_{X}+2\gamma$, then

$\displaystyle f_{C}(v)$
$\displaystyle=\delta_{C}\cdot\frac{\Delta}{\beta}+\partial_{C}(v)>(\rho_{X}+2\gamma)\cdot\frac{\Delta}{\beta}+\partial_{C}(v)$
$\displaystyle\geq 2\gamma\cdot\frac{\Delta}{\beta}+\max_{C^{\prime}\neq
C}\left\\{\delta_{C^{\prime}}\cdot\frac{\Delta}{\beta}+\partial_{C^{\prime}}(u)\right\\}=2\gamma\cdot\frac{\Delta}{\beta}+\max_{C^{\prime}\neq
C}f_{C^{\prime}}(v)\leavevmode\nobreak\ .$

In particular, by 3 the ball $B$ will be contained in $C$. We conclude

$\displaystyle\Pr\left[\mathcal{Q}\mid X\right]$
$\displaystyle\leq\Pr\left[\rho_{X}\leq\delta\leq\rho_{X}+2\gamma\right]$
$\displaystyle=\int_{\rho_{X}}^{\max\left\\{1,\rho_{X}+2\gamma\right\\}}\frac{\lambda\cdot
e^{-\lambda y}}{1-e^{-\lambda}}dy$
$\displaystyle\leq\frac{e^{-\rho_{X}\cdot\lambda}-e^{-\left(\rho_{X}+2\gamma\right)\cdot\lambda}}{1-e^{-\lambda}}$
$\displaystyle=\left(1-e^{-2\gamma\cdot\lambda}\right)\cdot\frac{e^{-\rho_{X}\cdot\lambda}}{1-e^{-\lambda}}$
$\displaystyle=\left(1-\alpha\right)\cdot\left(\Pr\left[\mathcal{F}\mid
X\right]+\frac{1}{e^{\lambda}-1}\right)\leavevmode\nobreak\ .$

Note that if $\rho_{X}>1$ then $\Pr\left[\mathcal{Q}\mid
X\right]=0\leq\left(1-\alpha\right)\cdot\left(\Pr\left[\mathcal{F}\mid
X\right]+\frac{1}{e^{\lambda}-1}\right)$ as well. Denote by $h$ the density
function of the distribution over all possible values of $X$. Using the law of
total probability, we can bound the probability of $\mathcal{Q}$:

$\displaystyle\Pr\left[\mathcal{Q}\right]$
$\displaystyle=\int_{X}\Pr\left[\mathcal{Q}\mid X\right]\cdot
h(X)\leavevmode\nobreak\ dX$
$\displaystyle\leq\left(1-\alpha\right)\cdot\int_{X}\left(\Pr\left[\mathcal{F}\mid
X\right]+\frac{1}{e^{\lambda}-1}\right)\cdot h(X)\leavevmode\nobreak\ dX$
$\displaystyle=\left(1-\alpha\right)\cdot\left(\Pr\left[\mathcal{F}\right]+\frac{1}{e^{\lambda}-1}\right)$

∎

Next, we bound the probability that the ball $B$ is cut.

$\displaystyle\Pr\left[\cup_{i}\mathcal{Q}_{i}\right]=\sum_{C_{i}\in\mathcal{C}_{v}}\Pr\left[\mathcal{Q}_{i}\right]$
$\displaystyle\leq\left(1-\alpha\right)\cdot\sum_{C_{i}\in\mathcal{C}_{v}}\left(\Pr\left[\mathcal{F}_{i}\right]+\frac{1}{e^{\lambda}-1}\right)$
$\displaystyle\leq\left(1-e^{-2\gamma\cdot\lambda}\right)\cdot\left(1+\frac{s}{e^{\lambda}-1}\right)$
$\displaystyle\leq\left(1-e^{-2\gamma\cdot\lambda}\right)\cdot\left(1+e^{-2\gamma\cdot\lambda}\right)=1-e^{-4\gamma\cdot\lambda}\leavevmode\nobreak\
,$

where the last inequality follows as
$e^{-2\gamma\lambda}=\frac{e^{-2\gamma\lambda}\left(e^{\lambda}-1\right)}{e^{\lambda}-1}\geq\frac{e^{-2\gamma\lambda}\cdot
e^{\lambda-1}}{e^{\lambda}-1}\geq\frac{e^{\frac{\lambda}{2}-1}}{e^{\lambda}-1}=\frac{s}{e^{\lambda}-1}$,
where we used that $\gamma\in(0,\frac{1}{4}]$, and $\lambda=2+2\ln s$.

We conclude that our distribution indeed produces a weak
$(4\beta\cdot\lambda,\frac{1}{4\beta},\Delta)$-padded decomposition. Indeed,
we already established that the diameter is at most $\Delta$. Next, fix
$\gamma\leq\frac{1}{4\beta}$, and $v\in V$. Denote by $P(v)$ the
$\mathcal{P}$-cluster containing $v$. Then

$\Pr_{\mathcal{P}}\left[B_{G}(v,\gamma\cdot\Delta)\subseteq
P(v)\right]=\Pr_{\mathcal{P}}\left[B_{G}(v,\beta\cdot\gamma\cdot\frac{\Delta}{\beta})\subseteq
P(v)\right]\geq e^{-4\cdot\beta\cdot\gamma\cdot\lambda}\leavevmode\nobreak\ ,$

where we used section 6 w.r.t. $\beta\cdot\gamma$, and the fact that
$\beta\cdot\gamma\leq\frac{1}{4}$. The theorem now follows.

∎

##  7 Further applications

###  7.1 Sparse Partitions

Given a weighted graph $G=(V,E,w)$, a weak/strong
$(\alpha,\tau,\Delta)$-sparse partition is a partition $\mathcal{C}$ of $V$
such that:

  * •

Low Diameter: $\forall C\in\mathcal{C}$, the $C$ has a weak/strong diameter at
most $\Delta$;

  * •

Ball Preservation: $\forall v\in V$, the ball $B_{G}(v,\frac{\Delta}{\alpha})$
intersects at most $\tau$ clusters from $\mathcal{C}$.

We say that the graph $G=(V,E,w)$ admits a weak/strong $(\alpha,\tau)$-sparse
partition scheme if for every $\Delta>0$, $G$ admits a weak/strong
$(\alpha,\tau,\Delta)$-sparse partition.

Sparse partition have been used to construct universal TSP and universal
Steiner tree [JLN+05, BDR+12, Fil20a, BCF+23] (see Section 7.2). Recently they
been also used to obtain an $O(\frac{d}{\log d})$ approximation for the
facility location problem in $\mathbb{R}^{d}$ in the geometric streaming model
[CFJ+22].

Jia et al. [JLN+05] implicitly proved (see [Fil20a] for an explicit proof)
that if a space admits a weak $(\beta,s)$-sparse cover scheme, then it admitsa
weak $(\beta,s)$-sparse partition scheme. Using Theorem 1 we conclude:

######  Corollary 3.

Every $K_{r}$-minor free graph $G$ admits a weak
$\left(O(r),O(r^{2})\right)$-sparse partition scheme. In addition, for
$\varepsilon\in(0,\frac{1}{2})$, $G$ admits a weak
$\left(4+\varepsilon,O(\frac{1}{\varepsilon})^{r}\right)$-sparse partition.

The previous state of the art follows directly from the previously best know
weak sparse cover scheme, that is weak $\left(O(r^{2}),O(2^{r})\right)$-sparse
partition scheme (see [Fil20a], and also [KPR93, FT03]).

###  7.2 Universal TSP and Universal Steiner Tree

Consider a postman providing post service for a set $X$ of clients with $n$
different locations (with distance measure $d_{X}$). Each morning the postman
receives a subset $S\subseteq X$ of the required deliveries for the day. In
order to minimize the total tour length, one solution may be to compute each
morning an (approximation of an) optimal TSP tour for the set $S$. An
alternative solution will be to compute a _Universal TSP_ (UTSP) tour. This is
a universal tour $R$ containing all the points $X$. Given a subset $S$, $R(S)$
is the tour visiting all the points in $S$ w.r.t. the order induced by $R$.
Given a tour $T$ denote its length by $|T|$. The _stretch_ of $R$ is the
maximum ratio among all subsets $S\subseteq X$ between the length of $R(S)$
and the length of the optimal TSP tour on $S$, $\max_{S\subseteq
X}\frac{|R(S)|}{|\mbox{Opt}(S)|}$.

A closely related problem to UTSP is the _Universal Steiner tree_ (UST).
Consider the problem of designing a network that allows a server to broadcast
a message to a single set of clients. If sending a message over a link incurs
some cost then designing the best broadcast network is classically modeled as
the Steiner tree problem [Hwa76]. However, if the server have to solve this
problem repeatedly, with different client sets, it is desirable to construct a
single network that will optimize the cost of the broadcast for every possible
subset of clients.

Given a metric space $(X,d_{X})$ and root $r\in X$, a $\rho$-approximate
universal Steiner tree (UST) is a weighted tree $T$ over $X$ such that for
every $S\subseteq X$ containing $r$, we have

$\displaystyle w(T\\{S\\})\leq\rho\cdot\text{OPT}_{S}$

where $T\\{S\\}\subseteq T$ is the minimal subtree of $T$ connecting $S$, and
$\text{OPT}_{S}$ is the minimum weight Steiner tree connecting $S$ in $X$. If
the tree $T$ is not required to be a subgraph of $G$, we will call the problem
metric UST.

Jia et al. [JLN+05] showed that for every $n$-point metric space that admits
weak $(\sigma,\tau)$-sparse partition scheme, there is a polynomial time
algorithm that given a root $\mbox{\rm rt}\in V$ computes a UTSP with stretch
$O(\tau\sigma^{2}\log_{\tau}n)$, and a metric UST with stretch
$O(\tau\sigma^{2}\log_{\tau}n)$. Using our Corollary 3, we conclude:

######  Corollary 4.

Consider an $n$-point $K_{r}$-minor free weighted graph $G=(V,E,w)$. Then $G$
admits a solution to both UTSP and metric UST with stretch
$O(\frac{r^{4}}{\log r})\cdot\log n$.

The previous state of the art had stretch $O(2^{r}\cdot r)\cdot\log n$, thus
we obtain an exponential improvement in the dependence on $r$. Interestingly,
there is an $\Omega(\frac{\log n}{\log\log n})$ lower bound for the UST
problem on the $n\times n$ grid, which is $K_{5}$-minor free, thus
essentially, in the context of $K_{r}$-minor free graphs, the dependence on
$r$ is the only parameter left to optimize.

It is important to note that the UST returned by [JLN+05] (and thus by
Corollary 4) is not a subgraph of $G$. The (non-metric) UST problem was also
studied and there is a similar reduction [BDR+12]. Formally, a strong
$(\tau,\sigma,\rho)$-sparse partition hierarchy is a set of laminar partitions
$\mathcal{P}_{1},\mathcal{P}_{2},\dots$, such that $\mathcal{P}_{i}$ refines
$\mathcal{P}_{i+1}$, and each $\mathcal{P}_{i}$ is a strong
$(\tau,\sigma,\rho^{i})$-sparse partition. Busch et al. [BDR+12] showed that
if a graph admits strong $(\tau,\sigma,\rho)$-sparse partition than there is a
subgraph solution to the UST problem with stretch
$O(\tau^{2}\cdot\sigma^{2}\cdot\rho\cdot\log n)$. This reduction was recently
used by Busch et al. [BCF+23] to obtain a solution for the UST problem on
general graphs with stretch $O(\log^{7}n)$. [BCF+23] also showed solution with
stretch $O(\log n)$ for graph with constant doubling dimension or pathwidth.
However, nothing better than general graphs is known for $K_{r}$-minor free
graphs, or even planar graphs. One reason being that even trees do no admit
better than $(\tilde{\Omega}(\log n),\tilde{\Omega}(\log n))$-strong sparse
partition scheme [Fil20b]. Improving the stretch factor for $K_{r}$-minor free
graphs is a fascinating open problem.

###  7.3 Oblivious Buy-at-Bulk

In the _buy-at-bulk_ problem we are given a weighted graph $G=(V,E,w)$ , the
goal is to satisfy a set of demands $A\subseteq{V\choose 2}$, by routing these
demands over the graph while minimizing the cost. In more details,
$\delta_{i}=(s_{i},t_{i})$ is a unit of demand that induces an unsplittable
unit of flow from source node $s_{i}\in V$ to a destination $t_{i}\in V$.
Given a set of demands $A=\\{\delta_{1},\delta_{2},\dots,\delta_{k}\\}$, a
valid solution is a set of paths $\mathcal{P}=\\{P_{1},\dots,P_{k}\\}$, where
$P_{i}$ is a path from $s_{i}$ to $t_{i}$. The paths can overlap. For an edge
$e\in E$, denote by $\varphi_{e}$ the number of paths in $\mathcal{P}$ that
use $e$. A function $f:\mathbb{N}\rightarrow\mathbb{R}_{\geq 0}$ is called
_canonical_ fusion function if it is (1) concave, (2) non-decreasing, (3)
$f(0)=0$, and (4) sub-additive (that is $\forall x,y\in\mathbb{N}$,
$f(x+y)\leq f(x)+f(y)$). In the buy-at-bulk problem we are given a canonical
fusion function $f$. The cost of a solution $\mathcal{P}$ is
$\operatorname{cost}(\mathcal{P})=\sum_{e\in E}f(\varphi_{e})\cdot w(e)$. The
goal is to find a valid solution of minimum cost. The canonical fusion
function provides the following intuition: there is a discount as you use more
and more of the same edge. So it is generally beneficial for the paths in
$\mathcal{P}$ to overlap. Note that the buy-at-bulk problem is NP-hard, as the
Steiner tree problem is a special case (where the canocical fusion function is
$f(0)=0$ and $f(i)=1$ for $i\geq 1$).

In the _oblivious buy-at-bulk_ problem we have to choose a collection of paths
$\mathcal{P}$ without knowing the demands. That is, for every possible demand
$\delta_{i}\in{V\choose 2}$, we have to add to $\mathcal{P}$ choose a path
$P(\delta_{i})$ between it’s endpoints. Then given a set of demands
$A\subseteq{V\choose 2}$, $\operatorname{cost}(\mathcal{P},A)=\sum_{e\in
E}f(\varphi_{e}(\mathcal{P},A))\cdot w(e)$, where
$\varphi_{e}(\mathcal{P},A)=\left|\\{P(\delta_{i})\mid e\in
P(\delta_{i})\leavevmode\nobreak\ \&\leavevmode\nobreak\ \delta_{i}\in
A\\}\right|$ is the number of paths associated with the demands in $A$ that
use $e$. The approximation ratio of $\mathcal{P}$, is the ratio between the
induced cost, to the optimal cost for the worst possible set of demands $A$:

${\rm Approximatio\leavevmode\nobreak\
ratio}(\mathcal{P})=\max_{A\subseteq{V\choose
2}}\frac{\operatorname{cost}(\mathcal{P},A)}{\mathrm{opt}(A)}\leavevmode\nobreak\
.$

Gupta et al. [GHR06] provided an algorithm achieving approximation ratio
$O(\log^{2}n)$. Interestingly, their algorithm is oblivious not only to the
demand pairs $A$, but also to the canonical fusion function $f$. A lower bound
of $\Omega(\log n)$ is known already for the case where the graph $G$ is
planar [IW91]. Later, Srinivasagopalan et al. [SBI11] improved the
approximation ratio for the case of planar graphs to $O(\log n)$. Their
solution is also oblivious to both demands and function. Srinivasagopalan et
al. [SBI11] left it as an explicit open problem to “obtain efficient solutions
to other related network topologies, such as minor-free graphs.” More than a
decade later, and compared with general graphs, nothing better for
$K_{r}$-minor free graphs is known.

Our contribution here is to answer the question from [SBI11] affirmatively.
Specifically, that every $K_{r}$-minor free graph admits a solution with
approximation ratio $\mathrm{poly}(r)\cdot\log n$. This is tight up to the
dependence on $r$.

Srinivasagopalan et al. [SBI11] implicitly proved that if a graph admits a
“colorable” strong sparse cover scheme, than it also admits an efficiently
computable solution with small approximation ratio for the oblivious buy-at-
bulk problem.

######  Definition 6.

Consider a strong $(\beta,s,\Delta)$-sparse cover $\mathcal{C}$ of
$G=(V,E,w)$. We say that cluster $C\in\mathcal{C}$ $\beta$-satisfies a vertex
$x\in V$ if the ball $B_{G}(x,\frac{\Delta}{\beta})\subseteq C$ is contained
in $C$. Two clusters $C_{1},C_{2}\in\mathcal{C}$ are neighbors if there is a
pair of vertices $x\in C_{1}$ and $y\in C_{2}$ at distance at most
$d_{G}(x,y)\leq\frac{\Delta}{\beta}$ such that $x,y$ are $\beta$-satisfied by
$X_{1},X_{2}$ respectively. A $k$-coloring is a function
$\chi:\mathcal{C}\rightarrow[k]$ such that no two neighboring clusters are
colored using the same color.

Srinivasagopalan et al. [SBI11] showed that the strong sparse cover of [BLT14]
for planar graphs is $18$-colorable. Note that given a strong
$(\beta,s,\Delta)$-sparse partition cover, it is clearly $s$-colorable.
Indeed, we can give all the clusters is each partition the same color. As the
clusters in each partitions are all disjoint, this is a valid coloring. We
conclude that our sparse covers from Theorem 1 are $O(r^{2})$-colorable.

Srinivasagopalan et al. [SBI11] showed that if a graph $G$ admits a strong
$(\beta,s)$-sparse cover scheme, where each cover is $k$-colorable, than one
can efficiently compute a solution for the oblivious buy-at-bulk problem with
approximation ratio $O(s\cdot\beta^{2}\cdot k\cdot\log n)$. Interestingly, no
colorable strong sparse covers for $K_{r}$-minor free graphs were known
before. Hence the question from [SBI11] remained open until now. Using our
Theorem 1 we conclude:

######  Corollary 5.

For every $n$-vertex weighted $K_{r}$-minor free graph $G=(V,E,w)$ admits an
efficiently computable solution to the oblivious buy-at-bulk problem with
approximation ratio $O(r^{6}\cdot\log n)$. Furthermore, the solution is also
oblivious to the concave faction $f$.

######  Remark 1.