# A polynomial-time $\text{OPT}^{\varepsilon}$-approximation algorithm for
maximum independent set of connected subgraphs in a planar graph

Jana Cslovjecsek111EPFL, Switzerland<EMAIL_ADDRESS>Michał
Pilipczuk222Institute of Informatics, University of Warsaw, Poland,
<EMAIL_ADDRESS>This work is a part of the project BOBR that
has received funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No 948057). Karol Węgrzycki333Saarland University and Max Planck
Institute for Informatics, Saarbrücken, Germany<EMAIL_ADDRESS>This work is part of the project TIPEA that has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No 850979).

###### Abstract

In the Maximum Independent Set of Objects problem, we are given an $n$-vertex
planar graph $G$ and a family $\mathcal{D}$ of $N$ _objects_ , where each
object is a connected subgraph of $G$. The task is to find a subfamily
$\mathcal{F}\subseteq\mathcal{D}$ of maximum cardinality that consists of
pairwise disjoint objects. This problem is $\mathsf{NP}$-hard and is
equivalent to the problem of finding the maximum number of pairwise disjoint
polygons in a given family of polygons in the plane.

As shown by Adamaszek et al. (J. ACM ’19), the problem admits a _quasi-
polynomial time approximation scheme_ (QPTAS): a
$(1-\varepsilon)$-approximation algorithm whose running time is bounded by
$2^{\mathrm{poly}(\log(N),1/\epsilon)}\cdot n^{\mathcal{O}(1)}$. Nevertheless,
to the best of our knowledge, in the polynomial-time regime only the trivial
$\mathcal{O}(N)$-approximation is known for the problem in full generality. In
the restricted setting where the objects are pseudolines in the plane, Fox and
Pach (SODA ’11) gave an $N^{\varepsilon}$-approximation algorithm with running
time $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$.

In this work, we present an $\text{OPT}^{\varepsilon}$-approximation algorithm
for the problem that runs in time
$N^{\tilde{\mathcal{O}}(1/\varepsilon^{2})}n^{\mathcal{O}(1)}$, for any
$\varepsilon>0$, thus improving upon the result of Fox and Pach both in terms
of generality and in terms of the running time. Our approach combines the
methodology of _Voronoi separators_ , introduced by Marx and Pilipczuk (TALG
’22), with a new analysis of the approximation factor.

##  1 Introduction

Maximum Independent Set is a fundamental optimization problem defined as
follows: Given a graph $G$, find a vertex subset $I\subseteq V(G)$ of maximum
cardinality such that no two vertices in $I$ are adjacent. The problem is
$\mathsf{NP}$-complete and in full generality, very hard to approximate: as
proved by Håstad [15], there is no $|V(G)|^{1-\varepsilon}$-approximation
algorithm running in polynomial time for any $\varepsilon>0$, assuming
$\mathsf{NP}\neq\mathsf{ZPP}$.

Therefore, special cases of the problem were investigated with the hope of
finding more positive results. In this work we study the Maximum Independent
Set of Objects problem, which boils down to Independent Set in intersection
graphs of families of connected subgraphs of a planar graph. More precisely,
the input consists of a planar $n$-vertex graph $G$ and a set $\mathcal{D}$ of
$N$ connected subgraphs of $G$, further called objects. The task is to find a
maximum size subset $\mathcal{F}\subseteq\mathcal{D}$ such that objects in
$\mathcal{F}$ are pairwise disjoint.

As observed in [20], the Maximum Independent Set of Objects problem is
equivalent to the geometric problem of finding the maximum number of pairwise
disjoint polygons in a given family of polygons in the plane. The latter
formulation is one of the oldest problems in computational geometry, with many
applications, for instance in cartography [5, 11, 22], interval scheduling
[21], chip manufacturing [16], and even cellular networks [17].

The problem has also received significant attention from the theoretical
community. For example, when objects are _fat_ (e.g., disks or squares),
polynomial-time approximation schemes (PTASes) are known. The standard
approach [10] relies on the quadtree combined with dynamic programming by
Arora [6]. Other approaches include the usage of the planar separator theorem
(see [7]) or local search strategies [8]; however, all of these developments
crucially rely on the geometric assumption of the fatness of the objects.
Another geometric setting that has been heavily studied is when all objects
are axis-parallel rectangles. No PTAS is known for this case, while constant-
factor approximation algorithms were proposed only very recently [13, 19].

Finally, Fox and Pach [12] considered the case when the considered objects
form a family of pseudolines. More generally, they assumed the objects to be
non-self-crossing curves in the plane such that any two of them intersect in
at most $k$ points, where $k$ is a constant. For this case, they gave an
$N^{\varepsilon}$-approximation algorithm with a running time
$N^{2^{\widetilde{\mathcal{O}}_{k}(1/\varepsilon)}}$; the running time is
independent of $N$, as their algorithm does not need to rely on any geometric
representation and can be given on input only the intersection graph of the
objects. The result of Fox and Pach improved the earlier work of Agarwal and
Mustafa [4], who gave an $N^{1/2+o(1)}$-approximation algorithm with a running
time $\mathcal{O}(N^{3})$ for the special case of segments in the plane.

Surprisingly, if one is willing to use time slightly higher than polynomial,
then much better approximation factors can be achieved. A recent line of work
due to Adamaszek, Har-Peled, and Wiese [1, 2, 3] gave a _quasipolynomial-time
approximation scheme_ (QPTAS) for Maximum Independent Set of Objects in full
generality with a running time $2^{\mathrm{poly}(\log(N),\varepsilon)}\cdot
n^{\mathcal{O}(1)}$. See also the work of Pilipczuk et al. [20] for a somewhat
streamlined presentation in the planar setting. Despite that, to the best of
our knowledge, for the general Maximum Independent Set of Objects problem, the
best approximation factor known to be achievable in polynomial time is the
trivial $N$-approximation: pack one object.

#### Our contribution.

In this work, we give a polynomial-time approximation algorithm for the
Maximum Independent Set of Objects problem in full generality with a non-
trivial approximation factor.

######  Theorem 1.1.

For every $\varepsilon>0$, Maximum Independent Set of Objects admits an
$\text{OPT}^{\varepsilon}$-approximation algorithm running in time
$N^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}\cdot n^{\mathcal{O}(1)}$,
where $N$ is the number of input objects, $n$ is the vertex count of the input
graph, and OPT is the cardinality of an optimum solution.

Observe that Theorem 1.1 improves the result of Fox and Pach [12] in terms of
the running time ($N^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}\cdot
n^{\mathcal{O}(1)}$ instead of
$N^{2^{\widetilde{\mathcal{O}}_{k}(1/\varepsilon)}}$), in terms of the
approximation factor ($\text{OPT}^{\varepsilon}$ instead of
$N^{\varepsilon}$), and in terms of generality (we do not assume the objects
to be curves that pairwise intersect in at most $k$ points). The caveat is
that our algorithm has to be provided a representation of the input consisting
of a planar graph $G$ and a family of objects $\mathcal{D}$ in $G$, while the
algorithm of Fox and Pach can rely only on the intersection graph of
$\mathcal{D}$.

#### Our techniques.

The backbone of our proof of Theorem 1.1 is the separator approach used for
the design of QPTASes [1, 2, 3, 20]. The crux of this approach lies in the
existence of a light separator, which splits the solution in a balanced way
and interacts with only a small fraction of the solution. The following
informal statement sketches the main properties of such a separator. For a
formalization, see e.g. [20, Lemma 3].

######  Lemma 1.2 (Light Separator Lemma).

Let $(G,\mathcal{D})$ be an instance of Maximum Independent Set of Objects,
$\mathcal{F}\subseteq\mathcal{D}$ be any independent set of objects, and
$\delta>0$ be an accuracy parameter. Then there exists a separator $S$ in $G$
of complexity $\mathrm{poly}(1/\delta)$ such that $S$ intersects at most
$\delta|\mathcal{F}|$ objects in $\mathcal{F}$ and $S$ breaks $\mathcal{F}$
into subsets of size at most $\frac{2}{3}|\mathcal{F}|$.

In the above statement we did not specify the precise notion of a separator
that we use, the definition of its complexity, and what it means for
$\mathcal{F}$ to be split by a separator. Following Pilipczuk et al. [20], in
this work, we use the notion of a radial separator, which is essentially a
cycle separator in the radial graph of the Voronoi diagram induced by the
solution $\mathcal{F}$. Importantly, there are only
$|\mathcal{D}|^{\mathcal{O}(\ell)}$ candidates for a radial separator of
complexity at most $\ell$, hence the separator $S$ whose existence is asserted
by Lemma 1.2 can be guessed among $|\mathcal{D}|^{\mathrm{poly}(1/\delta)}$
candidates.

The existence of balanced light separators suggests a simple recursive
strategy: guess a balanced light separator $S$ of the optimum solution
$\mathcal{F}$, sacrifice objects intersected by $S$, and recurse on
subproblems based on $S$. This strategy is applied until the optimum solution
size is $\mathrm{poly}(1/\varepsilon)$, in which case an optimum solution can
be found by brute-force. Clearly, the recursion depth is $\mathcal{O}(\log N)$
and it is not hard to see that every level of the recursion may incur a loss
of a $\delta$-fraction of the optimum solution $\mathcal{F}$. Consequently,
one needs to set $\delta=\frac{\varepsilon}{\log N}$ to make sure that the
total loss is bounded by $\varepsilon|\mathcal{F}|$, and hence all the
separators within the algorithm need to be guessed among quasi-polynomially
many candidates. This is the fundamental reason why the algorithms of [1, 2,
3, 20] are QPTASes, and not PTASes.

Our proof of Theorem 1.1 relies on the same concept of balanced light
separators provided by Lemma 1.2, but both the algorithm and the analysis of
the approximation factor are very different. In essence, we set
$\delta=\mathrm{poly}(1/\varepsilon)$ instead of
$\delta=\mathrm{poly}(1/\varepsilon,\log N)$ and use balanced light separators
for such $\delta$ to form a hierarchical decomposition of the optimum solution
$\mathcal{F}$ using so-called Swiss-cheese separators of total complexity
$\mathrm{poly}(1/\varepsilon)$; each Swiss-cheese separator consists of
several radial separators. Importantly, at every step of the decomposition, we
use two radial separators to split in a balanced way both the currently
considered part of $\mathcal{F}$ and the radial separators “stacked” by the
previous levels of the recursion. This way, the total complexity of each
Swiss-cheese separator present in the decomposition is bounded by
$\mathrm{poly}(1/\varepsilon)$. We note that this stacking problem did not
really arise in the QPTASes of [1, 2, 3, 20], because there one can afford an
additional $\log N$ factor in the total size of the separators stacked during
the recursion, and the recursion tree has depth $\mathcal{O}(\log N)$ anyway.

Once the existence of a hierarchical decomposition as above is argued, we
perform careful dynamic programming that guesses the decomposition “on the
fly” and at the same time computes an approximate solution to the problem. The
main novelty here lies in a new analysis of the approximation factor: we show
that an $\mathrm{OPT}^{\varepsilon}$-bound on the approximation factor can be
proved by induction on the hierarchical decomposition, even without exploiting
any bound on the depth of this decomposition.

#### Organization.

In Section 2 we recall the machinery of Voronoi diagrams and separators due to
Marx and Pilipczuk [18]. Section 3 introduces the notion of a Swiss-cheese
separator and provides a balanced separator theorem for them. In Section 4 we
gather all the tools and prove Theorem 1.1. Proofs of statements marked with
$\bigstar$ are deferred to Appendices A and B.

##  2 Basic toolbox

In this section, we recall the basic toolbox introduced in [18, 20].
Therefore, the text in this section is largely a paraphrase and an adaptation
of the corresponding sections of [18, 20], and serves as an introduction to
the methodology of Marx and Pilipczuk [18]. We remark that this methodology
was also used by Cohen-Addad, Pilipczuk, and Pilipczuk [9] in the context of
facility location problems in planar graphs.

Recall that in the Maximum Independent Set of Objects problem the input
consists of a planar graph $G$ and a family of objects $\mathcal{D}$, where
each object is a connected subgraph of $G$. We fix such an instance for the
remainder of the paper. Further, we fix an embedding of $G$ in the sphere
$\mathbb{S}^{2}$ and by triangulating every face, we assume that $G$ is a
triangulation. For the purpose of defining Voronoi diagrams on $G$, it will be
convenient to impose a distance metric in $G$. For this, we assume that each
edge $uv$ of $G$ is assigned a positive length, so that we may consider the
shortest path metric in $G$, denoted $\mathrm{dist}(\cdot,\cdot)$. By
perturbing the edge lengths slightly, we can make sure that all distances
between pairs of vertices in $G$ are pairwise different; handling this
perturbation increases the running times of our algorithms by only a
polynomial factor. Note that thus, shortest paths are unique in $G$.

Let $\mathcal{F}\subseteq\mathcal{D}$ be an independent set in $\mathcal{D}$,
that is, a subfamily consisting of pairwise disjoint objects. We first define
the Voronoi partition: it is the partition of $V(G)$ into Voronoi cells
$\\{\mathrm{Vor}_{\mathcal{F}}(p)\colon p\in\mathcal{F}\\}$ such that
$\mathrm{Vor}_{\mathcal{F}}(p)$ consists of vertices $u$ of $G$ such that
$\mathrm{dist}(u,p)<\mathrm{dist}(u,p^{\prime})$ for all
$p^{\prime}\in\mathcal{F}$, $p^{\prime}\neq p$. Here, for a vertex $u$ and an
object $p$ we denote $\mathrm{dist}(u,p)\coloneqq\min_{v\in
p}\mathrm{dist}(u,v)$. As the distances in $G$ are pairwise different, there
are no ties.

Now comes the key definition from [18], that of the Voronoi diagram of an
independent set $\mathcal{F}\subseteq\mathcal{D}$. Such a diagram
$\mathrm{Diag}_{\mathcal{F}}$ is constructed through a three-step process:

  1. (i)

For every $p\in\mathcal{F}$, fix an arbitrary spanning tree $T(p)$ of $p$.
Then extend $T(p)$ to a spanning tree $\widehat{T}(p)$ of
$G[\mathrm{Vor}_{\mathcal{F}}(p)]$ by adding, for every
$u\in\mathrm{Vor}_{\mathcal{F}}(p)$, a shortest path from $u$ to $p$.

  2. (ii)

Take the dual $G^{\star}$ of $G$ and remove from $G^{\star}$ all the edges
dual to the edges of $\widehat{T}(p)$, for every $p\in\mathcal{F}$.

  3. (iii)

From the obtained graph iteratively remove vertices of degree $1$ and bypass
vertices of degree $2$, where bypassing a vertex of degree $2$ means replacing
it together with the incident edges with a new edge connecting the neighbors.
Once these operations are applied exhaustively, the multigraph obtained at the
end is the Voronoi diagram $\mathrm{Diag}_{\mathcal{F}}$.

As proved in [18, Lemmas 4.4, 4.5 and Section 4.4], the diagram
$\mathrm{Diag}_{\mathcal{F}}$ is a $3$-regular connected multigraph with a
sphere embedding naturally inherited from $G$ ($3$-regularity follows from the
assumption that $G$ is triangulated). Moreover, $\mathrm{Diag}_{\mathcal{F}}$
has exactly $|\mathcal{F}|$ faces that bijectively correspond to the objects
of $\mathcal{F}$, in the sense that each object $p\in\mathcal{F}$ is the
unique object of $\mathcal{F}$ that is entirely contained in the face of
$\mathrm{Diag}_{\mathcal{F}}$ corresponding to $p$. The vertices of
$\mathrm{Diag}_{\mathcal{F}}$ are called branching points. Note that every
branching point $f$ is actually a (triangular) face of the original graph $G$,
and the duals of three edges of $f$ participate in the three different edges
of $\mathrm{Diag}_{\mathcal{F}}$ that are incident with $f$.

#### Singular faces.

Next, we recall the notion of singular faces, which characterize candidates
for branching points in a diagram. The following is a paraphrase of the
definition from [18].

A face $f$ of $G$ is a singular face of type $1$ for a triple of disjoint
objects $\mathcal{P}=\\{p_{1},p_{2},p_{3}\\}\subseteq\mathcal{D}$ if the
vertices of $f$ belong to pairwise different cells of the Voronoi partition
$\mathrm{Vor}_{\mathcal{P}}$. Next, $f$ is a singular face of type $2$ for
such a triple $\mathcal{P}$ if two vertices $u_{1},u_{2}$ of $f$ belong to
$\mathrm{Vor}_{\mathcal{P}}(p_{1})$, the third vertex $u_{3}$ of $f$ belongs
to $\mathrm{Vor}_{\mathcal{P}}(p_{2})$, and the cycle formed by closing the
$u_{1}$-$u_{2}$ path in $\widehat{T}(p_{1})$ using the edge $u_{1}u_{2}$ of
$f$ separates $p_{2}$ and $p_{3}$ on $\mathbb{S}^{2}$. Finally, $f$ is a
singular face of type $3$ for a quadruple of disjoint objects
$\mathcal{P}=\\{p_{0},p_{1},p_{2},p_{3}\\}\subseteq\mathcal{D}$ if all
vertices of $f$ belong to $\mathrm{Vor}_{\mathcal{P}}(p_{0})$, but objects
$p_{1},p_{2},p_{3}$ are pairwise separated on the sphere by the union of the
edges of $f$ and the minimal subtree of $\widehat{T}(p_{0})$ that connects the
vertices of $f$. See Fig. 1.

$p_{1}$$p_{2}$$p_{3}$$f$

$p_{1}$$p_{2}$$p_{3}$$u_{3}$$u_{2}$$u_{1}$$f$

$p_{1}$$p_{2}$$p_{0}$$p_{3}$$u_{3}$$u_{2}$$u_{1}$$f$

Figure 1: Singular faces of types 1, 2 and 3. Relevant spokes depicted in
gray. Figure reproduced from [18], with the consent of the authors.

We will need the following two statements from [18]: there are few candidates
for singular faces, and branching points of any diagram are always singular
faces.

######  Lemma 2.1 (Lemmas 4.8,4.9 and 4.10 in [18]).

For each independent triple of objects $(p_{1},p_{2},p_{3})$ there are at most
two singular faces of type $1$ for $(p_{1},p_{2},p_{3})$, and at most one
singular face of type $2$ for $(p_{1},p_{2},p_{3})$. For each independent
quadruple of objects $(p_{0},p_{1},p_{2},p_{3})$, there is at most one
singular face of type $3$ for $(p_{0},p_{1},p_{2},p_{3})$.

######  Lemma 2.2 (Lemma 4.12 in [18]).

Let $\mathcal{F}\subseteq\mathcal{D}$ be an independent set of objects, and
let $\mathrm{Diag}_{\mathcal{F}}$ be the Voronoi diagram of $\mathcal{F}$.
Then, every branching point of $\mathrm{Diag}_{\mathcal{F}}$ is either a
type-$1$ singular face for some triple of objects from $\mathcal{F}$, or a
type-$2$ singular face for some triple of objects from $\mathcal{F}$, or a
type-$3$ singular face for some quadruple of objects from $\mathcal{F}$.

#### Radial graph.

Next, we present the radial graph $\mathrm{Rad}_{\mathcal{F}}$ of the diagram
$\mathrm{Diag}_{\mathcal{F}}$ (see [18, 20]). This is the bipartite multigraph
whose vertex set consists of the objects of $\mathcal{F}$ (which, recall,
correspond to the faces of $\mathrm{Diag}_{\mathcal{F}}$) and the vertices of
$\mathrm{Diag}_{\mathcal{F}}$ (that is, branching points). For every branching
point $f$ and every vertex $u$ of $f$, we create in
$\mathrm{Diag}_{\mathcal{F}}$ one edge between $f$ and the unique object
$p\in\mathcal{F}$ such that $u\in\mathrm{Vor}_{\mathcal{F}}(p)$. For
convenience, this edge of $\mathrm{Rad}_{\mathcal{F}}$ will be labelled by the
vertex $u$. Note that $\mathrm{Rad}_{\mathcal{F}}$ may contain two or more
edges connecting the same object $p$ and a branching point $f$; this happens
when $\mathrm{Diag}_{\mathcal{F}}$ is incident to one or more bridges.
However, every branching point will have degree exactly $3$ in
$\mathrm{Rad}_{\mathcal{F}}$.

Consider an edge $pf$ of $\mathrm{Rad}_{\mathcal{F}}$ with label $u\in f$. The
spoke induced by $pf$ in the diagram $\mathrm{Diag}_{\mathcal{F}}$ is the
shortest path $P$ from $u$ to the (nearest vertex of) object $p$. Note that
$P$ is entirely contained in the tree $\widehat{T}(p)$, which means that it is
also entirely contained in the face of $\mathrm{Diag}_{\mathcal{F}}$
corresponding to $p$. We can now use those spokes to define a natural
embedding of $\mathrm{Rad}_{\mathcal{F}}$ in $\mathbb{S}^{2}$: take the
subgraph of $G$ consisting of all branching points, all objects of
$\mathcal{F}$, and all spokes of $\mathrm{Diag}_{\mathcal{F}}$, contract the
branching points and the objects of $\mathcal{F}$ to single vertices, and
contract the spokes of $\mathrm{Diag}_{\mathcal{F}}$ to single edges.

If $P$ is a spoke induced in $\mathrm{Diag}_{\mathcal{F}}$, corresponding to
an edge $pf$ of $\mathrm{Rad}_{\mathcal{F}}$, and $q\in\mathcal{D}$, $q\neq
p$, is another object, then we say that $q$ is in conflict with $P$ if there
exists a vertex $v$ on $P$ such that $\mathrm{dist}(v,q)<\mathrm{dist}(v,p)$.
Note that then we necessarily have $q\notin\mathcal{F}$, as $P$ is entirely
contained in the cell $\mathrm{Vor}_{\mathcal{F}}(p)$. If $H$ is a subgraph of
$\mathrm{Rad}_{\mathcal{F}}$, then we say that $q$ is _in conflict_ with $H$
if $q$ is in conflict with any spoke induced by an edge of $H$.

In the sequel, we will often work with cycles in the radial graph
$\mathrm{Rad}_{\mathcal{F}}$. Every such cycle $C$ consists of consecutive
edges
$p_{1}f_{1},f_{1}p_{2},p_{2}f_{2},f_{2}p_{3},\ldots,p_{\ell}f_{\ell},f_{\ell}p_{1}$,
where $p_{1},\ldots,p_{\ell}$ are objects visited by $C$,
$f_{1},\ldots,f_{\ell}$ are branching points visited by $C$, and the length of
$C$ is $2\ell$. For such a cycle $C$, we define a closed walk $\Gamma(C)$ in
$G$ by concatenating in the natural order (indices behave cyclically):

  * •

the spokes induced by the edges of $C$;

  * •

for every object $p_{i}$, the unique path within $T(p_{i})$ between the
endpoints of the spokes induced by $p_{i}f_{i}$ and $f_{i-1}p_{i}$ belonging
to $p_{i}$; and

  * •

for every branching point $f_{i}$, the edge of $f_{i}$ connecting the
endpoints of the spokes induced by $p_{i}f_{i}$ and $f_{i}p_{i+1}$ belonging
to $f_{i}$.

It is easy to observe that $\Gamma(C)$ is indeed a closed walk in $G$.
Moreover, the removal of $\Gamma(C)$ from $\mathbb{S}^{2}$ breaks
$\mathbb{S}^{2}$ into two connected regions that naturally correspond to the
two sides of the cycle $C$.

Finally, observe that for every edge $e=fg$ of $\mathrm{Diag}_{\mathcal{F}}$
there is a unique face of $\mathrm{Rad}_{\mathcal{F}}$ that contains $e$; this
face is a $4$-cycle $pfqg$, where $p,q$ are objects of $\mathcal{F}$
corresponding to the faces of $\mathrm{Diag}_{\mathcal{F}}$ on both sides of
$e$. (Note that possibly $f=g$ or $p=q$.) The face under consideration will be
called the diamond of $e$ and denoted $\diamondsuit_{\mathcal{F}}(e)$. Note
that thus, the sphere $\mathbb{S}^{2}$ is divided into diamonds
$\\{\diamondsuit_{\mathcal{F}}(e)\colon e\in
E(\mathrm{Diag}_{\mathcal{F}})\\}$. We will often implicitly identify the
diamond $\diamondsuit_{\mathcal{F}}(e)$ with the connected region of
$\Gamma(\diamondsuit_{\mathcal{F}}(e))$ that contains $e$.

#### Radial separators.

We now introduce the main separator notion that will be used in this work.
Essentially, these separators correspond to the Voronoi separators of Marx and
Pilipczuk [18], but it will be convenient to set up the definitional layer a
bit differently.

A _radial separator_ $S$ is a pair $(\mathcal{P},C)$, where
$\mathcal{P}\subseteq\mathcal{D}$ is an independent set of objects and $C$ is
a cycle in $\mathrm{Rad}_{\mathcal{P}}$. The _length_ of $S$ is the length of
$C$, and we denote $\Gamma(S)\coloneqq\Gamma(C)$.

We say that a radial separator $S=(\mathcal{P},C)$ is _compatible_ with an
independent set $\mathcal{F}\subseteq\mathcal{D}$ if
$\mathcal{P}\subseteq\mathcal{F}$ and each spoke of
$\mathrm{Diag}_{\mathcal{P}}$ that is incident with a branching point on $C$
is not in conflict with any $q\in\mathcal{F}-\mathcal{P}$. We will use the
following claim about persistence of branching points under addition of non-
conflicting objects.

######  Lemma 2.3.

Let $\mathcal{P}\subseteq\mathcal{F}$ be independent sets of objects in
$\mathcal{D}$. Further, let $f$ be a branching point in
$\mathrm{Diag}_{\mathcal{P}}$ such that none of the three spokes incident to
$f$ in $\mathrm{Diag}_{\mathcal{P}}$ is in conflict with any of the objects of
$\mathcal{F}-\mathcal{P}$. Then $f$ is also a branching point in
$\mathrm{Diag}_{\mathcal{F}}$ and all spokes of $\mathrm{Diag}_{\mathcal{P}}$
incident with $f$ persist as spokes of $\mathrm{Diag}_{\mathcal{F}}$ incident
with $f$.

###### Proof.

Since the spokes of $\mathrm{Diag}_{\mathcal{P}}$ incident with $f$ are not in
conflict with any object of $\mathcal{F}-\mathcal{P}$, they persist as
shortest paths within the cells of the same objects in
$\mathrm{Vor}_{\mathcal{F}}$, as compared to $\mathrm{Vor}_{\mathcal{P}}$. In
particular, every vertex of $f$ is in the cell of the same object in
$\mathrm{Vor}_{\mathcal{F}}$ as in $\mathrm{Vor}_{\mathcal{P}}$. Now, consider
any two distinct vertices $u,v$ of $f$. If $u,v$ belong to different cells in
$\mathrm{Vor}_{\mathcal{P}}$, equivalently in $\mathrm{Vor}_{\mathcal{F}}$,
then the dual of the edge $uv$ is for sure not removed in the iterative
removal of vertices of degree $1$ in the construction of
$\mathrm{Diag}_{\mathcal{F}}$, because in this process we remove only duals of
edges connecting vertices from the same cell. On the other hand, if $u,v$
belong to the same cell in $\mathrm{Diag}_{\mathcal{P}}$, say of object $p$,
then the cycle $L$ obtained by concatenating the edge $uv$ of $f$ with the
$u$-$v$ path in $\widehat{T}(p)$ must separate some two objects of
$\mathcal{P}$, hence it separates some two objects of $\mathcal{F}$ as well
due to $\mathcal{F}\supseteq\mathcal{P}$. In the construction of
$\mathrm{Vor}_{\mathcal{F}}$, again $uv$ is the only edge on the cycle $L$
that does not belong to $\widehat{T}(p)$. As $L$ separates two objects of
$\mathcal{F}$, it is easy to see that in the iterative removal of vertices of
degree $1$ in the construction of $\mathrm{Diag}_{\mathcal{F}}$, the dual of
the edge $uv$ also could not be removed. All in all, none of the duals of the
edges of the face $f$ was removed in the construction of
$\mathrm{Diag}_{\mathcal{F}}$, which means that $f$ remains a vertex of degree
$3$ in $\mathrm{Diag}_{\mathcal{F}}$, hence a branching point. Then the spokes
incident to $f$ in $\mathrm{Diag}_{\mathcal{P}}$ also remain spokes incident
to $f$ in $\mathrm{Diag}_{\mathcal{F}}$, because the vertices of $f$ are in
the cells of the same objects in $\mathrm{Vor}_{\mathcal{F}}$ as in
$\mathrm{Vor}_{\mathcal{P}}$. ∎

We first verify that extending the family of objects in a radial separator to
a compatible superset still yields a radial separator. This is because, by
definition, no spoke defining the separator can cease to be a spoke when
adding the additional objects.

######  Lemma 2.4.

Let $S=(\mathcal{P},C)$ be a radial separator and suppose $S$ is compatible
with $\mathcal{F}\subseteq\mathcal{D}$. Then each branching point on $C$ is
also a branching point on $\mathrm{Diag}_{\mathcal{F}}$. Moreover, $C$ is also
a cycle in $\mathrm{Rad}_{\mathcal{F}}$, which means that $(\mathcal{F},C)$ is
also a radial separator.

###### Proof.

Let $K$ be the set of spokes induced in $\mathrm{Diag}_{\mathcal{P}}$ that are
incident with the branching points visited by $C$. Since $S$ is compatible
with $\mathcal{F}$, it holds that $\mathcal{P}\subseteq\mathcal{F}$ and every
spoke in $K$ is not in conflict with any object of $\mathcal{F}-\mathcal{P}$.
By Lemma 2.3, all branching points traversed by $C$ persist as branching
points in $\mathrm{Diag}_{\mathcal{F}}$, and all spokes of $K$ persist as
spokes connecting the same objects and branching points in
$\mathrm{Diag}_{\mathcal{F}}$. The latter in particular applies to all spokes
corresponding to the edges of $C$. We conclude that all objects, branching
points, and edges between them that are traversed by $C$ in
$\mathrm{Rad}_{\mathcal{P}}$ persist intact in $\mathrm{Rad}_{\mathcal{F}}$.
So $C$ is also a cycle in $\mathrm{Rad}_{\mathcal{F}}$ and $(\mathcal{F},C)$
is a radial separator. ∎

Finally, we show that for the purpose of defining a radial separator $S$, one
can always restrict attention to a small set of objects relevant to the
branching points visited by $S$.

######  Lemma 2.5.

Let $(\mathcal{P},C)$ be a radial separator of length $\ell$. Then there
exists $\mathcal{P}^{\prime}\subseteq\mathcal{P}$ such that
$|\mathcal{P}^{\prime}|\leqslant\frac{5}{2}\ell$, $C$ is also a cycle in the
radial graph $\mathrm{Rad}_{\mathcal{P}^{\prime}}$, and
$(\mathcal{P}^{\prime},C)$ is a radial separator compatible with
$\mathcal{P}$.

###### Proof.

Let $\mathcal{P}^{\prime}$ consist of:

  * •

the $\ell/2$ objects traversed by $C$; and

  * •

for each of the $\ell/2$ branching points $f$ traversed by $C$, the set
$\mathcal{P}_{f}\subseteq\mathcal{P}$ consisting of three or four objects of
$\mathcal{P}$ that define $f$ in the sense of Lemma 2.2.

Thus, $|\mathcal{P}^{\prime}|\leqslant\frac{5}{2}\ell$.

Consider any branching point $f$ of $\mathrm{Diag}_{\mathcal{P}}$ traversed by
$C$. By the property provided by Lemma 2.2, $f$ is also a branching point in
$\mathrm{Diag}_{\mathcal{P}_{f}}$, and the construction in the proof of Lemma
2.2 in [18] actually shows that the spokes of
$\mathrm{Diag}_{\mathcal{P}_{f}}$ incident to $f$ are the same as the spokes
of $\mathrm{Diag}_{\mathcal{P}}$ incident to $f$. Since
$\mathcal{P}^{\prime}\supseteq\mathcal{P}_{f}$ and none of the objects of
$\mathcal{P}^{\prime}-\mathcal{P}_{f}$ is in conflict with any of those spokes
(because they are spokes in $\mathrm{Diag}_{\mathcal{P}}$ and
$\mathcal{P}^{\prime}\subseteq\mathcal{P}$), by Lemma 2.3 we conclude that $f$
remains a branching point in $\mathrm{Diag}_{\mathcal{P}^{\prime}}$, and all
spokes of $\mathrm{Diag}_{\mathcal{P}}$ incident with $f$ are also spokes of
$\mathrm{Diag}_{\mathcal{P}^{\prime}}$ incident with $f$. This in particular
applies to the two spokes corresponding to the edges of $C$ incident with $f$.

Hence, all objects, branching points, and edges between them that are
traversed by $C$ in $\mathrm{Rad}_{\mathcal{P}}$ persist intact in
$\mathrm{Rad}_{\mathcal{P}^{\prime}}$, and $C$ is also a cycle in
$\mathrm{Rad}_{\mathcal{P}^{\prime}}$. Finally, that all objects of
$\mathcal{P}-\mathcal{P}^{\prime}$ are not in conflict with the spokes of
$\mathrm{Diag}_{\mathcal{P}^{\prime}}$ incident with the branching points
traversed by $C$ follows immediately from the construction, as these spokes
are entirely contained in
$\bigcup_{p\in\mathcal{P}^{\prime}}\mathrm{Vor}_{\mathcal{P}}(p)$. Hence
$(\mathcal{P}^{\prime},C)$ is a radial separator compatible with
$(\mathcal{P},C)$. ∎

##  3 Swiss-cheese separators

The building blocks of our dynamic programming are captured through the
following notion. Here, two cycles in $\mathbb{S}^{2}$ are non-crossing if
there exists a homotopy that deforms one cycle into the other without any
intersections.

Figure 2: A schematic overview of a Swiss-cheese separator. The orange circles
represent objects of $\mathcal{P}$. The triangular faces are the branching
points of $\mathrm{Diag}_{\mathcal{F}}$. The yellow area (cheese mass) is the
face $f$, while green parts (holes) are the regions excluded by the cycles of
$\mathcal{K}$. The figure is built upon [9, Figure 1].

######  Definition 3.1 (Swiss-cheese Separator).

A _Swiss-cheese separator_ is a triple $(\mathcal{P},\mathcal{K},f)$ where
$\mathcal{P}\subseteq\mathcal{D}$ is a set of pairwise disjoint objects,
$\mathcal{K}$ is a set of edge-disjoint non-crossing cycles in
$\mathrm{Diag}_{\mathcal{P}}$, and $f$ is a face of
$\bigcup_{C\in\mathcal{K}}C$ (i.e., the subgraph of
$\mathrm{Diag}_{\mathcal{P}}$ consisting of the union of all the vertices and
edges of all the cycles in $\mathcal{K}$) whose boundary contains every cycle
of $\mathcal{K}$. The complexity of the Swiss-cheese separator
$(\mathcal{P},\mathcal{K},f)$ is the total number of edges of cycles in
$\mathcal{K}$. A Swiss-cheese separator is ripe if
$|\mathcal{P}|\leqslant\frac{5}{2}\ell$, where $\ell$ is its complexity.

In the context of a Swiss-cheese separator $(\mathcal{P},\mathcal{K},C)$, we
will often identify the face $f$ with the corresponding region of
$\mathbb{S}^{2}-\bigcup_{C\in\mathcal{K}}\Gamma(C)$, with the natural meaning
(see Fig. 2).

Note that if $(\mathcal{P},\mathcal{K},C)$ is a Swiss-cheese separator, then
for every $C\in\mathcal{K}$, the pair $(\mathcal{P},C)$ is a radial separator.
The next definition is adapted from [20]. For a $C\in\mathcal{K}$, we say that
an object $p\in\mathcal{D}$ is banned by $C$ if $p$ is in conflict with any
spoke of $\mathrm{Diag}_{\mathcal{P}}$ incident to any branching point
traversed by $C$. We define

$\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)\coloneqq\left\\{\,p\in\mathcal{D}\quad\Big{|}\quad
p\subseteq f,\ p\textrm{ is not banned by any }C\in\mathcal{K}\textrm{ and
}\mathcal{P}\cup\\{p\\}\textrm{ is independent}\right\\}.$

In other words, $\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$ comprises all
objects entirely contained in the region $f$ that are not banned by the radial
separators $(\mathcal{P},C)$, for any $C\in\mathcal{K}$, and are disjoint with
the objects of $\mathcal{P}$. The point of this definition is that for any
$C\in\mathcal{K}$ and $p\in\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$, $p$
is not in conflict with $C$.

Now, let us introduce the following _size_ parameter:

$s\coloneqq
s(\varepsilon)=\frac{10^{10}\ln^{2}(1/\varepsilon)}{\varepsilon^{2}}.$

The main goal of this section is to prove the following separator theorem.

######  Theorem 3.2 (Swiss-cheese Separator Theorem).

Let $\varepsilon>0$ be a small enough parameter and let
$(\mathcal{P},\mathcal{K},f)$ be a ripe Swiss-cheese separator of complexity
at most $s(\varepsilon)$. Let
$\mathcal{F}\subseteq\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$ be a set of
pairwise disjoint objects such that $|\mathcal{F}|\geqslant s(\varepsilon)$.
Then there exists a set of disjoint objects $\mathcal{S}$ with
$\mathcal{P}\subseteq\mathcal{S}\subseteq\mathcal{P}\cup\mathcal{F}$ and
$|\mathcal{S}-\mathcal{P}|\leqslant 2s(\varepsilon)$ and two cycles
$C_{1},C_{2}$ in $\mathrm{Rad}_{\mathcal{S}}$ such that

  1. (a)

at most $\varepsilon|\mathcal{F}|$ objects of $\mathcal{F}$ are in conflict
with $C_{1}$ or $C_{2}$.

Further, let $R$ be a subgraph of $\mathrm{Rad}_{\mathcal{S}}$ consisting of
all the edges and vertices of cycles corresponding to the cycles of
$\mathcal{K}\cup\\{C_{1},C_{2}\\}$ (where cycles of $\mathcal{K}$ are also
cycles in $\mathrm{Rad}_{\mathcal{S}}$ by Lemma 2.4). Then

  1. (b)

for every face $g$ of $R$ satisfying $g\subseteq f$, the region of
$\mathbb{S}^{2}-\bigcup_{C\in\mathcal{K}\cup\\{C_{1},C_{2}\\}}\Gamma(C)$
corresponding to $g$ contains at most $\frac{3}{4}|\mathcal{F}|$ objects of
$\mathcal{F}$, and

  2. (c)

the boundary of every face $g$ of $R$ satisfying $g\subseteq f$ can be
partitioned into edge-disjoint non-crossing cycles in
$\mathrm{Rad}_{\mathcal{S}}$ of total length at most $s(\varepsilon)$, and
therefore $g$ can be represented as some ripe Swiss-cheese separator
$(\mathcal{P}_{g},\mathcal{K}_{g},g)$ of complexity at most $s(\varepsilon)$.

The rest of this section is dedicated to the proof of Theorem 3.2. Therefore,
from now on we fix the ripe Swiss-cheese separator
$(\mathcal{P},\mathcal{K},f)$ and the family
$\mathcal{F}\subseteq\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$. Let $\ell$
be the complexity of $(\mathcal{P},\mathcal{K},f)$; we have $\ell\leqslant
s\leqslant|\mathcal{F}|$. Also, recall that $\mathcal{P}\subseteq\mathcal{D}$
and, as $(\mathcal{P},\mathcal{K},f)$ is ripe, also
$|\mathcal{P}|\leqslant\frac{5}{2}\ell\leqslant\frac{5}{2}s$. We will assume
that $\varepsilon<10^{-100}$, so that we also have $s>10^{10}$.

###  3.1 Sampling

The first step is to construct $\mathcal{S}$. Similarly to [1, 14, 20], we do
this by sampling objects from $\mathcal{F}$. More precisely, first we include
in $\mathcal{S}$ every member of $\mathcal{P}$. Then, for every object
$p\in\mathcal{F}$, we include $p$ in $\mathcal{S}$ independently with
probability $\lambda\coloneqq\frac{s}{|\mathcal{F}|}$. Note that
$\lambda\leqslant 1$, as we assumed that $|\mathcal{F}|\geqslant s$. This
concludes the construction of $\mathcal{S}$. Our first observation is that
with high probability, the size of $\mathcal{S}-\mathcal{P}$ is $\Theta(s)$.
The proof is a standard application of Chernoff’s inequality.

######  Claim 3.3.

With probability at least $\frac{3}{4}$ it holds that
$s/2\leqslant|\mathcal{S}-\mathcal{P}|\leqslant 2s$.

###### Proof.

Let $X$ be the random variable equal to the cardinality of
$\mathcal{S}-\mathcal{P}$. Hence $X=\sum_{p\in\mathcal{F}}X_{p}$, where
$X_{p}$ are random variables that take value $1$ if $p\in\mathcal{F}$ is
included in $\mathcal{S}$ and $0$ otherwise. Note that $X_{p}$ are independent
identically distributed Bernoulli variables with success probability
$\lambda$, and

$\mathbb{E}\left[X\right]=\sum_{p\in\mathcal{F}}\mathbb{E}\left[X_{p}\right]=|\mathcal{F}|\cdot\lambda=s.$

Hence, by Chernoff inequality we conclude that

$\mathbb{P}\left[X<s/2\right]\leqslant
e^{-s/8}\qquad\textrm{and}\qquad\mathbb{P}\left[X>2s\right]\leqslant
e^{-s/3}.$

As we assumed that $s>100$, the probability that any of the above events
happens is bounded by $\frac{1}{4}$. ∎

Next, we analyze the properties of the set $\mathcal{S}$. This will generally
follow the framework of [20, Section 2.2] with the caveat that the objects of
$\mathcal{P}$ are always included in $\mathcal{S}$. We start by arguing that
with high probability, every spoke induced in $\mathrm{Diag}_{\mathcal{S}}$ is
in conflict with only a few objects in $\mathcal{F}$. To measure this, we need
the following definition: we say that a spoke of $\mathrm{Diag}_{\mathcal{S}}$
is _heavy_ if it is in conflict with at least

$\eta\coloneqq\frac{100\ln(1/\varepsilon)}{s}\cdot|\mathcal{F}|\qquad\textrm{objects
in }\mathcal{F}.$

The following statement guarantees that with high probability no spoke is
heavy.

######  Lemma 3.4 ($\bigstar$).

With probability at least $\frac{3}{4}$, all spokes induced in the diagram
$\mathrm{Diag}_{\mathcal{S}}$ are not heavy.

The proof of Lemma 3.4 is a direct adaptation of the proof of [20, Claim 2] to
our setting. The main difference is that here we need to take objects of
$\mathcal{P}$ into account.

Next, we focus our attention on diamonds, which, recall, are faces of the
radial graph $\mathrm{Rad}_{\mathcal{S}}$. The _weight_ of a diamond
$\diamondsuit_{\mathcal{S}}(e)$ with respect to $\mathcal{F}$ is the number of
objects of $\mathcal{F}$ that intersect $\diamondsuit_{\mathcal{S}}(e)$,
excluding the (at most) two objects of $\mathcal{S}$ that define
$\diamondsuit_{\mathcal{S}}(e)$. Note that all the objects contributing to the
weight of $\diamondsuit_{\mathcal{S}}(e)$ do not belong to $\mathcal{S}$. This
leads to the following definition: call a diamond
$\diamondsuit_{\mathcal{S}}(e)$ in $\mathrm{Diag}_{\mathcal{S}}$ heavy if its
weight with respect to $\mathcal{F}$ is larger than $\eta$. The next statement
ensures that with high probability, in $\mathrm{Diag}_{\mathcal{S}}$ one does
not observe any heavy diamonds. The estimation of this probability basically
follows the same framework as the proof of Lemma 3.4, and is a direct
adaptation of the proof of [20, Claim 3].

######  Lemma 3.5 ($\bigstar$).

With probability at least $\frac{3}{4}$, there is no heavy diamond in
$\mathrm{Diag}_{\mathcal{S}}$.

###  3.2 Finding cycles

We proceed to finding suitable cycles $C_{1},C_{2}$ in
$\mathrm{Rad}_{\mathcal{S}}$. These cycles should be balanced with respect to
two different weight functions: one reflecting the density of $\mathcal{F}$ in
different parts of the diagram $\mathrm{Diag}_{\mathcal{S}}$, and second
corresponding to the placement of the initial Swiss-cheese separator
$(\mathcal{P},\mathcal{K},f)$, as we wish to split this separator in a
balanced way. To find the cycles, we will use the following statement.

######  Theorem 3.6.

($\bigstar$) Let $H$ be the Voronoi diagram of some set $\mathcal{S}$ of
disjoint disjoint objects in a graph $G$ embedded in the sphere
$\mathbb{S}^{2}$. Let $\omega$ be an assignment of nonnegative weights to
vertices of $H$ such that the total sum of the weights is equal to $1$. Then
there exists a cycle $C$ in $\mathrm{Rad}_{\mathcal{S}}$ of length at most
$\sqrt{18|V(H)|}$ such that the total weight of the vertices of $H$ lying
strictly inside any of the two regions of $\mathbb{S}^{2}-C$ is at most $2/3$.

The proof of Theorem 3.6 follows from a rather straightforward adjustment of
the arguments contained in [18, Sections 4.7 and 4.8], hence we defer it to
Appendix B. With Theorem 3.6 in hand, we can now construct the two cycles and
prove Theorem 3.2.

Recall that if we perform sampling as explained in Section 3.1, then by 3.3,
3.4 and 3.5 with probability at least
$1-(\frac{1}{4}+\frac{1}{4}+\frac{1}{4})=\frac{1}{4}$ we get $\mathcal{S}$
with $\mathcal{P}\subseteq\mathcal{S}\subseteq\mathcal{P}\cup\mathcal{F}$
satisfying the following:

  * •

$s/2\leqslant|\mathcal{S}-\mathcal{P}|\leqslant 2s$;

  * •

no spoke in $\mathrm{Diag}_{\mathcal{S}}$ is heavy; and

  * •

no diamond in $\mathrm{Diag}_{\mathcal{S}}$ is heavy.

Hence, there exists a sample $\mathcal{S}$ satisfying the above properties,
which we fix from now on. Let $H\coloneqq\mathrm{Diag}_{\mathcal{S}}$. The two
cycles $C_{1},C_{2}$ will be obtained by applying Theorem 3.6 to two different
weight functions on $H$. The first one will guarantee balancedness with
respect to the number of objects of $\mathcal{F}$. More precisely, let
$\mu_{\mathrm{bal}}\colon V(H)\to[0,1]$ be defined as follows. For every
object $p\in\mathcal{F}$, assign $p$ to an arbitrary diamond
$\diamondsuit_{\mathcal{S}}(e)$, where $e\in V(H)$, such that $p$ intersects
$\diamondsuit_{\mathcal{S}}(e)$ (including its boundary). Next, assign every
diamond $\diamondsuit_{\mathcal{S}}(e)$ to an arbitrarily chosen endpoint of
$e$. Finally, for $f\in V(H)$ define $\mu_{\mathrm{bal}}(f)$ to be the total
number of objects assigned to $f$ through the composition of the two
assignments described above, divided by $|\mathcal{F}|$. Clearly, $\sum_{f\in
V(H)}\mu_{\mathrm{bal}}(f)=1$. Also, the absence of heavy diamonds implies the
following.

######  Claim 3.7.

For every $f\in V(H)$, $\mu_{\mathrm{bal}}(f)\leqslant
10^{-5}\cdot\frac{\varepsilon^{2}}{\ln(1/\varepsilon)}$.

###### Proof.

Every object of $\mathcal{F}$ assigned to $f$ must either be an object of
$\mathcal{S}$ that corresponds to one of the at most three faces of
$\mathrm{Diag}_{\mathcal{S}}$ incident to $f$, or must intersect one of the
three diamonds corresponding to the edges of $\mathrm{Diag}_{\mathcal{S}}$
incident with $f$. Since every diamond in $\mathrm{Diag}_{\mathcal{S}}$ is not
heavy, the claim follows due to
$\mu_{\mathrm{bal}}(f)\leqslant\frac{3\eta+3}{|\mathcal{F}|}\leqslant
10^{-5}\cdot\frac{\varepsilon^{2}}{\ln(1/\varepsilon)}$. ∎

Similarly, we define the weight function $\mu_{\mathrm{len}}\colon
V(H)\to[0,1]$ by setting $\mu_{\mathrm{len}}(f)=\frac{2}{\ell}$ if $f$ is a
branching point traversed by any of the cycles from $\mathcal{K}$, and
$\mu_{\mathrm{len}}(f)=0$ otherwise. Observe that since branching points have
degree $3$ in $\mathrm{Rad}_{\mathcal{S}}$ and cycles of $\mathcal{K}$ are
edge-disjoint, every branching point $f$ participates in at most one cycle
from $\mathcal{K}$. As the total length of cycles in $\mathcal{K}$ is $\ell$,
we conclude that $\sum_{f\in V(H)}\mu_{\mathrm{len}}(f)=1$.

We now apply Theorem 3.6 to the weight functions $\mu_{\mathrm{bal}}$ and
$\mu_{\mathrm{len}}$, yielding cycles $C_{1}$ and $C_{2}$ in
$\mathrm{Diag}_{\mathcal{S}}$. First, we estimate the size of
$H=\mathrm{Diag}_{\mathcal{S}}$ and the lengths of the cycles $C_{1}$ and
$C_{2}$. First, we have
$|\mathcal{S}|=|\mathcal{P}|+|\mathcal{S}-\mathcal{P}|\leqslant\frac{9}{2}s$.
As $\mathrm{Diag}_{\mathcal{S}}$ is a connected $3$-regular sphere-embedded
multigraph with $|\mathcal{S}|$ faces, from Euler’s formula it follows that
$H$ has less than $2|\mathcal{S}|\leqslant 9s$ branching points (see [18,
Lemma 4.5]). So $|V(H)|\leqslant 9s$. Now, by Theorem 3.6 both $C_{1}$ and
$C_{2}$ have lengths bounded by $\sqrt{18\cdot 9s}=\sqrt{162s}$.

To conclude the proof of Theorem 3.2, we are left with verifying properties
(a), (b), and (c).

###### Proof of property (a) in Theorem 3.2.

For property (a), we need to show that only $\varepsilon|\mathcal{F}|$ of
objects of $\mathcal{F}$ are in conflict with any of the cycles $C_{1}$ or
$C_{2}$. Recall that each spoke of $H$ is in conflict with at most $\eta$
objects of $\mathcal{F}$. Therefore, the total number of objects in conflict
with $C_{1}$ or $C_{2}$ is bounded by

$2\cdot\sqrt{162s}\cdot\eta\leqslant\frac{\sqrt{648s}\cdot
100\ln(1/\varepsilon)}{s}\cdot|\mathcal{F}|\leqslant
10^{5}\cdot\frac{\ln(1/\varepsilon)}{\sqrt{s}}\cdot|\mathcal{F}|=\varepsilon|\mathcal{F}|,$

as required. ∎

###### Proof of property (b) in Theorem 3.2.

For property (b), let $A$ be any of the two regions into which $\Gamma(C_{1})$
divides the sphere $\mathbb{S}^{2}$. Observe that every object $p$ of
$\mathcal{F}$ that is entirely contained in $A$ contributes, in the definition
of the weight function $\mu_{\mathrm{bal}}$, to the weight of a branching
point that lies either inside $A$ or on the cycles $C_{1}$; this is because
$p$ can intersect only diamonds contained in $A$. By Theorem 3.6, the total
$\mu_{\mathrm{bal}}$-weight of branching points lying on either side of the
cycle $C_{1}$ (excluding branching points on $C_{1}$ itself) is at most
$\frac{2}{3}$, while by 3.7, the total weight of branching points lying on
$C_{1}$ is bounded by

$10^{-5}\cdot\frac{\varepsilon^{2}}{\ln(1/\varepsilon)}\cdot\sqrt{162s}=10^{-5}\cdot\sqrt{162}\cdot
10^{5}\cdot\varepsilon\leqslant\frac{1}{12}.$

Hence, the total number of objects $p$ entirely contained in $A$ is bounded by
$(\frac{2}{3}+\frac{1}{12})|\mathcal{F}|=\frac{3}{4}|\mathcal{F}|$. Since for
every face $g$ of $R$, the corresponding region of
$\mathbb{S}^{2}-\bigcup_{C\in\mathcal{K}\cup\\{C_{1},C_{2}\\}}\Gamma(C)$ is
entirely contained in one of the regions of $\mathbb{S}^{2}-\Gamma(C_{1})$,
property (b) follows. ∎

###### Proof of property (c) in Theorem 3.2.

For property (c), let $g\subseteq f$ be a face of $R$. As $g$ is a face of a
subgraph of $H$, the boundary of $g$ can be partitioned into a set
$\mathcal{K}_{g}$ consisting of non-crossing edge-disjoint cycles in $H$. Let
us now estimate the total length of the cycles in $\mathcal{K}_{g}$.

Recall that the cycle $C_{2}$ is balanced with respect to the weight function
$\mu_{\mathrm{len}}$ in the sense of Theorem 3.6. Since $g$ is entirely
contained in one of the sides of $C_{2}$, say $A$, it follows that every
branching point visited by any cycle of $\mathcal{K}_{g}$ is either a
branching point visited by $C_{2}$ or it lies strictly inside $A$. Since the
total length of cycles in $\mathcal{K}$ is $\ell$ and every branching point
traversed by a cycle of $\mathcal{K}$ is incident to exactly two edges of
cycles in $\mathcal{K}$, the total number of branching points traversed by the
cycles of $\mathcal{K}$ is $\frac{\ell}{2}$. By Theorem 3.6, at most
$\frac{2}{3}\cdot\frac{\ell}{2}=\frac{\ell}{3}$ of these branching points may
lie strictly inside $A$. On the other hand, cycle $C_{2}$ has length at most
$\sqrt{162s}\leqslant\frac{s}{3}$, which means that there are at most
$\frac{s}{6}$ branching points traversed by $C_{2}$. All in all, the total
number of branching points traversed by any cycle of $\mathcal{K}_{g}$ is
bounded by

$\frac{\ell}{2}+\frac{s}{6}\leqslant\frac{s}{3}+\frac{s}{6}=\frac{s}{2}.$

Now every branching point traversed by any cycle of $\mathcal{K}_{g}$ is
incident to exactly two edges of cycles in $\mathcal{K}_{g}$. So the total
number of edges on the cycles of $\mathcal{K}_{g}$ is bounded by $s$, as
required.

It remains to define $\mathcal{P}_{g}$ so that
$(\mathcal{P}_{g},\mathcal{K}_{g},g)$ is a ripe Swiss-cheese separator. For
this, it suffices to apply Lemma 2.5 to every cycle of $\mathcal{K}_{g}$ and
take the union of the obtained subsets of $\mathcal{S}$ (note that the
compatibility of cycles in $\mathcal{K}_{g}$ holds). The fact that
$(\mathcal{P}_{g},\mathcal{K}_{g},g)$ obtained in this manner is a Swiss-
cheese separator follows from Lemma 2.4. ∎

##  4 Algorithm

In this section, we present the proof of Theorem 1.1. We write $s\coloneqq
s(\varepsilon)$ for brevity and denote $n\coloneqq|V(G)|$. Our algorithm
enumerates the set of all ripe Swiss-cheese separators of complexity $s$:

$\displaystyle\mathsf{Sep}$
$\displaystyle\coloneqq\\{(\mathcal{P},\mathcal{K},f)\ \colon\
(\mathcal{P},\mathcal{K},f)\text{ is a ripe Swiss-cheese separator of
complexity at most }s\\}.$

Throughout this section we will think of $f$ in the above as of a region of
$\mathbb{S}^{2}-\bigcup_{C\in\mathcal{K}}\Gamma(C)$, as explained below
Definition 3.1.

######  Lemma 4.1.

$\mathsf{Sep}$ has size at most
$|\mathcal{D}|^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}$ and can be
enumerated in time
$|\mathcal{D}|^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}\cdot
n^{\mathcal{O}(1)}$.

###### Proof.

Recall that if $(\mathcal{P},\mathcal{K},f)$ is a ripe Swiss-chees separator
of complexity at most $s$, then $|\mathcal{P}|\leqslant\frac{5}{2}s$.
Therefore, to describe $(\mathcal{P},\mathcal{K},f)$ it suffices to provide
the following components:

  * •

An independent set $\mathcal{P}\subseteq\mathcal{D}$ consisting of
$\frac{5}{2}s$ objects, for which there are $|\mathcal{D}|^{\mathcal{O}(s)}$
options.

  * •

A set $\mathcal{K}$ consisting of edge-disjoint non-crossing cycles in
$\mathrm{Diag}_{\mathcal{P}}$. Note that $\mathcal{K}$ is uniquely defined by
the set of edges participating in the cycles of $\mathcal{K}$, and
$\mathrm{Diag}_{\mathcal{S}}$ has $\mathcal{O}(s)$ edges, hence there are
$2^{\mathcal{O}(s)}$ options for $\mathcal{K}$.

  * •

A face $f$ of the subgraph of $\mathrm{Diag}_{\mathcal{P}}$ consisting of
edges and vertices of the cycles $\mathcal{K}$, for which there are at most
$\mathcal{O}(s)$ options.

For each candidate as described above, we can verify in polynomial time
whether it indeed defines a ripe Swiss-cheese separator. Since
$s=\widetilde{\mathcal{O}}(1/\varepsilon^{2})$, the claim follows. ∎

Next, we define the order in which separators in $\mathsf{Sep}$ will be
considered. For two separators $(\mathcal{P}_{1},\mathcal{K}_{1},f_{1})$ and
$(\mathcal{P}_{2},\mathcal{K}_{2},f_{2})$ in $\mathsf{Sep}$, we say that
$(\mathcal{P}_{1},\mathcal{K}_{1},f_{1})\preceq(\mathcal{P}_{2},\mathcal{K}_{2},f_{2})$
if the region $f_{1}$ is contained in the region $f_{2}$. Observe that
$\preceq$ is a partial order on $\mathsf{Sep}$. We also define the optima that
will be sought by our dynamic programming procedure.

######  Definition 4.2.

We say that an independent set $\mathcal{F}\subseteq\mathcal{D}$ _is inside_
$(\mathcal{P},\mathcal{K},f)$ if
$\mathcal{F}\subseteq\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$. The maximum
size of such an independent set will be denoted by
$\mathrm{opt}(\mathcal{P},\mathcal{K},f)$.

Next, we prove that given a separator
$(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$, one can enumerate a family of
candidate splits of $(\mathcal{P},\mathcal{K},f)$ into several separators from
$\mathsf{Sep}$ with strictly smaller regions, with the guarantee that among
the splits there is one where only small fraction of objects of $\mathcal{F}$
is lost. The proof is just an application of Theorem 3.2.

######  Lemma 4.3.

Given $(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$, one can in time
$|\mathcal{D}|^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}\cdot
n^{\mathcal{O}(1)}$ enumerate a family
$\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ of size
$|\mathcal{D}|^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}$, such that:

  * •

each member of $\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ is a family
$\mathcal{C}\subseteq\mathsf{Sep}$ such that for each
$(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}$, the
region $f^{\prime}$ is a strict subset of $f$, and the interiors of
$f^{\prime}$ for
$(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}$ are
pairwise disjoint; and

  * •

provided $\mathrm{opt}(\mathcal{P},\mathcal{K},f)\geqslant s$, there exists
$\mathcal{C}\in\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ such that

$\sum_{(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}}\min\left(\frac{3}{4}\cdot\mathrm{opt}(\mathcal{P},\mathcal{K},f),\mathrm{opt}(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\right)\geqslant(1-\varepsilon)\cdot\mathrm{opt}(\mathcal{P},\mathcal{K},f).$

###### Proof.

We enumerate the family $\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ as follows.
Iterate through all independent sets
$\mathcal{S}^{\circ}\subseteq\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$ of
size at most $2s$ and all pairs of cycles $C_{1},C_{2}$ in
$\mathrm{Rad}_{\mathcal{S}}$, where
$\mathcal{S}\coloneqq\mathcal{P}\cup\mathcal{S}^{\circ}$. For each such
choice, let $R$ be the subgraph of $\mathrm{Rad}_{\mathcal{S}}$ consisting of
all vertices and edges traversed by the cycles of
$\mathcal{K}\cup\\{C_{1},C_{2}\\}$ (where the cycles of $\mathcal{K}$ persist
as cycles in $\mathrm{Rad}_{\mathcal{S}}$ due to Lemma 2.4). For every face
$g$ of $R$ satisfying $g\subseteq f$, construct a ripe Swiss-cheese separator
$(\mathcal{P}_{g},\mathcal{K}_{g},g)$ by applying Lemma 2.5 to
$(\mathcal{S},\mathcal{K}_{g},g)$, where $\mathcal{K}_{g}$ is the
decomposition of the boundary of $g$ into edge-disjoint non-crossing cycles in
$\mathrm{Diag}_{\mathcal{S}}$. Note that the compatibility is preserved. Next,
we let $\mathcal{C}$ be the set of separators
$(\mathcal{P}_{g},\mathcal{K}_{g},g)$ as described above. We include
$\mathcal{C}$ in $\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ if it satisfies
the first condition from the lemma statement:
$\mathcal{C}\subseteq\mathsf{Sep}$ (equivalently, every separator in
$\mathcal{C}$ has complexity at most $s$) and $g\subsetneq f$ for all
$(\mathcal{P}_{g},\mathcal{K}_{g},g)\in\mathcal{C}$.

The family $\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ constructed in this way
will have size $|\mathcal{D}|^{\mathcal{O}(s)}$, which is
$|\mathcal{D}|^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}$ due to
$s=\widetilde{\mathcal{O}}(1/\varepsilon^{2})$. It can also be enumerated in
time $|\mathcal{D}|^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}\cdot
n^{\mathcal{O}(1)}$.

It remains to prove the second postulated condition. Let then
$\mathcal{F}\subseteq\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$ be the
maximum-size independent set that is inside $(\mathcal{P},\mathcal{K},f)$.
Then $|\mathcal{F}|=\mathrm{opt}(\mathcal{P},\mathcal{K},f)$, which by
assumption is at least $s$. Now Theorem 3.2 asserts that the enumeration
algorithm explained above will consider a suitable choice of $\mathcal{S}$ and
$C_{1},C_{2}$ for which the constructed family $\mathcal{C}$ will be included
in $\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$, and for which we have the
following properties:

  * •

$|\mathcal{F}\cap\mathrm{Allowed}(\mathcal{P}_{g},\mathcal{K}_{g},g)|\leqslant\frac{3}{4}|\mathcal{F}|=\frac{3}{4}\cdot\mathrm{opt}(\mathcal{P},\mathcal{K},f)$
for all $(\mathcal{P}_{g},\mathcal{K}_{g},g)\in\mathcal{C}$, and

  * •

at least $(1-\varepsilon)|\mathcal{F}|$ objects from $\mathcal{F}$ are not in
conflict with $C_{1}$ and $C_{2}$.

Note that the first condition above in particular implies that $g\subsetneq f$
for all $(\mathcal{P}_{g},\mathcal{K}_{g},g)\in\mathcal{C}$. Further, every
object of $\mathcal{F}$ that is not in conflict with $C_{1}$ and $C_{2}$ is
inside one of the Swiss-cheese separators
$(\mathcal{P}_{g},\mathcal{K}_{g},g)\in\mathcal{C}$. Hence

$\displaystyle\sum_{(\mathcal{P}_{g},\mathcal{K}_{g},g)\in\mathcal{C}}\min\left(\frac{3}{4}\cdot\mathrm{opt}(\mathcal{P},\mathcal{K},f),\mathrm{opt}(\mathcal{P}_{g},\mathcal{K}_{g},g)\right)$
$\displaystyle\geqslant\sum_{(\mathcal{P}_{g},\mathcal{K}_{g},g)\in\mathcal{C}}|\mathcal{F}\cap\mathrm{Allowed}(\mathcal{P}_{g},\mathcal{K}_{g},g)|$
$\displaystyle\geqslant(1-\varepsilon)\cdot\mathrm{opt}(\mathcal{P},\mathcal{K},f).$

This concludes the proof. ∎

#### Description of the algorithm.

Now, we present our algorithm. The idea is to perform dynamic programming on
Swiss-cheese separators. First, we enumerate the set $\mathsf{Sep}$ using
Lemma 4.1. We construct two dynamic programming tables
$\mathsf{SmallSol},\mathsf{ApproxIS}\colon\mathsf{Sep}\to\mathbb{N}$. We
initially set for every $(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$:

$\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f]\coloneqq
0\qquad\textrm{and}\qquad\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]\coloneqq
0.$

The intention is that after filling in the tables, for all
$(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$ we will have the following:

$\displaystyle\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f]$
$\displaystyle=\min(s,\mathrm{opt}(\mathcal{P},\mathcal{K},f))\qquad\textrm{and}$
$\displaystyle\mathrm{opt}(\mathcal{P},\mathcal{K},f)^{1-4\varepsilon}\,$
$\displaystyle\leqslant\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]\leqslant\mathrm{opt}(\mathcal{P},\mathcal{K},f).$
(1)

That is, in $\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f]$ we store the
maximum size of a solution, but capped at the value $s$, and in
$\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]$, we store an approximation of
the maximum size of a solution. Note that the above bound will naturally lead
to an $\text{OPT}^{4\varepsilon}$-approximation algorithm. To achieve the
statement of Theorem 1.1, we rescale $\varepsilon$ by a factor of $4$.

In the first phase, we compute the table $\mathsf{SmallSol}[\cdot]$. To do so,
we iterate over every possible separator
$(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$ and every set
$\mathcal{F}\subseteq\mathrm{Allowed}(\mathcal{P},\mathcal{K},f)$ of size at
most $s$. In $\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f]$, we simply store
the maximum cardinality among the considered sets $\mathcal{F}$ that turned
out to be independent. This operation can be implemented in time
$|\mathcal{D}|^{\widetilde{\mathcal{O}}(s)}\cdot n^{\mathcal{O}(1)}$.

In the second phase, we compute the table $\mathsf{ApproxIS}[\cdot]$. To fill
in $\mathsf{ApproxIS}[\cdot]$, we iterate over separators
$(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$ according to the partial order
$\preceq$. In other words, if $f_{1}\subsetneq f_{2}$, then we consider the
separator $(\mathcal{P},\mathcal{K}_{1},f_{1})$ before the separator
$(\mathcal{P},\mathcal{K}_{2},f_{2})$.

Now, assuming that we are considering
$(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$, we enumerate the family
$\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ provided by Lemma 4.3. Then we set

$\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]\coloneqq\max\left(\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f],\
\max_{\mathcal{C}\in\mathsf{Cand}(\mathcal{P},\mathcal{K},f)}\left\\{\sum_{(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}}\mathsf{ApproxIS}[\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime}]\right\\}\right).$

In other words, $\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]$ is set to be
the largest value among the candidates:
$\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f]$ and
$\sum_{(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}}\mathsf{ApproxIS}[\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime}]$,
for all $\mathcal{C}\in\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$.

Finally, observing that $(\emptyset,\emptyset,\mathbb{S}^{2})$ is also a valid
ripe Swiss-cheese separator that belongs to $\mathsf{Sep}$, we return
$\mathsf{ApproxIS}[\emptyset,\emptyset,\mathbb{S}^{2}]$ as the final answer.
This concludes the description of the algorithm. Note that the number of
states in our dynamic programming tables, as well as the number of operations
required to compute them, is
$|\mathcal{D}|^{\widetilde{\mathcal{O}}(1/\varepsilon^{2})}\cdot
n^{\mathcal{O}(1)}$. Therefore, to prove Theorem 1.1, we need to justify the
approximate correctness of the algorithm. That is, we need to prove the
assertion (1).

#### Approximation factor.

We will need the following inequality.

######  Proposition 4.4.

Let $\delta,c\in(0,1)$ and $a_{1},\ldots,a_{m},A\in\real$ be positive reals
such that $cA\geqslant a_{i}$ for all $i\in\\{1,\ldots,m\\}$ and
$\sum_{i=1}^{m}a_{i}\geqslant c^{\delta}A$. Then

$\sum_{i=1}^{m}(a_{i})^{1-\delta}\geqslant A^{1-\delta}.$

###### Proof.

By the assumption $cA\geqslant a_{i}$ we have:

$\mathrm{LHS}\coloneqq\sum_{i=1}^{m}(a_{i})^{1-\delta}=\sum_{i=1}^{m}\frac{a_{i}}{(a_{i})^{\delta}}\geqslant
c^{-\delta}\cdot\sum_{i=1}^{m}\frac{a_{i}}{A^{\delta}}.$

Next, we use the assumption $\sum_{i=1}^{m}a_{i}\geqslant c^{\delta}A$ and
conclude that $\mathrm{LHS}\geqslant
c^{-\delta}\cdot\frac{c^{\delta}A}{A^{\delta}}=A^{1-\delta}$. ∎

Next, we proceed to the proof of (1). Note that
$\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f]=\min(s,\mathrm{opt}(\mathcal{K},f))$
for all $(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$ is clear from the way we
computed the entries of $\mathsf{SmallSol}[\cdot]$. So we are left with
proving the following.

######  Lemma 4.5.

For every Swiss-cheese separator $(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$
of complexity at most $s$, we have

$\mathrm{opt}(\mathcal{P},\mathcal{K},f)^{1-4\varepsilon}\leqslant\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]\leqslant\mathrm{opt}(\mathcal{P},\mathcal{K},f).$

###### Proof.

For the upper bound, a straightforward inductive argument over separators of
$\mathsf{Sep}$ ordered by $\preceq$ shows that whenever
$\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]$ is set to some value, say $w$,
then this is witnessed by the existence of an independent set of size $w$ that
is inside $(\mathcal{P},\mathcal{K},f)$. It follows that
$\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]\leqslant\mathrm{opt}(\mathcal{P},\mathcal{K},f)$
for all $(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$.

We proceed to the proof of the lower bound, which is also by induction on
$(\mathcal{P},\mathcal{K},f)\in\mathsf{Sep}$ according to the order $\preceq$.
Note that whenever $\mathrm{opt}(\mathcal{P},\mathcal{K},f)\leqslant s$, we
have
$\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]=\mathrm{opt}(\mathcal{P},\mathcal{K},f)$
due to taking $\mathsf{SmallSol}[\mathcal{P},\mathcal{K},f]$ into account
among the candidates for the value of
$\mathsf{ApproxIS}[\mathcal{P},\mathcal{K},f]$. So assume otherwise, that
$\mathrm{opt}(\mathcal{P},\mathcal{K},f)>s$. In that case, the second point of
Lemma 4.3 asserts that there exists
$\mathcal{C}\in\mathsf{Cand}(\mathcal{P},\mathcal{K},f)$ such that

$\sum_{(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}}\min\left(\frac{3}{4}\cdot\mathrm{opt}(\mathcal{P},\mathcal{K},f),\mathrm{opt}(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\right)\geqslant(1-\varepsilon)\cdot\mathrm{opt}(\mathcal{P},\mathcal{K},f).$
(2)

As $f^{\prime}\subsetneq f$ for all
$(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}$, by
induction we know that

$\mathrm{opt}(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})^{1-4\varepsilon}\leqslant\mathsf{ApproxIS}[\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime}]\qquad\textrm{for
all }(\mathcal{P}^{\prime},\mathcal{K}^{\prime},f^{\prime})\in\mathcal{C}.$
(3)

We may now use Proposition 4.4 with

$\delta\coloneqq 4\varepsilon,\quad c\coloneqq\frac{3}{4},\quad
A\coloneqq\mathrm{opt}(\mathcal{P},\mathcal{K},f),\quad\textrm{and}\quad
a_{i}\coloneqq\min\left(\frac{3}{4}\cdot\mathrm{opt}(\mathcal{P},\mathcal{F},f),\mathrm{opt}(\mathcal{P}_{i},\mathcal{F}_{i},f_{i})\right),$

where $\\{(\mathcal{P}_{i},\mathcal{F}_{i},f_{i})\colon i=1,\ldots,m\\}$ is an
arbitrary enumeration of $\mathcal{C}$. Indeed, for such a choice we have on
one hand $cA\geqslant a_{i}$ for all $i\in\\{1,\ldots,m\\}$, and on the other
hand, by Bernoulli’s inequality444We use the following variant:
$(1-x)^{r}\leqslant 1-rx$ for all $r,x\in[0,1]$.,

$1-\varepsilon\geqslant\left(1-\frac{1}{4}\right)^{4\varepsilon}=c^{\delta},$

hence (2) implies that $\sum_{i=1}^{m}a_{i}\geqslant c^{\delta}A$. By
Proposition 4.4 we conclude that

$\sum_{i=1}^{m}\mathrm{opt}(\mathcal{P}_{i},\mathcal{K}_{i},f_{i})^{1-4\varepsilon}\geqslant\sum_{i=1}^{m}(a_{i})^{1-4\varepsilon}\geqslant
A^{1-4\varepsilon}=\mathrm{opt}(\mathcal{P},\mathcal{F},f)^{1-4\varepsilon}.$
(4)

As $\mathcal{C}\in\mathsf{Cand}(\mathcal{P},\mathcal{F},f)$, the algorithm
considers $\mathcal{C}$ when computing
$\mathsf{ApproxIS}[\mathcal{P},\mathcal{F},f]$, and hence

$\mathsf{ApproxIS}[\mathcal{P},\mathcal{F},f]\geqslant\sum_{i=1}^{m}\mathsf{ApproxIS}[\mathcal{P}_{i},\mathcal{K}_{i},f_{i}]$
(5)

We may now combine (3), (4), and (5) to conclude that
$\mathsf{ApproxIS}[\mathcal{P},\mathcal{F},f]\geqslant\mathrm{opt}(\mathcal{P},\mathcal{F},f)^{1-4\varepsilon}$,
as required. So the induction proof is complete. ∎

This concludes the proof of Theorem 1.1.

#### Acknowledgements.

The results presented in this paper were obtained during the trimester on
Discrete Optimization at Hausdorff Research Institute for Mathematics (HIM) in
Bonn, Germany. We are thankful for the possibility of working in the
stimulating and creative research environment at HIM.

## References

  * [1] A. Adamaszek, S. Har-Peled, and A. Wiese.  Approximation Schemes for Independent Set and Sparse Subsets of Polygons.  J. ACM, 66(4):29:1–29:40, 2019.
  * [2] A. Adamaszek and A. Wiese.  Approximation Schemes for Maximum Weight Independent Set of Rectangles.  In IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, pages 400–409, 2013.
  * [3] A. Adamaszek and A. Wiese.  A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices.  In C. Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 645–656. SIAM, 2014.
  * [4] P. K. Agarwal and N. H. Mustafa.  Independent set of intersection graphs of convex objects in 2D.  Comput. Geom., 34(2):83–95, 2006.
  * [5] P. K. Agarwal, M. J. van Kreveld, and S. Suri.  Label placement by maximum independent set in rectangles.  Comput. Geom., 11(3-4):209–218, 1998.
  * [6] S. Arora.  Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems.  J. ACM, 45(5):753–782, 1998.
  * [7] T. M. Chan.  Polynomial-time approximation schemes for packing and piercing fat objects.  J. Algorithms, 46(2):178–189, 2003.
  * [8] T. M. Chan and S. Har-Peled.  Approximation algorithms for maximum independent set of pseudo-disks.  In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 333–340, 2009.
  * [9] V. Cohen-Addad, M. Pilipczuk, and M. Pilipczuk.  Efficient approximation schemes for uniform-cost clustering problems in planar graphs.  In 27th Annual European Symposium on Algorithms, ESA 2019, volume 144 of LIPIcs, pages 33:1–33:14. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2019.
  * [10] T. Erlebach, K. Jansen, and E. Seidel.  Polynomial-Time Approximation Schemes for Geometric Intersection Graphs.  SIAM J. Comput., 34(6):1302–1323, 2005.
  * [11] L. D. Floriani, P. Magillo, and E. Puppo.  Applications of Computational Geometry to Geographic Information Systems.  In J. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 333–388. North Holland / Elsevier, 2000.
  * [12] J. Fox and J. Pach.  Computing the Independence Number of Intersection Graphs.  In D. Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1161–1165. SIAM, 2011.
  * [13] W. Gálvez, A. Khan, M. Mari, T. Mömke, M. R. Pittu, and A. Wiese.  A 3-Approximation Algorithm for Maximum Independent Set of Rectangles.  In 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 894–905, 2022.
  * [14] S. Har-Peled.  Quasi-polynomial time approximation scheme for sparse subsets of polygons.  In 30th Annual Symposium on Computational Geometry, SoCG’14, page 120. ACM, 2014.
  * [15] J. Håstad.  Clique is hard to approximate within $n^{1-\varepsilon}$.  Acta Mathematica, 182:105–142, 1999.
  * [16] D. S. Hochbaum and W. Maass.  Approximation schemes for covering and packing problems in image processing and VLSI.  Journal of the ACM (JACM), 32(1):130–136, 1985.
  * [17] E. Malesinska.  Graph theoretical models for frequency assignment problems.  Citeseer, 1997.
  * [18] D. Marx and M. Pilipczuk.  Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams.  ACM Trans. Algorithms, 18(2):13:1–13:64, 2022.
  * [19] J. S. B. Mitchell.  Approximating Maximum Independent Set for rectangles in the plane.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 339–350, 2021.
  * [20] M. Pilipczuk, E. J. van Leeuwen, and A. Wiese.  Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs.  Algorithmica, 82(6):1703–1739, 2020.
  * [21] F. C. R. Spieksma.  Approximating an Interval Scheduling Problem.  In K. Jansen and D. S. Hochbaum, editors, Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX’98, Aalborg, Denmark, July 18-19, 1998, Proceedings, volume 1444 of Lecture Notes in Computer Science, pages 169–180. Springer, 1998.
  * [22] B. Verweij and K. Aardal.  An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling.  In J. Nesetril, editor, Algorithms - ESA ’99, 7th Annual European Symposium, Prague, Czech Republic, July 16-18, 1999, Proceedings, volume 1643 of Lecture Notes in Computer Science, pages 426–437. Springer, 1999.

##  Appendix A Proofs from Section 3

This section contains the missing proofs from Section 3. We emphasize again
that to a large extent, the proofs of 3.3, 3.4 and 3.5 below follow [20,
Section 2.2].

###### Proof of Lemma 3.4.

The remainder of this proof is in its entirety a paraphrase and an adaptation
of the proof of [20, Claim 2 in the proof of Lemma 4], with a majority of text
taken verbatim.

By Lemma 2.2 there are three cases to be analysed based on whether the spoke
in question comes from a face of type 1, type 2, or type 3. For the sake of
presentation, let us first focus on the case of type 1.

Consider any triple $p_{1},p_{2},p_{3}$ of different objects from
$\mathcal{F}\cup\mathcal{P}$ and let $f$ be a singular type-1 face for
$(p_{1},p_{2},p_{3})$. Suppose further that $P$ is one of the spokes incident
to $f$ induced in the Voronoi diagram of $\\{p_{1},p_{2},p_{3}\\}$.
Importantly, let us assume that spoke $P$ is heavy. Let us estimate the
probability of the following event

$\mathrm{Event\;\textbf{A}}:p_{1},p_{2},p_{3}\text{ all belong to
}\mathcal{S}\text{ and }P\text{ is a spoke induced in
}\mathrm{Diag}_{\mathcal{S}}.$

For the Event A to happen two things must happen: (i)
$p_{1},p_{2},p_{3}\in\mathcal{S}$, and (ii) for each
$p^{\prime}\in\mathcal{F}-\\{p_{1},p_{2},p_{3}\\}$ that is in conflict with
$P$, the object $p^{\prime}$ must not be included in $\mathcal{S}$. Let
$\mathcal{Z}$ be the set of such objects $p^{\prime}$. Observe that the
probability that object $p^{\prime}$ is not included in $\mathcal{S}$ is
$(1-\lambda)$. As for (i), let $q_{p}$ be the probability that
$p\in\mathcal{S}$. Observe that $q_{p}=\lambda$ if $p\in\mathcal{F}$ and
$q_{p}=1$ if $p\in\mathcal{P}$. Using the standard inequality
$1-x\leqslant\exp(-x)$ we have:

$\displaystyle\mathbb{P}(\textbf{A})\leqslant$ $\displaystyle
q_{p_{1}}q_{p_{2}}q_{p_{3}}\cdot\prod_{p^{\prime}\in\mathcal{Z}}(1-\lambda)\leqslant
q_{p_{1}}q_{p_{2}}q_{p_{3}}\cdot\exp\left(-\sum_{p^{\prime}\in\mathcal{Z}}\lambda\right)$
$\displaystyle\leqslant$ $\displaystyle
q_{p_{1}}q_{p_{2}}q_{p_{3}}\cdot\exp\left(-\lambda|\mathcal{Z}|\right)\leqslant
q_{p_{1}}q_{p_{2}}q_{p_{3}}\cdot\exp\left(-\lambda\eta\right)=q_{p_{1}}q_{p_{2}}q_{p_{3}}\cdot\varepsilon^{100}$
(6)

For a fixed triple $p_{1},p_{2},p_{3}\in\mathcal{F}\cup\mathcal{P}$, face $f$
that is singular of type-1 for $(p_{1},p_{2},p_{3})$ and a spoke $P$ incident
to $f$, let us denote by $\textbf{A}^{1}_{P,(p_{1},p_{2},p_{3})}$ the event A
considered above. Let $\textbf{B}^{1}$ be the event that some event
$\textbf{A}^{1}_{P,(p_{1},p_{2},p_{3})}$ happens; that is, $\textbf{B}^{1}$ is
the union of events $\textbf{A}^{1}_{P,(p_{1},p_{2},p_{3})}$ as above. By
Lemma 2.1, for every triple $p_{1},p_{2},p_{3}\in\mathcal{F}\cup\mathcal{P}$
there are at most two faces $f$ that are singular of type 1 for
$(p_{1},p_{2},p_{3})$, and for each of them there are at most $3$ spokes $P$
to consider.

Thus, by applying the union bound to (6) we get that the probability that some
event $\textbf{A}^{1}_{P,(p_{1},p_{2},p_{3})}$ happens can be bounded as
follows:

$\displaystyle\mathbb{P}(\textbf{B}^{1})$ $\displaystyle\leqslant
6\varepsilon^{100}\sum_{p_{1}\in\mathcal{F}\cup\mathcal{P}}\
\sum_{p_{2}\in\mathcal{F}\cup\mathcal{P}}\
\sum_{p_{3}\in\mathcal{F}\cup\mathcal{P}}q_{p_{1}}q_{p_{2}}q_{p_{3}}$
$\displaystyle=6\varepsilon^{100}\cdot\left(\sum_{p_{1}\in\mathcal{F}\cup\mathcal{P}}q_{p_{1}}\right)\left(\sum_{p_{2}\in\mathcal{F}\cup\mathcal{P}}q_{p_{2}}\right)\left(\sum_{p_{3}\in\mathcal{F}\cup\mathcal{P}}q_{p_{3}}\right)$
$\displaystyle\leqslant
6\varepsilon^{100}\cdot\left(\sum_{p\in\mathcal{F}\cup\mathcal{P}}q_{p}\right)^{3}=6\varepsilon^{100}\cdot\left(\left(\sum_{p\in\mathcal{F}}q_{p}\right)+\left(\sum_{p\in\mathcal{P}}q_{p}\right)\right)^{3}=6\varepsilon^{100}\left(s+|\mathcal{P}|\right)^{3}$

As $|\mathcal{P}|\leqslant 5s$, we have $\mathbb{P}(\textbf{B}^{1})\leqslant
5\cdot 48\varepsilon^{100}s^{3}\leqslant 240\varepsilon$, which bounded by
$10^{-3}$ due to $\varepsilon<10^{-100}$. Note that if $\textbf{B}^{1}$ does
not occur, then $\mathrm{Diag}_{\mathcal{S}}$ has no heavy spoke that would be
incident to a type-$1$ singular face for some triple of objects in
$\mathcal{S}$.

This concludes the case of spokes incident to singular faces of type $1$.
Next, we analyse the remaining cases. Denote by $\textbf{B}^{2}$ the following
event: there exist distinct $p_{1},p_{2},p_{3}\in\mathcal{F}\cup\mathcal{P}$
and a type-$2$ singular face $f$ for $(p_{1},p_{2},p_{3})$ such that (i)
$p_{1},p_{2},p_{3}\in\mathcal{S}$, and (ii) at least one of the heavy (w.r.t.
$\mathcal{F}$) spokes incident to $f$ in the Voronoi diagram of
$\\{p_{1},p_{2},p_{3}\\}$ remains a spoke in $\mathcal{S}$. Similar
calculation as for $\textbf{B}^{1}$ yield that
$\mathbb{P}(\textbf{B}^{2})\leqslant 10^{-3}$, as the only property of the
face of type 1 that we have used is that it was defined by a triple of
objects.

Finally, denote by $\textbf{B}^{3}$ the following event: there exist distinct
$p_{0},p_{1},p_{2},p_{3}\in\mathcal{F}\cup\mathcal{P}$ and a singular type-3
face $f$ for $(p_{0},p_{1},p_{2},p_{3})$ such that (i)
$p_{0},p_{1},p_{2},p_{3}\in\mathcal{S}$ and (ii) at least one of the heavy
(w.r.t. $\mathcal{F}$) spokes incident to $f$ in the Voronoi diagram of
$\\{p_{0},p_{1},p_{2},p_{3}\\}$ remains a spoke in $\mathcal{S}$. To bound the
probability of $\textbf{B}^{3}$ we apply similar calculations, however we sum
over quadruples of objects instead of triples. This gives:

$\displaystyle\mathbb{P}(\textbf{B}^{1})$ $\displaystyle\leqslant
8\varepsilon^{100}\sum_{p_{0}\in\mathcal{F}\cup\mathcal{P}}\sum_{p_{1}\in\mathcal{F}\cup\mathcal{P}}\sum_{p_{2}\in\mathcal{F}\cup\mathcal{P}}\sum_{p_{3}\in\mathcal{F}\cup\mathcal{P}}q_{p_{0}}q_{p_{1}}q_{p_{2}}q_{p_{3}}$
$\displaystyle\leqslant
8\varepsilon^{100}\cdot\left(\left(\sum_{p\in\mathcal{F}}q_{p}\right)+\left(\sum_{p\in\mathcal{P}}q_{p}\right)\right)^{4}\leqslant
8\varepsilon^{100}\left(s+|\mathcal{P}|\right)^{4}.$

Again, as $|\mathcal{P}|\leqslant 5s$, this means that
$\mathbb{P}(\textbf{B}^{3})\leqslant 5\cdot 128\varepsilon\leqslant 10^{-3}$.
By Lemma 2.2 we conclude that the probability that any spoke in the diagram
$\mathrm{Diag}_{\mathcal{S}}$ is heavy is at most $3\cdot
10^{-3}\leqslant\frac{1}{4}$. ∎

###### Proof of Lemma 3.5.

The remainder of this proof is in its entirety a paraphrase and an adaptation
of the proof of [20, Claim 3 in the proof of Lemma 4], with a majority of text
taken verbatim.

Consider an edge $e$ of $\mathrm{Diag}_{\mathcal{S}}$. Let $f_{1},f_{2}$ be
the endpoints of $e$ and let $p_{1},p_{2}$ be the objects of $\mathcal{S}$ so
that $\diamondsuit_{\mathcal{S}}(e)$ corresponds ot the $4$-cycle
$p_{1}f_{1}p_{2}f_{2}$ in $\mathrm{Rad}_{\mathcal{S}}$. From Lemma 2.2 we have
that both $f_{1}$ and $f_{2}$ are singular faces, for a triple (for types 1 or
2) or a quadruple (for type 3) of objects in $\mathcal{S}$. Consider first the
case when $f_{1}$ and $f_{2}$ are type-1 singular faces for triples of objects
from $\mathcal{S}$, then $f_{1}$ is a type-1 singular face for
$(p_{1},p_{2},p_{1}^{\prime})$ for some object $p_{1}^{\prime}\in\mathcal{S}$
and $f_{2}$ is a type-1 singular face for $(p_{1},p_{2},p_{2}^{\prime})$ for
some object $p_{2}^{\prime}\in\mathcal{S}$. Let us assume for a moment that
$p_{1}^{\prime}\neq p_{2}^{\prime}$; all the other cases will be discussed
later, and they will follow the same reasoning scheme.

We have a quadruple of pairwise different objects
$p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime}$. For the diamond
$\diamondsuit=\diamondsuit_{\mathcal{S}}(e)$ to arise in the diagram
$\mathrm{Diag}_{\mathcal{S}}$, both of the following two events must happen:
(i) objects $p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime}$ are included in
$\mathcal{S}$, and (ii) all objects intersecting $\diamondsuit$ except for
$p_{1},p_{2}$ must not be included in $\mathcal{S}$. These two events are
independent. The probability of the first is $q_{p_{1}}\cdot q_{p_{2}}\cdot
q_{p_{1}^{\prime}}\cdot q_{p_{1}^{\prime}}$, where $q_{p}=\lambda$ if
$p\in\mathcal{F}$ and $q_{p}=1$ if $p\in\mathcal{P}$. Therefore, we are left
to analyse the probability of event (ii).

Let $\mathcal{G}$ be the family of objects entirely contained in the interior
of $\diamondsuit$. By the assumption that $\diamondsuit$ is heavy, we know
that $|\mathcal{G}|\geqslant\eta$. Therefore, the probability that no object
of $\mathcal{G}$ is included in $\mathcal{S}$ is upper bounded by

$\displaystyle\prod_{r\in\mathcal{G}}(1-q_{r})\leqslant\exp\left(-\sum_{r\in\mathcal{G}}q_{r}\right)\leqslant\exp(-\eta\lambda)=\varepsilon^{100}.$

We conclude that the probability that $\diamondsuit$ arises in
$\mathrm{Diag}_{\mathcal{S}}$ is upper bounded by
$q_{p_{1}}q_{p_{2}}q_{p_{1}^{\prime}}q_{p_{1}^{\prime}}\cdot\varepsilon^{100}$.
For every quadruple $(p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime})$ of objects
in $\mathcal{F}\cup\mathcal{P}$, there are at most $4$ diamonds induced by
this quadruple as above, as there are at most $2$ type-1 singular faces for
$(p_{1},p_{2},p_{1}^{\prime})$, and similarly, for
$(p_{1},p_{2},p_{1}^{\prime})$. Therefore, the total probability that in
$\mathrm{Diag}_{\mathcal{S}}$ there is a heavy diamond with both endpoints
being singular faces of type 1 and $p_{1}^{\prime}\neq p_{2}^{\prime}$ is
bounded by:

$\displaystyle
4\varepsilon^{100}\cdot\sum_{p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime}\in\mathcal{F}\cup\mathcal{P}}q_{p_{1}}q_{p_{2}}q_{p_{1}^{\prime}}q_{p_{2}^{\prime}}$
$\displaystyle\leqslant
4\varepsilon^{100}\cdot\left(\sum_{p\in\mathcal{F}\cup\mathcal{P}}q_{p}\right)^{4}$
$\displaystyle\leqslant
4\varepsilon^{100}\cdot\left(|\mathcal{P}|+s\right)^{4}\leqslant
4\cdot\varepsilon\leqslant 10^{-3}.$

The reasoning for the case when $p_{1}^{\prime}=p_{2}^{\prime}$ is analogous;
the bound is even better as we sum over triples instead of quadruples. The
proofs for the cases when $f_{1}$ or $f_{2}$ is a face of type $2$ or $3$ are
similar; the type $3$ we would consider a quadruple of objects for the
respective branching point instead of a triple, so for instance the case when
both $f_{1}$ and $f_{2}$ are of type $3$ would involve summation over
$8$-tuples of objects. Due to the appearance of the $\varepsilon^{100}$
factor, the probability in every case can be bounded by $10^{-3}$. Moreover,
the number of different cases is bounded by $250$, so summing all the
probabilities we can conclude that the probability that
$\mathrm{Diag}_{\mathcal{S}}$ contains a heavy diamond is at most
$\frac{1}{4}$. ∎

##  Appendix B Finding balanced cycles in the radial graph

This section is dedicated to the proof of the following separator statement
for Voronoi diagrams.

See 3.6

Our proof of Theorem 3.6 is a rather straightforward modification of the proof
of [18, Theorem 4.15 and Lemma 4.18]. The main caveat is that in [18, Section
4], Pilipczuk and Marx consider only the setting of unweighted graphs, and
need balancedness with respect to either the number of edges or of faces.
Here, we consider the vertex-weighted setting, hence the reasoning has to be
adjusted. The remainder of this section is dedicated to the proof of Theorem
3.6.

#### Nooses.

Before we start, we need to recall the notion of a _noose_ and its main
properties; this recollection is a close-to-verbatim citation of the
discussion in [18, Section 4.6]. Let $H$ be a connected graph embedded in the
sphere $\mathbb{S}^{2}$. A noose in $H$ is a closed, directed curve $\sigma$
on $\mathbb{S}^{2}$ without self-crossings that only intersects $H$ at its
vertices and visits every face of $H$ at most once. When we remove $\sigma$
from the sphere $\mathbb{S}^{2}$, it divides the sphere into two open disks:
one for which $\sigma$ represents the clockwise traversal of the perimeter,
and the other for which it represents the counterclockwise traversal (assuming
a fixed orientation of $\mathbb{S}^{2}$). Following the notation of [20], we
shall call the first disk $\mathrm{Enc}(\sigma)$ (for _enclosed_), and the
second disk we call $\mathrm{Exc}(\sigma)$ (for _excluded_). The length of a
noose is the number of vertices of $H$ it crosses.

We will use the following variant of a balanced noose lemma.

######  Lemma B.1.

Let $H$ be a connected $3$-regular multigraph embedded in the sphere
$\mathbb{S}^{2}$. Let $\omega$ be an assignment of nonnegative weights to the
vertices of $H$ such that the total sum of the weights is $1$. Then there
exists a noose $\sigma$ of length at most $\sqrt{\frac{9}{2}|V(H)|}$ such that
the total weight of vertices lying inside $\mathrm{Enc}(\sigma)$ is at most
$2/3$, and the same holds for the vertices lying inside
$\mathrm{Exc}(\sigma)$.

The proof of Lemma B.1 is essentially a repetition of the proof of [18,
Theorem 4.15], so we only highlight the necessary minor modifications. There
are two differences between Lemma B.1 and [18, Theorem 4.15]:

  1. (i)

in [18, Theorem 4.15] the balancedness is measured in terms of edges of $H$
instead of vertices; and

  2. (ii)

[18, Theorem 4.15] considers the unweighted setting where every edge of $H$
has a unit weight.

These two differences can be mitigated as follows.

In the proof of [18, Theorem 4.15] one considers the decomposition of $H$ into
bridgeless components and identifies a central bridgeless component
$B_{x_{0}}$: a bridgeless component such that the total weight of every
component of $G-B_{x_{0}}$ is at most $1/2$. There is an easy corner case when
$B_{x_{0}}$ consists of just one vertex, which can be resolved in exactly the
same way in our setting when the diagram is vertex-weighted. So let us assume
that $B_{x_{0}}$ consists of more than one vertex.

Observe that if for any component $C$ of $G-B_{x_{0}}$ the total weight of
vertices in $C$ is between $1/3$ and $1/2$, then we can easily construct a
noose of length $1$ with the desired balancedness property as follows: the
noose travels through the unique face lying on both sides of the bridge
connecting $C$ and $B_{x_{0}}$, and crosses the endpoint of that bridge that
belongs to $B_{x_{0}}$. Hence, we may assume that for each component $C$ of
$G-B_{x_{0}}$, the total weight of the vertices of $C$ is at most $1/3$.

Next, in [18, Theorem 4.15] one considers the induced subgraph $G[B_{x_{0}}]$
(we consider $B_{x_{0}}$ to be a subset of vertices of $G$) and constructs a
weight function on the edges of this subgraph as follows. For every connected
component $C$ of $G-B_{x_{0}}$, say connected to $B_{x_{0}}$ through a bridge
$fg$ where $g\in B_{x_{0}}$, we assign all the edges of $C$ (including the
bridge $fg$) to one of the edges of $G[B_{x_{0}}]$ incident to $g$. Then the
weight of an edge $e\in E(G[B_{x_{0}}])$ is equal to $1$ plus the total number
of edges assigned to $e$. In our vertex-weighted setting, we can just assign
the total weight of vertices in $C$ to the vertex $g$, so that its new weight
becomes the original weight plus the total weight of vertices in $C$.

Now that $G[B_{x_{0}}]$ is bridgeless, one can find a balanced noose (which is
a noose in the sphere drawing of $G[B_{x_{0}}]$) using known results about the
existence of sphere-cut decompositions in bridgeless planar multigraphs. In
[18, Theorem 4.15] the noose is balanced with respect to the edge weights, but
exactly the same proof strategy also yields a noose $\gamma$ such that the
total weight of the vertices of $B_{x_{0}}$ strictly enclosed by $\gamma$ is
at most $2/3$, and the same holds also for the vertices of $B_{x_{0}}$
strictly excluded by $\gamma$.

The last step in the proof is to lift the noose $\gamma$ — which is a noose in
the sphere drawing of $G[B_{x_{0}}]$ — to a noose $\gamma^{\prime}$ in the
sphere drawing of $G$. This boils down to deciding, for every component $C$ of
$G-B_{x_{0}}$ such that $\gamma$ crosses the vertex of $B_{x_{0}}$ adjacent to
$C$, whether $C$ should be placed so that it is entirely enclosed or entirely
excluded by $\gamma^{\prime}$. Since the total weight of every such $C$ is at
most $1/3$, it is not difficult to see that by investigating the components
$C$ one by one, and always assigning them to the side of $\gamma^{\prime}$
that is currently lighter, we do not break the $2/3$-balancedness property.
Hence, the noose $\gamma^{\prime}$ constructed at the end will be
$2/3$-balanced, as required.

Equipped with Lemma B.1, we continue the proof of Theorem 3.6. Let $\sigma$ be
the noose given by Lemma B.1 for the diagram
$H\coloneqq\mathrm{Diag}_{\mathcal{S}}$ (which, recall, is a connected sphere-
embedded $3$-regular multigraph). Analogously to [18], we define a cycle
$C=C(\sigma)$ in $\mathrm{Rad}_{\mathcal{S}}$ as follows. Suppose $\sigma$
visits faces and branching points
$f_{1}^{\ast},f_{1},f_{2}^{\ast},f_{2},\ldots,f_{r}^{\ast},f_{r}$ in this
order, where $f_{i}^{\ast}$ are different faces of $H$, and $f_{i}$ are
different branching points of $H$. Recall that faces of $H$ correspond to
objects of $\mathcal{F}$. Therefore, let $p_{1},\ldots,p_{r}\in\mathcal{F}$ be
the objects that correspond to $f_{1}^{\ast},\ldots,f_{r}^{\ast}$,
respectively.

Next, consider any $i\in\\{1,\ldots,r\\}$. Upon leaving face $f_{i}^{\ast}$,
noose $\sigma$ enters branching point $f_{i}$ through one of three regions in
a close neighborhood of $f_{i}$, separated by the edges of $H$ incident to
$f_{i}$. Each of these three regions corresponds in a natural way to one of
the vertices of $f_{i}$ (which, recall, is a triangular face of $G$); see also
the discussion in [18, Section 4.8] for a formal treatment. Therefore, we
define $u_{i}$ to be the vertex of $f_{i}$ that corresponds to the region
through which $\sigma$ enters $f_{i}$ from $f_{i}^{\ast}$. Analogously, we
define $v_{i}$ to be the vertex of $f_{i}$ that corresponds to the region
through which $\sigma$ enters face $f_{i+1}^{\ast}$ from branching point
$f_{i}$ (with indices behaving cyclically).

We now may define the cycle $C=C(\sigma)$ naturally: the consecutive edges of
$\mathrm{Diag}_{\mathcal{S}}$ traversed by $C$ are the edge $p_{i}f_{i}$ with
label $u_{1}$ and the edge $f_{i}p_{i+1}$ with label $v_{1}$, for
$i=1,\ldots,r$ (indices behave cyclically). Since $\sigma$ visits every face
of $\mathrm{Diag}_{\mathcal{S}}$ and every branching point of
$\mathrm{Diag}_{\mathcal{S}}$ at most once, it is clear that $C$ is a cycle in
$\mathrm{Diag}_{\mathcal{S}}$. Moreover, the balancedness assertion provided
by Lemma B.1 and the construction immediately imply the balancedness property
asserted in the statement of Theorem 3.6. Finally, the length of $C$ is twice
larger than the length of $\sigma$, hence it is bounded by $\sqrt{18|V(H)|}$.
So the proof of Theorem 3.6 is complete.