# Catenary and Mercator projection

Mikhail A. Akhukov
Huawei Nizhny Novgorod Research Center, Nizhny Novgorod, Russia
<EMAIL_ADDRESS>
& Vasiliy A. Es’kin
Department of Radiophysics, University of Nizhny Novgorod, Nizhny Novgorod,
Russia, 603950
and
Huawei Nizhny Novgorod Research Center, Nizhny Novgorod, Russia
<EMAIL_ADDRESS>
& Mikhail E. Smorkalov
Skolkovo Institute of Science and Technology, Moscow, Russia
and
Huawei Nizhny Novgorod Research Center, Nizhny Novgorod, Russia
<EMAIL_ADDRESS>Corresponding author: Mikhail Aleksandrovich Akhukov
<EMAIL_ADDRESS>
###### Abstract

The Mercator projection is sometimes confused with another mapping technique,
specifically the central cylindrical projection, which projects the Earth’s
surface onto a cylinder tangent to the equator, as if a light source is at the
Earth’s center. Accidentally, this misconception is rather close to a truth.
The only operation that the map needs is a free bending in a uniform
gravitational field if the map’s material is dense and soft enough to produce
a catenary profile. The north and south edges of the map should be parallel
and placed in the same plane at the appropriate distance. In this case, the
bent map been projected onto this plane gives the Mercator projection. This
property is rather curious, since it allows to make such a sophisticated one-
to-one mapping as the Mercator projection using simple tools available in the
workroom.

_Keywords_ Mercator projection, Central cylindrical projection, Gudermannian
function, Catenary

##  1 Introduction

A catenary is a curve that appears in the profile of an idealized freely
hanging heavy chain under its own weight, supported only at its ends in a
uniform gravitational field. The exact shape of the curve is described by the
hyperbolic cosine function.

The Mercator projection is a cylindrical map projection. It is a conformal
projection, which means that it preserves the angles. The formal equation for
the Mercator projection can be expressed in a number of ways. Within them,
there is also a variant that includes a hyperbolic cosine function (Osborne,
2016). This fact will be discussed in more details further.

The map in Mercator projection was published in 1569 by the Flemish
philosopher and mathematician Gerhardus Mercator. The map was originally
designed for navigation, as it maps loxodromes into the straight lines. The
loxodrome or rhumb line is a line on the sphere of a ship’s course in the
constant compass direction. This allows sailors to plot a straight course
between two points by following a constant compass bearing. The exact
calculation of Mercator projection requires logarithms and modern calculus
that had not yet been invented at that time.

Figure 1:  To calculate the Mercator projection of a given point $N$ with
latitude $\varphi$, we first project the point $N$ to the point $B$ on the
vertical line $AB$, then move it vertically downward to the point $Q$. The
exact vertical coordinate of the point $Q$ is $\psi$, which is expressed by
the equation (1).

##  2 Mercator projection

The Mercator projection is derived from a differential equation, which is
based on the conception of equal scales and requires the integration of the
secant function. Having a latitude $\varphi$ (see figure 1), in case of a unit
sphere, the formal equation of the vertical coordinate of the Mercator map
projection is as follow:

$\psi:=\int\limits_{0}^{\varphi}\frac{dt}{\cos{t}}=\ln\left(\tan\left(\frac{\varphi}{2}+\frac{\pi}{4}\right)\right).$
(1)

This equation can be expressed in a number of ways using the Gudermannian
function ((Weisstein, 1999) page 778, (Yanpolskiy, 1960) page 47), which is
popular in calculus, because it relates circular ($\varphi$) and hyperbolic
($\psi$) angle measures as $\varphi=gd(\psi)$, and allows to establish a
number of relations between trigonometric and hyperbolic function directly
without the imaginary unit.

The theory of the Gudermannian function introduces a concept of hyperbolic
amplitude ((Yanpolskiy, 1960) page 47), that is a special angle constructed
for an arbitrary point belonging to a unit hyperbola. It is also known as the
gudermannian of the hyperbolic measure $\psi$ because it is expressed in terms
of the Gudermannian function: $\varphi=\operatorname{gd}(\psi)$.

Figure 2:  The hyperbolic amplitude $\varphi$ is constructed for an arbitrary
point $M$ belonging to the unit hyperbola (blue curve), as shown here. Also
$\varphi$ is the latitude of the point $N$ figured out in the Mercator
projection (see figure 1 for comparison).

The theory of the Gudermannian function allows to establish a number of
relations (see figure 2):

$L:=|AB|=\tan(\varphi)=\sinh(\psi)=|MP|,$ (2)

$|OB|=\frac{1}{\cos(\varphi)}=\cosh(\psi)=|OP|.$ (3)

Using elementary trigonometry in case of $0\leq\varphi<\pi/2$ we can write:

$\tan\left(\frac{\varphi+\pi/2}{2}\right)=\frac{1+\sin{\varphi}}{\cos{\varphi}}=\frac{1}{\cos{\varphi}}+\sqrt{\frac{1}{\cos^{2}{\varphi}}-1}.$
(4)

Equation (4) allows to rewrite the right-hand side of equation (1) in the next
form:

$\psi=\ln\left(\tan\left(\frac{\varphi}{2}+\frac{\pi}{4}\right)\right)=\operatorname{arcosh}\left(\frac{1}{\cos(\varphi)}\right).$
(5)

See also equation (3) for comparison. For more details on the integration of
the secant function and its relation to the history of the Mercator projection
see Vis (2018).

Equation (5), via area hyperbolic cosine, implicitly introduces a catenary
oriented in the horizontal direction, when vertexes of the unit hyperbola and
area hyperbolic cosine touch each other, see figure 3.

Figure 3:  After introduction of the hyperbolic amplitude $\varphi$ and
disclose its relation to the hyperbolic measure $\psi$ via the Gudermannian
function, the length of the catenary (solid magenta curve $AC$) introduced
implicitly via the area hyperbolic cosine as described by equation (5) is
equal to the length $L$ (solid green line $AB$) that is vertical component of
the central cylindrical map projection.

A key point in this work is next. We need to calculate the length of the area
hyperbolic cosine introduced in such a way as in the equation (5), as a
function of the hyperbolic measure $\psi$, which is the vertical component of
the Mercator map projection:

$L_{catenary}(\psi)=\\\
\int\limits_{0}^{\psi}\sqrt{1+\left(\frac{d\cosh(t)}{dt}\right)^{2}}dt=\\\
\int\limits_{0}^{\psi}\sqrt{1+\sinh^{2}(t)}dt=\\\
\int\limits_{0}^{\psi}\cosh(t)dt=\sinh(\psi).$ (6)

Using equation (2) we see that $L_{catenary}(\psi)=\tan(\varphi)=L$, where $L$
— is vertical component of the central cylindrical map projection. The
equality of two these lengths, the length of line segment $AB$ and the length
of catenary segment $AC$ allows to construct the Mercator map projection from
the central cylindrical map projection by bending the former on the catenary
profile and then project the bent map onto the plane. See figure 3 111All
figures are generated by the scripts in Python programming language (Van
Rossum and Drake Jr, 1995) using the matplotlib library (Hunter, 2007).

###  2.1 Bending parameter

Finally, we calculate the exact parameter of the bending for the map in the
central cylindrical projection to produce the map in the Mercator projection.
If the map in the central cylindrical projection has the plots of a number of
loxodromes, then the straightening of the loxodromes has to be observed from
high enough point of view, that will be an unavoidable sign of the Mercator
map projection.

Suppose, we have a map in the central cylindrical projection constructed
between $\alpha$ degrees of north and south latitudes and physical map’s
height is $H$. The only parameter we need is a distance $D$ between the north
and south edges of the map been placed parallel and in the same plane. Using
equation (2) in case of the unit sphere the distance $D_{unit~{}sphere}$ is
exactly $2\psi$: $D_{unit~{}sphere}=2\operatorname{arsinh}(\tan(\alpha))$. In
case of sphere with arbitrary radius $R$:

$R=\frac{H}{2\tan{\alpha}},$ (7)

we re-scale $D_{unit~{}sphere}$ by $R$, that gives the value of distance $D$:

$D=\frac{H}{\tan{\alpha}}\operatorname{arsinh}\left(\tan{\alpha}\right).$ (8)

##  3 Conclusion

We show that the map in the Mercator projection can be constructed from the
map in the central cylindrical projection as if some one has such map been
printed on dense and soft enough material allows it to hang freely to make the
catenary profile and then project the bent map onto the plane. Interestingly
speaking, if such map has a number of loxodromes, then a person standing high
enough can see that the loxodromes become straight lines when original map is
bent when, for example, the map is carried by two other persons if they hold
the map at the north and south edges.

This hypothetical situation could happen in real life in some kind of workroom
and serve as a basis for further study of this property — the straightening of
loxodromes printed on the map in the central cylindrical projection when this
map hangs freely as described above.

## References

  * Osborne [2016] Peter Osborne.  _The Mercator Projections_.  Zenodo, February 2016.  doi:10.5281/zenodo.35392.  URL https://doi.org/10.5281/zenodo.35392.
  * Weisstein [1999] Eric W Weisstein.  _CRC concise encyclopedia of mathematics_.  CRC press, 1999.
  * Yanpolskiy [1960] Avraam Ruvimovich Yanpolskiy.  _Giperbolicheskie funkcii_.  Ripol Classic, 1960.
  * Vis [2018] MJP Vis.  History of the mercator projection.  B.S. thesis, Utrecht University, The Netherlands, 2018.
  * Van Rossum and Drake Jr [1995] Guido Van Rossum and Fred L Drake Jr.  _Python tutorial_ , volume 620.  Centrum voor Wiskunde en Informatica Amsterdam, The Netherlands, 1995\.
  * Hunter [2007] J. D. Hunter.  Matplotlib: A 2d graphics environment.  _Computing in Science & Engineering_, 9(3):90–95, 2007.


# Approximation schemes for bounded distance problems on fractionally
treewidth-fragile graphs

Zdeněk Dvořák Supported by the ERC-CZ project LL2005 (Algorithms and
complexity within and beyond bounded expansion) of the Ministry of Education
of Czech Republic. email<EMAIL_ADDRESS>Charles University, Prague,
Czech Republic  Abhiruk Lahiri Supported by ISF grant 822/18 and Ariel
University Post-doctoral fellowship. email<EMAIL_ADDRESS>Ariel
University

###### Abstract

We give polynomial-time approximation schemes for monotone maximization
problems expressible in terms of distances (up to a fixed upper bound) and
efficiently solvable in graphs of bounded treewidth. These schemes apply in
all fractionally treewidth-fragile graph classes, a property which is true for
many natural graph classes with sublinear separators. We also provide
quasipolynomial-time approximation schemes for these problems in all classes
with sublinear separators.

##  1 Introduction

In this paper, we consider optimization problems such as:

  * •

Maximum $r$-Independent Set, $r\in\mathbb{Z}^{+}$: Given a graph $G$, the
objective is to find a largest subset $X\subseteq V(G)$ such that distance in
$G$ between any two vertices in $X$ is at least $r$.

  * •

Maximum weight induced forest: Given a graph $G$ and an assignment
$w:V(G)\to\mathbb{Z}_{0}^{+}$ of non-negative weights to vertices, the
objective is to find a subset $X\subseteq V(G)$ such that $G[X]$ does not
contain a cycle and subject to that, $w(X)\coloneqq\sum_{v\in X}w(v)$ is
maximized.

  * •

Maximum $(F,r)$-Matching, for a fixed connected graph $F$ and
$r\in\mathbb{Z}^{+}$: Given a graph $G$, the objective is to find a largest
subset $X\subseteq V(G)$ such that $G[X]$ can be partitioned into vertex-
disjoint copies of $F$ such that distance in $G$ between any two vertices
belonging to different copies is at least $r$.

To be precise, to fall into the scope of our work, the problem must satisfy
the following conditions:

  * •

It must be a maximization problem on certain subsets of vertices of an input
graph, possibly with non-negative weights. That is, the problem specifies
which subsets of vertices of the input graph are _admissible_ , and the goal
is to find an admissible subset of largest size or weight.

  * •

The problem must be defined in terms of distances between the vertices, up to
some fixed bound. That is, there exists a parameter $r\in\mathbb{Z}^{+}$ such
that for any graphs $G$ and $G^{\prime}$, sets $X\subseteq V(G)$ and
$X^{\prime}\subseteq V(G^{\prime})$, and a bijection $f:X\to X^{\prime}$, if
$\min(r,d_{G}(u,v))=\min(r,d_{G^{\prime}}(f(u),f(v)))$ holds for all $u,v\in
X$, then $X$ is admissible in $G$ if and only if $X^{\prime}$ is admissible in
$G^{\prime}$.

  * •

The problem must be monotone (i.e., all subsets of an admissible set must be
admissible), or at least near-monotone (as happens for example for Maximum
$(F,r)$-Matching) in the following sense: There exists a parameter
$c\in\mathbb{Z}^{+}$ such that for any admissible set $A$ in a graph $G$,
there exists a system $\\{R_{v}\subseteq A:v\in A\\}$ of subsets of $A$ such
that every vertex belongs to $R_{v}$ for at most $c$ vertices $v\in A$, $v\in
R_{v}$ for each $v\in A$, and for any $Z\subseteq A$, the subset
$X\setminus\bigcup_{v\in Z}R_{v}$ is admissible in $G$.

  * •

The problem must be tractable in graphs of bounded treewidth, that is, there
must exist a function $g$ and a polynomial $p$ such that given any graph $G$,
its tree decomposition of width $t$, an assignment $w$ of non-negative weights
to the vertices of $G$, and a set $X_{0}\subseteq X$, it is possible to find a
maximum-weight admissible subset of $X_{0}$ in time $g(t)p(|V(G)|)$.

Let us call such problems _$(\leq\\!r)$ -distance determined $c$-near-monotone
$(g,p)$-tw-tractable_. Note that a convenient way to verify these assumptions
is to show that the problem is expressible in _solution-restricted Monadic
Second-Order Logic_ ($\operatorname{\mathsf{MSOL}}$) _with bounded-distance
predicates_ , i.e., by a $\operatorname{\mathsf{MSOL}}$ formula with one free
variable $X$ such that the quantification is restricted to subsets and
elements of $X$, and using binary predicates $d_{1}$, …, $d_{r}$, where
$d_{i}(u,v)$ is interpreted as testing whether the distance between $u$ and
$v$ in the whole graph is at most $i$. This ensures that the problem is
$(\leq\\!r)$-distance determined, and $(g,O(n))$-tw-tractable for some
function $g$ by Courcelle’s metaalgorithmic result [5].

Of course, the problems satisfying the assumptions outlined above are
typically hard to solve optimally, even in rather restrictive circumstances.
For example, Maximum Independent Set is $\operatorname{\mathsf{NP}}$-hard even
in planar graphs of maximum degree at most $3$ and arbitrarily large (fixed)
girth [1]. Moreover, it is hard to approximate it within factor of $0.995$ in
graphs of maximum degree at most three [4]. Hence, to obtain polynomial-time
approximation schemes ($\operatorname{\mathsf{PTAS}}$), i.e., polynomial-time
algorithms for approximating within any fixed precision, further restrictions
on the considered graphs are needed.

A natural restriction that has been considered in this context is the
requirement that the graphs have sublinear separators (a set $S$ of vertices
of a graph $G$ is a _balanced separator_ if every component of $G\setminus S$
has at most $|V(G)|/2$ vertices, and a hereditary class $\mathcal{G}$ of
graphs has _sublinear separators_ if for some $c<1$, every graph
$G\in\mathcal{G}$ has a balanced separator of size $O(|V(G)|^{c})$). This
restriction still lets us speak about many interesting graph classes (planar
graphs [18] and more generally proper minor-closed classes [2], many geometric
graph classes [20], …). Moreover, the problems discussed above admit
$\operatorname{\mathsf{PTAS}}$ in all classes with sublinear separators or at
least in substantial subclasses of these graphs:

  * •

Maximum Independent Set has been shown to admit $\operatorname{\mathsf{PTAS}}$
in graphs with sublinear separators already in the foundational paper of
Lipton and Tarjan [19].

  * •

For any positive integer, Maximum $r$-Independent Set and several other
problems are known to admit $\operatorname{\mathsf{PTAS}}$ in graphs with
sublinear separators by a straightforward local search algorithm [16].

  * •

All of the problems mentioned above (an more) are known to admit
$\operatorname{\mathsf{PTAS}}$ in planar graphs by a layering argument of
Baker [3]; this approach can be extended to some related graph classes,
including all proper minor-closed classes [6, 12].

  * •

The problems also admit $\operatorname{\mathsf{PTAS}}$ in graph classes that
admit thin systems of overlays [11], a technical property satisfied by all
proper minor-closed classes and by all hereditary classes with sublinear
separators and bounded maximum degree.

  * •

Bidimensionality arguments [7] apply to a wide range of problems in proper
minor-closed graph classes.

However, each of the outlined approaches has drawbacks. On one side, the local
search approach only applies to specific problems and does not work at all in
the weighted setting. On the other side of the spectrum, Baker’s approach is
quite general as far as the problems go, but there are many hereditary graph
classes with sublinear separators to which it does not seem to apply. The
approach through thin systems of overlays tries to balance these concerns, but
it is rather technical and establishing this property is difficult.

Another option that has been explored is via _fractional treewidth-fragility_.
For a function $f\colon\mathbb{Z}^{+}\times\mathbb{Z}^{+}\to\mathbb{Z}^{+}$
and a polynomial $p$, a class of graphs $\mathcal{G}$ is _$p$ -efficiently
fractionally treewidth-$f$-fragile_ if there exists an algorithm that for
every $k\in\mathbb{Z}^{+}$ and a graph $G\in\mathcal{G}$ returns in time
$p(|V(G)|)$ a collection of subsets $X_{1},X_{2},\dots X_{m}\subseteq V(G)$
such that each vertex of $G$ belongs to at most $m/k$ of the subsets, and
moreover, for $i=1,\ldots,m$, the algorithm also returns a tree decomposition
of $G\setminus X_{i}$ of width at most $f(k,|V(G)|)$. We say a class is _$p$
-efficiently fractionally treewidth-fragile_ if $f$ does not depend on its
second argument (the number of vertices of $G$). This property turns out to
hold for basically all known natural graph classes with sublinear separators.
In particular, a hereditary class $\mathcal{G}$ of graphs is efficiently
fractionally treewidth-fragile if

  * •

$\mathcal{G}$ has sublinear separator and bounded maximum degree [9],

  * •

$\mathcal{G}$ is proper minor-closed [8, 12], or

  * •

$\mathcal{G}$ consists of intersection graphs of convex objects with bounded
aspect ratio in a finite-dimensional Euclidean space and the graphs have
bounded clique number, as can be seen by a modification of the argument of
Erlebach et al. [15]. This includes all graph classes with polynomial growth
[17].

In fact, Dvořák conjectured that every hereditary class with sublinear
separators is fractionally treewidth-fragile, and gave the following result
towards this conjecture.

######  Theorem 1 (Dvořák [10]).

There exists a polynomial $p$ so that the following claim holds. For every
hereditary class $\mathcal{G}$ of graphs with sublinear separators, there
exists a polynomial $q$ such that $\mathcal{G}$ is $p$-efficiently
fractionally treewidth-$f$-fragile for the function $f(k,n)=q(k\log n)$.

Moreover, Dvořák [9] observed that weighted Maximum Independent Set admits a
$\operatorname{\mathsf{PTAS}}$ in any efficiently fractionally treewidth-
fragile class of graphs. Indeed, the algorithm is quite simple, based on the
observation that for the sets $X_{1}$, …, $X_{m}$ from the definition of
fractional treewidth-fragility, at least one of the graphs $G\setminus X_{1}$,
…, $G\setminus X_{m}$ (of bounded treewidth) contains an independent set whose
weight is within the factor of $1-1/k$ from the optimal solution. A problem
with this approach is that it does not generalize to more general problems;
even for the Maximum $2$-Independent Set problem, the approach fails, since a
$2$-independent set in $G\setminus X_{i}$ is not necessarily $2$-independent
in $G$. Indeed, this observation served as one of the motivations behind more
restrictive (and more technical) concepts employed in [11, 12].

As our main result, we show that this intuition is in fact false: There is a
simple way how to extend the approach outlined in the previous paragraph to
all bounded distance determined near-monotone tw-tractable problems.

######  Theorem 2.

For every class $\mathcal{G}$ of graphs with bounded expansion, there exists a
function $h:\mathbb{Z}^{+}\times\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ such that the
following claim holds. Let $c$ and $r$ be positive integers,
$g:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ and
$f:\mathbb{Z}^{+}\times\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ functions and $p$ and
$q$ polynomials. If $\mathcal{G}$ is $q$-efficiently fractionally
treewidth-$f$-fragile, then for every $(\leq\\!r)$-distance determined
$c$-near-monotone $(g,p)$-tw-tractable problem, there exists an algorithm that
given a graph $G\in\mathcal{G}$, an assignment of non-negative weights to
vertices, and a positive integer $k$, returns in time
$h(r,c)|V(G)|+q(|V(G)|)\cdot p(|V(G)|)\cdot g(f(h(r,c)k,|V(G)|))$ an
admissible subset of $V(G)$ whose weight is within the factor of $1-1/k$ from
the optimal one.

Note that the assumption that $\mathcal{G}$ has bounded expansion is of little
consequence—it is true for any hereditary class with sublinear separators [14]
as well as for any fractionally treewidth-fragile class [9]; see Section 2 for
more details. The time complexity of the algorithm from Theorem 2 is
polynomial if $f$ does not depend on its second argument, and quasipolynomial
(exponential in a polylogaritmic function) if $f$ is logarithmic in the second
argument and $g$ is single-exponential (i.e., if $\log\log g(n)=O(\log n)$).
Hence, we obtain the following corollaries.

######  Corollary 3.

Let $c$ and $r$ be positive integers, $g:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ a
function and $p$ a polynomial. Every $(\leq\\!r)$-distance determined
$c$-near-monotone $(g,p)$-tw-tractable problem admits a
$\operatorname{\mathsf{PTAS}}$ in any efficiently fractionally treewidth-
fragile class of graphs.

We say a problem admits a quasipolynomial-time approximation schemes
($\mathsf{QPTAS}$) if there exist quasipolynomial-time algorithms for
approximating the problem within any fixed precision. Combining Theorems 1 and
2, we obtain the following result.

######  Corollary 4.

Let $c$ and $r$ be positive integers, $g:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ a
single-exponential function, and $p$ a polynomial. Every $(\leq\\!r)$-distance
determined $c$-near-monotone $(g,p)$-tw-tractable problem admits a
$\mathsf{QPTAS}$ in any hereditary class of graphs with sublinear separators.

The idea of the algorithm from Theorem 2 is quite simple: We consider the sets
$X_{1},\ldots,X_{m}$ from the definition of fractional
treewidth-$f$-fragility, extend them to suitable supersets $Y_{1}$, …,
$Y_{m}$, and argue that for $i=1,\ldots,m$, any admissible set in $G\setminus
X_{i}$ disjoint from $Y_{i}$ is also admissible in $G$, and that for some $i$,
the weight of the heaviest admissible set in $G\setminus X_{i}$ disjoint from
$Y_{i}$ is within the factor of $1-1/k$ from the optimal one. The construction
of the sets $Y_{1}$, …, $Y_{m}$ is based on the existence of orientations with
bounded outdegrees that represent all short paths, a result of independent
interest that we present in Section 2.

Let us remark one can develop the idea of this paper in further directions.
Dvořák proved in [13](via a substantially more involved argument) that every
monotone maximization problem expressible in first-order logic admits a
$\operatorname{\mathsf{PTAS}}$ in any efficiently fractionally treewidth-
fragile class of graphs. Note that this class of problems is incomparable with
the one considered in this paper (e.g., Maximum Induced Forest is not
expressible in the first-order logic, while Maximum Independent Set consisting
of vertices belonging to triangles is expressible in the first-order logic but
does not fall into the scope of the current paper).

Finally, it is worth mentioning that our results only apply to maximization
problems. We were able to extend the previous uses of fractional treewidth-
fragility by giving a way to handle dependencies over any bounded distance.
However, for the minimization problems, we do not know whether fractional
treewidth-fragility is sufficient even for the distance-$1$ problems. For a
simple example, consider the Minimum Vertex Cover problem in fractionally
treewidth-fragile graphs, or more generally in hereditary classes with
sublinear separators. While the unweighted version can be dealt with by the
local search method [16], we do not know whether there exists a
$\operatorname{\mathsf{PTAS}}$ for the weighted version of this problem.

##  2 Paths and orientations in graphs with bounded expansion

For $r\in\mathbb{Z}^{+}_{0}$, a graph $H$ is an _$r$ -shallow minor_ of a
graph $G$ if $H$ can be obtained from a subgraph of $G$ by contracting
pairwise vertex-disjoint connected subgraphs, each of radius at most $r$. For
a function $f\colon\mathbb{Z}^{+}\to\mathbb{Z}^{+}$, a class $\mathcal{G}$ of
graphs has _expansion bounded_ by $f$ if for all non-negative integers $r$,
all $r$-shallow minors of graphs from $\mathcal{G}$ have average degree at
most $f(r)$. A class has bounded expansion if its expansion is bounded by some
function $f$. The theory of graph classes with bounded expansion has been
developed in the last 15 years, and the concept has found many algorithmic and
structural applications; see [22] for an overview. Crucially for us, this
theory includes a number of tools for dealing with short paths. Moreover, as
we have pointed out before, all hereditary graph classes with sublinear
separators [14] as well as all fractionally treewidth-fragile classes [9] have
bounded expansion.

Let $\vec{G}$ be an orientation of a graph $G$, i.e, $uv$ is an edge of $G$ if
and only if the directed graph $\vec{G}$ contains at least one of the directed
edges $(u,v)$ and $(v,u)$; note that we allow $\vec{G}$ to contain both of
them at the same time, and thus for the edge $uv$ to be oriented in both
directions. We say that a directed graph $\vec{H}$ with the same vertex set is
a _$1$ -step fraternal augmentation of $\vec{G}$_ if
$\vec{G}\subseteq\vec{H}$, for all distinct edges $(x,y),(x,z)\in E(\vec{G})$,
either $(y,z)$ or $(z,y)$ is an edge of $\vec{H}$, and for each edge $(y,z)\in
E(\vec{H})\setminus E(\vec{G})$, there exists a vertex $x\in
V(\vec{G})\setminus\\{y,z\\}$ such that $(x,y),(x,z)\in E(\vec{G})$. That is,
to obtain $\vec{H}$ from $\vec{G}$, for each pair of edges $(x,y),(x,z)\in
E(\vec{G})$ we add an edge between $y$ and $z$ in one of the two possible
directions (we do not specify the direction, but in practice we would choose
directions of the added edges that minimize the maximum outdegree of the
resulting directed graph). For an integer $a\geq 0$, we say $\vec{F}$ is an
_$a$ -step fraternal augmentation of $\vec{G}$_ if there exists a sequence
$\vec{G}=\vec{G}_{0},\vec{G}_{1},\ldots,\vec{G}_{a}=\vec{F}$ where for
$i=1,\ldots,a$, $\vec{G}_{i}$ is a $1$-step fraternal augmentation of
$\vec{G}_{i-1}$. We say $\vec{F}$ is an $a$-step fraternal augmentation of an
undirected graph $G$ if $\vec{F}$ is an $a$-step fraternal augmentation of
some orientation of $G$. A key property of graph classes with bounded
expansion is the existence of fraternal augmentations with bounded outdegrees.
Let us remark that whenever we speak about an algorithm returning an $a$-step
fraternal augmentation $\vec{H}$ or taking one as an input, this implicitly
includes outputing or taking as an input the whole sequence of $1$-step
fraternal augmentations ending in $\vec{H}$.

######  Lemma 5 (Nešetřil and Ossona de Mendez [21]).

For every class $\mathcal{G}$ with bounded expansion, there exists a function
$d:\mathbb{Z}^{+}_{0}\to\mathbb{Z}^{+}$ such that for each $G\in\mathcal{G}$
and each non-negative integer $a$, the graph $G$ has an $a$-step fraternal
augmentation of maximum outdegree at most $d(a)$. Moreover, such an
augmentation can be found in time $O(d(a)|V(G)|)$.

As shown already in [21], fraternal augmentations can be used to succintly
represent distances between vertices of the graph. For the purposes of this
paper, we need a more explicit representation by an orientation of the
original graph (without the additional augmentation edges). By a _walk_ in a
directed graph $\vec{G}$, we mean a sequence $W=v_{0}v_{1}v_{2}\ldots v_{b}$
such that for $i=1,\ldots,b$, $(v_{i-1},v_{i})\in E(\vec{G})$ or
$(v_{i},v_{i-1})\in E(\vec{G})$; that is, the walk does not have to respect
the orientation of the edges. The walk $W$ is _inward directed_ if for some
$c\in\\{0,\ldots,b\\}$, we have $(v_{i},v_{i+1})\in E(\vec{G})$ for
$i=0,\ldots,c-1$ and $(v_{i},v_{i-1})\in E(\vec{G})$ for $i=c+1,\ldots,b$. For
a positive integer $r$, an orientation $\vec{G}$ of a graph $G$ _represents
$(\leq\\!r)$-distances_ if for each $u,v\in V(G)$ and each
$b\in\\{0,\ldots,r\\}$, the distance between $u$ and $v$ in $G$ is at most $b$
if and only if $\vec{G}$ contains an inward-directed walk of length at most
$b$ between $u$ and $v$. Note that given such an orientation with bounded
maximum outdegree for a fixed $r$, we can determine the distance between $u$
and $v$ (up to distance $r$) by enumerating all (constantly many) walks of
length at most $r$ directed away from $u$ and away from $v$ and inspecting
their intersections.

Our goal now is to show that graphs from classes with bounded expansion admit
orientations with bounded maximum outdegree that represent
$(\leq\\!r)$-distances. Let us define a more general notion used in the proof
of this claim, adding to the fraternal augmentations the information about the
lengths of the walks in the original graph represented by the added edges. A
_directed graph with $(\leq\\!r)$-length sets_ is a pair $(\vec{H},\ell)$,
where $\vec{H}$ is a directed graph and $\ell$ is a function assigning a
subset of $\\{1,\ldots,r\\}$ to each _unordered_ pair $\\{u,v\\}$ of vertices
of $\vec{H}$, such that if neither $(u,v)$ nor $(v,u)$ is an edge of
$\vec{H}$, then $\ell(\\{u,v\\})=\emptyset$. We say that $(\vec{H},\ell)$ is
an _orientation_ of a graph $G$ if $G$ is the underlying undirected graph of
$\vec{H}$ and $\ell(\\{u,v\\})=\\{1\\}$ for each $uv\in E(G)$. We say that
$(\vec{H},\ell)$ is an _$(\leq\\!r)$ -augmentation_ of $G$ if
$V(\vec{H})=V(G)$, for each $uv\in E(G)$ we have $1\in\ell(\\{u,v\\})$, and
for each $u,v\in V(G)$ and $b\in\ell(\\{u,v\\})$ there exists a walk of length
$b$ from $u$ to $v$ in $G$. Let $(\vec{H}_{1},\ell_{1})$ be another directed
graph with $(\leq\\!r)$-length sets. We say $(\vec{H}_{1},\ell_{1})$ is a
_1-step fraternal augmentation_ of $(\vec{H},\ell)$ if $\vec{H}_{1}$ is a
$1$-step fraternal augmentation of $\vec{H}$ and for all distinct $u,v\in
V(\vec{H})$ and $b\in\\{1,\ldots,r\\}$, we have $b\in\ell_{1}(\\{u,v\\})$ if
and only if $b\in\ell(\\{u,v\\})$ or there exist $x\in
V(\vec{H})\setminus\\{u,v\\}$, $b_{1}\in\ell(\\{x,u\\})$, and
$b_{2}\in\ell(\\{x,v\\})$ such that $(x,u),(x,v)\in E(\vec{H})$ and
$b=b_{1}+b_{2}$. Note that a $1$-step fraternal augmentation of an
$(\leq\\!r)$-augmentation of a graph $G$ is again an $(\leq\\!r)$-augmentation
of $G$. The notion of an $a$-step fraternal augmentation of a graph $G$ is
then defined in the natural way, by starting with an orientation of $G$ and
peforming the $1$-step fraternal augmentation operation $a$-times. Let us now
restate Lemma 5 in these terms (we just need to maintain the edge length sets,
which can be done with $O(a^{2})$ overhead per operation).

######  Lemma 6.

Let $\mathcal{G}$ be a class of graphs with bounded expansion, and let
$d:\mathbb{Z}^{+}_{0}\to\mathbb{Z}^{+}$ be the function from Lemma 5. For each
$G\in\mathcal{G}$ and each non-negative integer $a$, we can in time
$O(a^{2}d(a)|V(G)|)$ construct a directed graph with $(\leq\\!a+1)$-length
sets $(\vec{H},\ell)$ of maximum outdegree at most $d(a)$ such that
$(\vec{H},\ell)$ is an $a$-step fraternal augmentation of $G$.

Let $(\vec{H},\ell)$ be an $(\leq\\!r)$-augmentation $(\vec{H},\ell)$ of a
graph $G$. For $b\leq r$, a _length $b$ walk_ in $(\vec{H},\ell)$ is a tuple
$(v_{0}v_{1}\ldots v_{t},b_{1},\ldots,b_{t})$, where $v_{0}v_{1}\ldots v_{t}$
is a walk in $\vec{H}$, $b_{i}\in\ell(\\{v_{i-1},v_{i}\\}$ for $i=1,\ldots,t$,
and $b=b_{1}+\ldots+b_{t}$. Note that if there exists a length $b$ walk from
$u$ to $v$ in $(\vec{H},\ell)$, then there also exists a walk of length $b$
from $u$ to $v$ in $G$. We say that $(\vec{H},\ell)$ _represents
$(\leq\\!r)$-distances_ in $G$ if for all vertices $u,v\in V(G)$ at distance
$b\leq r$ from one another, $(\vec{H},\ell)$ contains an inward-directed
length $b$ walk between $u$ and $v$. Next, we show that this property always
holds for sufficient fraternal augmentations.

######  Lemma 7.

Let $G$ be a graph and $r$ a positive integer and let $(\vec{H},\ell)$ be a
directed graph with $(\leq\\!r)$-length sets. If $(\vec{H},\ell)$ is obtained
as an $(r-1)$-step fraternal augmentation of $G$, then it represents
$(\leq\\!r)$-distances in $G$.

###### Proof.

For $b\leq r$, consider any length $b$ walk $W=(v_{0}v_{1}\ldots
v_{t},b_{1},\ldots,b_{t})$ in an $(\leq\\!r)$-augmentation
$(\vec{H}_{1},\ell_{1})$ of $G$, and let $(\vec{H}_{2},\ell_{2})$ be a
$1$-step augmentation of $(\vec{H}_{1},\ell_{1})$. Note that $W$ is also a
length $b$ walk between $v_{0}$ and $v_{t}$ in $(\vec{H}_{2},\ell_{2})$.
Suppose that $W$ is not inward-directed in $(\vec{H}_{1},\ell_{1})$, and thus
there exists $i\in\\{1,\ldots,t-1\\}$ such that
$(v_{i},v_{i-1}),(v_{i},v_{i+1})\in E(\vec{H}_{1})$. By the definition of
$1$-step fraternal augmentation, this implies
$b_{i}+b_{i+1}\in\ell_{2}(v_{i-1},v_{i+1})$, and thus $(v_{0}\ldots
v_{i-1}v_{i+1}\ldots v_{t},b_{1},\ldots,b_{i}+b_{i+1},\ldots b_{t})$ is a
length $b$ walk from $v_{0}$ to $v_{t}$ in $(\vec{H}_{2},\ell_{2})$.

Let $(\vec{G}_{0},\ell_{0})$, …, $(\vec{G}_{r-1},\ell_{r-1})$ be a sequence of
$(\leq\\!r)$-augmentations of $G$, where $(\vec{G},\ell_{0})$ is an
orientation of $G$, $(\vec{G}_{r-1},\ell_{r-1})=(\vec{H},\ell)$, and for
$i=1,\ldots,r-1$, $(\vec{G}_{i},\ell_{i})$ is a $1$-step fraternal
augmentation of $(\vec{G}_{i-1},\ell_{i-1})$. Let $u$ and $v$ be any vertices
at distance $b\leq r$ in $G$, and let $P$ be a shortest path between them.
Then $P$ naturally corresponds to a length $b$ walk $P_{0}$ in
$(\vec{G}_{0},\ell_{0})$. For $i=1,\ldots,r-1$, if $P_{i-1}$ is inward-
directed, then let $P_{i}=P_{i-1}$, otherwise let $P_{i}$ be a length $b$ walk
in $(\vec{G}_{i},\ell_{i})$ obtained from $P_{i-1}$ as described in the
previous paragaph. Since each application of the operation decreases the
number of vertices of the walk, we conclude that $P_{r-1}$ is an inward-
directed length $b$ walk between $u$ and $v$ in $(\vec{H},\ell)$. Hence,
$(\vec{H},\ell)$ represents $(\leq\\!r)$-distances in $G$. ∎

Next, let us propagate this property back through the fraternal augmentations
by orienting some of the edges in both directions. We say that
$(\vec{H},\ell)$ is an _$a$ -step fraternal superaugmentation_ of a graph $G$
if there exists an $a$-step fraternal augmentation $(\vec{F},\ell)$ of $G$
such that $V(\vec{F})=V(\vec{H})$, $E(\vec{F})\subseteq E(\vec{H})$ and for
each $(u,v)\in E(\vec{H})\setminus E(\vec{F})$, we have $(v,u)\in E(\vec{F})$.
We say that $(\vec{F},\ell)$ is a _support_ of $(\vec{H},\ell)$.

######  Lemma 8.

Let $G$ be a graph and $r$ a positive integer and let $(\vec{H},\ell)$ be an
$(\leq\\!r)$-augmentation of $G$ of maximum outdegree $\Delta$ representing
$(\leq\\!r)$-distances. For $a\geq 1$, suppose that $(\vec{H},\ell)$ is an
$a$-step fraternal superaugmentation of $G$. Then we can in time
$O(r^{2}\Delta|V(G)|)$ obtain an $(a-1)$-step fraternal superaugmentation of
$G$ representing $(\leq\\!r)$-distances, of maximum outdegree at most
$(r+1)\Delta$.

###### Proof.

Let $(\vec{F},\ell)$ be an $a$-step fraternal augmentation of $G$ forming a
support of $(\vec{H},\ell)$, obtained as a $1$-step fraternal augmentation of
an $(a-1)$-step fraternal augmentation $(\vec{F}_{1},\ell_{1})$ of $G$. Let
$(\vec{H}_{1},\ell_{1})$ be the $(a-1)$-step fraternal superaugmentation of
$G$ obtained from $(\vec{F}_{1},\ell_{1})$ as follows:

  * •

For all distinct vertices $y,z\in V(G)$ such that $(y,z),(z,y)\in E(\vec{H})$,
$(y,z)\in E(\vec{F}_{1})$, and $(z,y)\not\in E(\vec{F}_{1})$, we add the edge
$(z,y)$.

  * •

For each edge $(y,z)\in E(\vec{H})$ and integer
$b\in\ell(\\{y,z\\})\setminus\ell_{1}(\\{y,z\\})$, we choose a vertex $x\in
V(G)\setminus\\{y,z\\}$ such that $(x,y),(x,z)\in E(\vec{F}_{1})$ and
$b=b_{1}+b_{2}$ for some $b_{1}\in\ell_{1}(\\{x,y\\})$ and
$b_{2}\in\ell_{1}(\\{x,z\\})$, and add the edge $(y,x)$. Note that such a
vertex $x$ and integers $b_{1}$ and $b_{2}$ exist, since $b$ was added to
$\ell(\\{y,z\\})$ when $(\vec{F},\ell)$ was obtained from
$(\vec{F}_{1},\ell_{1})$ as a $1$-step fraternal augmentation.

Each edge $(y,x)\in E(\vec{H}_{1})\setminus E(\vec{H})$ arises from an edge
$(y,z)\in E(\vec{H})$ leaving $y$ and an element
$b\in\ell(\\{y,z\\})\setminus\ell_{1}(\\{y,z\\})$, and each such pair
contributes at most one edge leaving $y$. Hence, the maximum outdegree of
$\vec{H}_{1}$ is at most $(r+1)\Delta$.

Consider a length $b$ inwards-directed walk $(v_{0}v_{1}\ldots
v_{t},b_{1},\ldots,b_{t})$ in $\vec{H}$, for any $b\leq r$. Then $\vec{H}$
contains a length $b$ inwards-directed walk from $v_{0}$ to $v_{t}$ obtained
by natural edge replacements: For any edge $(y,z)\in E(\vec{H})$ of this walk
and $b^{\prime}\in\ell_{i}(\\{y,z\\})$, the construction described above
ensures that if $(y,z)\not\in E(\vec{H}_{1})$ or
$b^{\prime}\not\in\ell_{1}(\\{y,z\\})$, then there exists $x\in
V(G)\setminus\\{y,z\\}$ such that $(y,x),(x,z)\in E(\vec{H}_{1})$ and
$b^{\prime}=b^{\prime\prime}+b^{\prime\prime\prime}$ for some
$b^{\prime\prime}\in\ell_{1}(\\{x,y\\})$ and
$b^{\prime\prime\prime}\in\ell_{1}(\\{x,z\\})$, and we can replace the edge
$(y,z)$ in the walk by the edges $(y,x)$ and $(x,z)$ of $E(\vec{H}_{1})$.
Since $\vec{H}$ represents $(\leq\\!r)$-distances in $G$, this transformation
shows that so does $\vec{H}_{1}$. ∎

We are now ready to prove the main result of this section.

######  Lemma 9.

For any class $\mathcal{G}$ with bounded expansion, there exists a function
$d^{\prime}:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ such that for each
$G\in\mathcal{G}$ and each positive integer $r$, the graph $G$ has an
orientation with maximum outdegree at most $d^{\prime}(r)$ that represents
$(\leq\\!r)$-distances in $G$. Moreover, such an orientation can be found in
time $O(r^{2}d^{\prime}(r)|V(G)|)$.

###### Proof.

Let $d$ be the function from Lemma 5, and let
$d^{\prime}(r)=(r+1)^{r-1}d(r-1)$. By Lemma 6, we obtain an $(r-1)$-step
fraternal augmentation $(\vec{H},\ell)$ of $G$ of maximum outdegree at most
$d(r-1)$. By Lemma 7, $(\vec{H},\ell)$ represents $(\leq\\!r)$-distances in
$G$. Repeatedly applying Lemma 8, we obtain a $0$-step fraternal
superaugmentation $(\vec{G},\ell_{0})$ of $G$ of maximum outdegree at most
$d^{\prime}(r)$ representing $(\leq\\!r)$-distances. Clearly, $\vec{G}$ is an
orientation of $G$ of maximum outdegree at most $d^{\prime}(r)$ representing
$(\leq\\!r)$-distances. ∎

##  3 Approximation schemes

Let us now prove Theorem 2. To this end, let us start with a lemma to be
applied to the sets arising from fractional treewidth-fragility.

######  Lemma 10.

Let $\vec{G}$ be an orientation of a graph $G$ with maximum outdegree
$\Delta$. Let $A$ be a set of vertices of $G$ and for a positive integer $c$,
let $\\{R_{v}:v\in A\\}$ be a system of subsets of $A$ such that each vertex
belongs to at most $c$ of the subsets. For $X\subseteq V(G)$ and a positive
integer $r$, let $D_{\vec{G},r}(X)$ be the union of the sets $R_{v}$ for all
vertices $v\in V(G)$ such that $\vec{G}$ contains a walk from $v$ to $X$ of
length at most $r$ directed away from $v$. For a positive integer $k$, let
$X_{1}$, …, $X_{m}$ be a system of subsets of $V(G)$ such that each vertex
belongs to at most $\frac{m}{c(\Delta+1)^{r}k}$ of the subsets. For any
assignment $w$ of non-negative weights to vertices of $G$, there exists
$i\in\\{1,\ldots,m\\}$ such that $w(A\setminus
D_{\vec{G},r}(X_{i}))\geq(1-1/k)w(A)$.

###### Proof.

For a vertex $z\in A$, let $B(z)$ be the set of vertices reachable in
$\vec{G}$ from vertices $v\in A$ such that $z\in R_{v}$ by walks of length at
most $r$ directed away from $v$. Note that $|B(z)|\leq c(\Delta+1)^{r}$ and
that for each $X\subseteq V(G)$, we have $z\in D_{\vec{G},r}(X)$ if and only
if $B(z)\cap X\neq\emptyset$.

Suppose for a contradiction that for each $i$ we have $w(A\setminus
D_{\vec{G},r}(X_{i}))<(1-1/k)w(A)$, and thus $w(D_{\vec{G},r}(X_{i}))>w(A)/k$.
Then

$\displaystyle\frac{m}{k}w(A)$
$\displaystyle<\sum_{i=1}^{m}w(D_{\vec{G},r}(X_{i}))=\sum_{i=1}^{m}\sum_{z\in
D_{\vec{G},r}(X_{i})}w(z)=\sum_{i=1}^{m}\sum_{z\in A:B(z)\cap
X_{i}\neq\emptyset}w(z)$ $\displaystyle\leq\sum_{i=1}^{m}\sum_{z\in
A}w(z)|B(z)\cap X_{i}|=\sum_{z\in A}w(z)\sum_{i=1}^{m}|B(z)\cap X_{i}|$
$\displaystyle=\sum_{z\in A}w(z)\sum_{x\in B(z)}|\\{i\in\\{1,\ldots,m\\}:x\in
X_{i}\\}|\leq\sum_{z\in A}w(z)\sum_{x\in B(z)}\frac{m}{c(\Delta+1)^{r}k}$
$\displaystyle=\sum_{z\in A}w(z)|B(z)|\frac{m}{c(\Delta+1)^{r}k}\leq\sum_{z\in
A}w(z)\frac{m}{k}=\frac{m}{k}w(A),$

which is a contradiction. ∎

Next, let us derive a lemma on admissibility for $(\leq\\!r)$-distance
determined problems.

######  Lemma 11.

For a positive integer $r$, let $\vec{G}$ be an orientation of a graph $G$
representing $(\leq\\!r)$-distances. For a set $X\subseteq V(G)$, let
$Y_{\vec{G},r}(X)$ be the set of vertices $y$ such that $\vec{G}$ contains a
walk from $y$ to $X$ of length at most $r$ directed away from $y$. For any
$(\leq\\!r)$-distance determined problem, a set $B\subseteq V(G)\setminus
Y_{\vec{G},r}(X)$ is admissible in $G$ if and only if it is admissible in
$G-X$.

###### Proof.

Since the problem is $(\leq\\!r)$-distance determined, it suffices to show
that $\min(r,d_{G}(u,v))=\min(r,d_{G-X}(u,v))$ holds for all $u,v\in B$.
Clearly, $d_{G}(u,v)\leq d_{G-X}(u,v)$, and thus it suffices to show that if
the distance between $u$ and $v$ is $G$ is $b\leq r$, then $G-X$ contains a
walk of length $b$ between $u$ and $v$. Since $\vec{G}$ represents
$(\leq\\!r)$-distances, there exists an inward-directed walk $P$ of length $b$
between $u$ and $v$ in $\vec{G}$. Since $u,v\not\in Y_{\vec{G},r}(X)$, we have
$V(P)\cap X=\emptyset$, and thus $P$ is also a walk of length $b$ between $u$
and $v$ in $G-X$. ∎

We are now ready to prove the main result.

###### Proof of Theorem 2.

Let $d^{\prime}$ be the function from Lemma 9 for the class $\mathcal{G}$. Let
us define $h(r,c)=c(d^{\prime}(r)+1)^{r}$. The algorithm is as follows. Since
$\mathcal{G}$ is $q$-efficiently fractionally treewidth-$f$-fragile, in time
$q(|V(G)|)$ we can find sets $X_{1},\ldots,X_{m}\subseteq V(G)$ such that each
vertex belongs to at most $\frac{m}{h(r,c)k}$ of them, and for each $i$, a
tree decomposition of $G-X_{i}$ of width at most $f(h(r,c)k,|V(G)|)$. Clearly,
$m\leq q(|V(G)|)$. Next, using Lemma 9, we find an orientation $\vec{G}$ of
$G$ that represents $(\leq\\!r)$-distances. Let $Y_{\vec{G},r}$ be defined as
in the statement of Lemma 11. Since the problem is $(g,p)$-tw-tractable
problem, for each $i$ we can in time $p(|V(G)|)\cdot g(f(h(r,c)k,|V(G)|))$
find a subset $A_{i}$ of $V(G)\setminus Y_{\vec{G},r}(X_{i})$ admissible in
$G-X_{i}$ of largest weight. By Lemma 11, each of these sets is admissible in
$G$; the algorithm return the heaviest of the sets $A_{1}$, …, $A_{m}$.

As the returned set is admissible in $G$, it suffices to argue about its
weight. Let $A$ be a heaviest admissible set in $G$. Let $\\{R_{v}\subseteq
A:v\in A\\}$ be the system of subsets from the definition of $c$-near-
monotonicity, and let $D_{\vec{G},r}$ be defined as in the statement of Lemma
10. By the definition of $c$-near-monotonicity, for each $i$ the set
$A\setminus D_{\vec{G},r}(X_{i})$ is admissible in $G$. Since $v\in R_{v}$ for
each $v\in A$, we have $Y_{\vec{G},r}(X_{i})\subseteq D_{\vec{G},r}(X_{i})$,
and thus by Lemma 11, $A\setminus D_{\vec{G},r}(X_{i})$ is also admissible in
$G-X_{i}$, and by the choice of $A_{i}$, we have $w(A_{i})\geq w(A\setminus
D_{\vec{G},r}(X_{i}))$. By Lemma 10, we conclude that for at least one $i$, we
have $w(A_{i})\geq(1-1/k)w(A)$, as required. ∎

## References

  * [1] Vladimir E. Alekseev, Vadim V. Lozin, Dmitriy S. Malyshev, and Martin Milanic.  The maximum independent set problem in planar graphs.  In Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, volume 5162 of Lecture Notes in Computer Science, pages 96–107. Springer, 2008.  https://doi.org/10.1007/978-3-540-85238-4_7.
  * [2] Noga Alon, Paul D. Seymour, and Robin Thomas.  A separator theorem for graphs with an excluded minor and its applications.  In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 293–299. ACM, 1990.  https://doi.org/10.1145/100216.100254.
  * [3] Brenda S. Baker.  Approximation algorithms for np-complete problems on planar graphs.  J. ACM, 41(1):153–180, 1994.  https://doi.org/10.1145/174644.174650.
  * [4] Piotr Berman and Marek Karpinski.  On some tighter inapproximability results (extended abstract).  In Automata, Languages and Programming, 26th International Colloquium, ICALP’99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 200–209. Springer, 1999.  https://doi.org/10.1007/3-540-48523-6_17.
  * [5] Bruno Courcelle.  The monadic second-order logic of graphs. i. recognizable sets of finite graphs.  Inf. Comput., 85(1):12–75, 1990.  https://doi.org/10.1016/0890-5401(90)90043-H.
  * [6] Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt.  Approximation schemes for first-order definable optimisation problems.  In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings, pages 411–420. IEEE Computer Society, 2006.  https://doi.org/10.1109/LICS.2006.13.
  * [7] Erik D. Demaine and Mohammad Taghi Hajiaghayi.  Bidimensionality: new connections between FPT algorithms and ptass.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 590–601. SIAM, 2005.  http://dl.acm.org/citation.cfm?id=1070432.1070514.
  * [8] Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce A. Reed, Paul D. Seymour, and Dirk Vertigan.  Excluding any graph as a minor allows a low tree-width 2-coloring.  J. Comb. Theory, Ser. B, 91(1):25–41, 2004.  https://doi.org/10.1016/j.jctb.2003.09.001.
  * [9] Zdenek Dvorák.  Sublinear separators, fragility and subexponential expansion.  Eur. J. Comb., 52:103–119, 2016.  https://doi.org/10.1016/j.ejc.2015.09.001.
  * [10] Zdenek Dvorák.  On classes of graphs with strongly sublinear separators.  Eur. J. Comb., 71:1–11, 2018.  https://doi.org/10.1016/j.ejc.2018.02.032.
  * [11] Zdenek Dvorák.  Thin graph classes and polynomial-time approximation schemes.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1685–1701. SIAM, 2018.  https://doi.org/10.1137/1.9781611975031.110.
  * [12] Zdenek Dvorák.  Baker game and polynomial-time approximation schemes.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2227–2240. SIAM, 2020.  https://doi.org/10.1137/1.9781611975994.137.
  * [13] Zdenek Dvorák.  Approximation metatheorem for fractionally treewidth-fragile graphs.  CoRR, abs/2103.08698, 2021.  https://arxiv.org/abs/2103.08698.
  * [14] Zdenek Dvorák and Sergey Norin.  Strongly sublinear separators and polynomial expansion.  SIAM J. Discret. Math., 30(2):1095–1101, 2016.  https://doi.org/10.1137/15M1017569.
  * [15] Thomas Erlebach, Klaus Jansen, and Eike Seidel.  Polynomial-time approximation schemes for geometric intersection graphs.  SIAM J. Comput., 34(6):1302–1323, 2005.  https://doi.org/10.1137/S0097539702402676.
  * [16] Sariel Har-Peled and Kent Quanrud.  Approximation algorithms for polynomial-expansion and low-density graphs.  SIAM J. Comput., 46(6):1712–1744, 2017.  https://doi.org/10.1137/16M1079336.
  * [17] Robert Krauthgamer and James R. Lee.  The intrinsic dimensionality of graphs.  Comb., 27(5):551–585, 2007.  https://doi.org/10.1007/s00493-007-2183-y.
  * [18] Richard J. Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM J. Appl. Math., 36(2):177–189, 1979.  https://doi.org/10.1137/0136016.
  * [19] Richard J. Lipton and Robert Endre Tarjan.  Applications of a planar separator theorem.  SIAM J. Comput., 9(3):615–627, 1980.  https://doi.org/10.1137/0209046.
  * [20] Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis.  Separators for sphere-packings and nearest neighbor graphs.  J. ACM, 44(1):1–29, 1997.  https://doi.org/10.1145/256292.256294.
  * [21] Jaroslav Nesetril and Patrice Ossona de Mendez.  Grad and classes with bounded expansion II. algorithmic aspects.  Eur. J. Comb., 29(3):777–791, 2008.  https://doi.org/10.1016/j.ejc.2006.07.014.
  * [22] Jaroslav Nesetril and Patrice Ossona de Mendez.  Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics.  Springer, 2012.  https://doi.org/10.1007/978-3-642-27875-4.