The work in this paper is supported by the Dutch Research Council (NWO)
through Gravitation-grant NETWORKS-024.002.003. Department of Computer
Science, TU Eindhoven, the<EMAIL_ADDRESS>Institute for
Theoretical Studies, ETH Zürich, Switzerlandsandor.kisfaludibak@eth-
its.ethz.ch Department of Computer Science, TU Eindhoven, the
<EMAIL_ADDRESS>Department of Computer Science, TU Eindhoven,
the<EMAIL_ADDRESS>Mark de Berg and Sándor Kisfaludi-Bak and
Morteza Monemizadeh and Leonidas Theocharous [100]Theory of computation Design
and analysis of algorithms John Q. Open and Joan R. Access 2 42nd Conference
on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016
Little Whinging, United Kingdom 42 23

# Clique-Based Separators for Geometric Intersection Graphs

Mark de Berg  Sándor Kisfaludi-Bak111The research was conducted while the
author was at the Max Planck Institute for Informatics, Saarbrücken, Germany.
Morteza Monemizadeh  Leonidas Theocharous

###### Abstract

Let $F$ be a set of $n$ objects in the plane and let $\mathcal{G}^{\times}(F)$
be its intersection graph. A balanced clique-based separator of
$\mathcal{G}^{\times}(F)$ is a set $\mathcal{\mathcal{S}}$ consisting of
cliques whose removal partitions $\mathcal{G}^{\times}(F)$ into components of
size at most $\delta n$, for some fixed constant $\delta<1$. The weight of a
clique-based separator is defined as
$\sum_{C\in\mathcal{\mathcal{S}}}\log(|C|+1)$. Recently De Berg et al.(SICOMP
2020) proved that if $S$ consists of convex fat objects, then
$\mathcal{G}^{\times}(F)$ admits a balanced clique-based separator of weight
$O(\sqrt{n})$. We extend this result in several directions, obtaining the
following results.

  * •

Map graphs admit a balanced clique-based separator of weight $O(\sqrt{n})$,
which is tight in the worst case.

  * •

Intersection graphs of pseudo-disks admit a balanced clique-based separator of
weight $O(n^{2/3}\log n)$. If the pseudo-disks are polygonal and of total
complexity $O(n)$ then the weight of the separator improves to $O(\sqrt{n}\log
n)$.

  * •

Intersection graphs of geodesic disks inside a simple polygon admit a balanced
clique-based separator of weight $O(n^{2/3}\log n)$.

  * •

Visibility-restricted unit-disk graphs in a polygonal domain with $r$ reflex
vertices admit a balanced clique-based separator of weight
$O(\sqrt{n}+r\log(n/r))$, which is tight in the worst case.

These results immediately imply sub-exponential algorithms for Maximum
Independent Set (and, hence, Vertex Cover), for Feedback Vertex Set, and for
$q$-Coloring for constant $q$ in these graph classes.

###### keywords:

Computational geometry, intersection graphs, separator theorems

##  1 Introduction

The famous Planar Separator Theorem states that any planar graph
$\mathcal{G}=(V,E)$ with $n$ nodes222We use the terms _nod_ e and _arc_ when
talking about graphs, and _vertex_ and _edge_ for geometric objects. admits a
subset $\mathcal{\mathcal{S}}\subset V$ of size $O(\sqrt{n})$ nodes whose
removal decomposes $\mathcal{G}$ into connected components of size at most
$2n/3$. The subset $\mathcal{\mathcal{S}}$ is called a balanced333For a
separator to be balanced it suffices that the components have size at most
$\delta n$ for some constant $\delta<1$. When we speak of separators, we
always mean balanced separators, unless stated otherwise. _separator_ of
$\mathcal{G}$. The theorem was first proved in 1979 by Lipton and Tarjan [21],
and it has been instrumental in the design of algorithms for planar graphs: it
has been used to design efficient divide-and-conquer algorithms, to design
sub-exponential algorithms for various np-hard graph problems, and to design
approximation algorithms for such problems.

The Planar Separator Theorem has been extended to various other graph classes.
Our interest lies in _geometric intersection graphs_ , where the nodes
correspond to geometric objects and there is an arc between two nodes iff the
corresponding objects intersect. If the objects are disks, the resulting graph
is called a _disk graph_. Disk graphs, and in particular unit-disk graphs, are
a popular model for wireless communication networks and have been studied
extensively. Miller et al. [25] and Smith and Wormald [30] showed that if $F$
is a set of balls in $\mathbb{R}^{d}$ of ply at most $k$—the _ply_ of $F$ is
the maximum number of objects in $F$ with a common intersection—then the
intersection graph of $F$ has a separator of size $O(k^{1/d}n^{1-1/d})$. This
was generalized by Chan [6] and Har-Peled and Quanrud [16] to intersection
graphs of so-called low-density sets. Separators for string graphs—a string
graph is an intersection graph of sets of curves in the plane—have also been
considered [15, 20, 24], with Lee [20] showing that a separator of size
$O(\sqrt{m})$ exists, where $m$ is the number of arcs of the graph.

Even for simple objects such as disks or squares, one must restrict the ply to
obtain a separator of small size. Otherwise the objects can form a single
clique, which obviously does not have a separator of sublinear size. To design
subexponential algorithms for problems such as Maximum Independent Set,
however, one can also work with a separator consisting of a small number of
cliques instead of a small number of nodes. Such _clique-based separators_
were introduced recently by De Berg et al. [11]. Formally, a clique-based
separator of a graph $\mathcal{G}$ is a collection $\mathcal{\mathcal{S}}$ of
node-disjoint cliques whose union is a balanced separator of $\mathcal{G}$.
The _weight_ of $\mathcal{\mathcal{S}}$ is defined as
$\mathrm{weight}(\mathcal{\mathcal{S}}):=\sum_{C\in\mathcal{\mathcal{S}}}\log(|C|+1)$.
De Berg et al.[11] proved that the intersection graph of any set $F$ of $n$
convex fat objects in the plane admits a clique-based separator of weight
$O(\sqrt{n})$, and they used this to obtain algorithms with running time
$2^{O(\sqrt{n})}$ for many classic np-hard problems on such graphs. This
running time is optimal, assuming the Exponential-Time Hypothesis (ETH). The
result generalizes to convex fat objects in $\mathbb{R}^{d}$, where the bound
on the weight of the clique-based separator becomes $O(n^{1-1/d})$.

The goal of our paper is to investigate whether similar results are possible
for non-fat objects in the plane. Note that not all intersection graphs admit
clique-based separators of small weight. String graphs, for instance, can have
arbitrarily large complete bipartite graphs as induced subgraphs, in which
case any balanced clique-based separator has weight $\Omega(n)$.

The first type of intersection graphs we consider are map graphs, which are a
natural generalization of planar graphs. The other types are generalizations
of disk graphs. One way to generalize disk graphs is to consider fat objects
instead of disks, as done by De Berg et al. [11]. We will study three other
generalizations, involving non-fat objects: pseudo-disks, geodesic disks, and
visibility-restricted unit disks. Next we define the graph classes we consider
more precisely; see Fig. 1 for an example of each graph class.

Figure 1: A map graph, a pseudo-disk graph, a geodesic-disk graph, and a
visibility restricted unit-disk graph. For the latter class, the grey disks in
the picture have radius $\frac{1}{2}$.

In the following, we use $\mathcal{G}^{\times}(F)$ to denote the intersection
graph induced by a set $F$ of objects. For convenience, we do not distinguish
between the objects and the corresponding nodes, so we use $F$ to denote the
set of objects as well as the set of nodes in $\mathcal{G}^{\times}(F)$. We
assume that the objects in $F$ are connected, bounded, and closed.

_Map graphs._ Let $\mathcal{M}$ be a planar subdivision and $F$ be its set of
faces. The graph with node set $F$ that has an arc between every pair of
neighboring faces is called the _dual graph_ of $\mathcal{M}$, and it is
planar. Here two faces are neighbors if their boundaries have an edge of the
subdivision in common. A _map graph_ [8] is defined similarly, except now two
faces are neighbors even if their boundaries meet in a single point.
Alternatively, we can define a map graph as the intersection graph of a set
$F$ of interior-disjoint regions in the plane. Since arbitrarily many faces
can share a vertex on their boundary, map graphs can contain arbitrarily large
cliques. If at most $k$ faces meet at each subdivision vertex, the graph is
called a _$k$ -map graph_. Chen [7] proved that any $k$-map graph has a
(normal, not clique-based) separator of size $O(\sqrt{kn})$, which is also
implied by Lee’s recent result on string graphs [20].

_Pseudo-disk graphs._ A set $F$ of objects is a set of pseudo-disks if for any
$f,f^{\prime}\in F$ the boundaries $\partial f$ and $\partial f^{\prime}$
intersect at most twice. Pseudo-disks were introduced in the context of motion
planning by Kedem et al. [17], who proved that the union complexity of $n$
pseudo-disks is $O(n)$. Since then they have been studied extensively. We
consider two types of pseudo-disks: polygonal pseudo-disks with $O(n)$
vertices in total, and arbitrary pseudo-disks.

_Geodesic-disk graphs and visibility-restricted unit-disk graphs._ As
mentioned, unit-disk graphs are popular models for wireless communication
networks. We consider two natural generalizations of unit-disk graphs, which
can be thought of as communication networks in a polygonal environment that
may obstruct communication.

  * •

_Geodesic-disk graphs_ in a simple polygon $P$ are intersection graphs of
geodesic disks inside $P$. (The _geodesic disk_ with center $q\in P$ and
radius $r$ is the set of all points in $P$ at geodesic distance at most $r$
from $q$, where the geodesic distance between two points is the length of the
shortest path between them inside $P$.)

  * •

In _visibility-restricted unit-disk graphs_ the nodes correspond to a set $Q$
of $n$ points inside a polygon $P$, which may have holes, and two points
$p,q\in Q$ are connected by an arc iff $|pq|\leqslant 1$ and $p$ and $q$ see
each other (meaning that $pq\subset P$).444Visibility-restricted unit-disk
graphs are, strictly speaking, not intersection graphs. In particular, if
$R_{q}$ is defined as the region of points within $P$ that are visible from
$q$ and lie within distance $1/2$, then the visibility-restricted unit-disk
graph is _not_ the same as the intersection graph of the objects $R_{q}$. A
more general, directed version of such graphs was studied by Ben-Moshe et al.
[2] under the name range-restricted visibility graph. They presented an
output-sensitive algorithm to compute the graph.

Our results: clique-based separator theorems. So far, clique-based separators
were studied for fat objects: De Berg et al. [11] consider convex or
similarly-sized fat objects, Kisfaludi-Bak et al.[19] study how the fatness of
axis-aligned fat boxes impacts the separator weight, and Kisfaludi-Bak [18]
studies balls in hyperbolic space. The $O(\sqrt{n})$ bound on the separator
weight is tight even for unit-disk graphs. Indeed, a $\sqrt{n}\times\sqrt{n}$
grid graph can be realized as a unit-disk graph, and any separator of such a
grid graph must contain $\Omega(\sqrt{n})$ nodes. Since the maximum clique
size in a grid graph is two, any separator must contain $\Omega(\sqrt{n})$
cliques. All graph classes we consider can realize a $\sqrt{n}\times\sqrt{n}$
grid graph, so $\Omega(\sqrt{n})$ is a lower bound on the weight of the
clique-based separators we consider. We obtain the following results.

In Section 2 we show that any map graph has a clique-based separator of weight
$O(\sqrt{n})$. This gives the first ETH-tight algorithms for Maximum
Independent Set (and, hence, Vertex Cover), Feedback Vertex Set, and Coloring
in map graphs; see below.

In Section 3 we show that any intersection graph of pseudo-disks has a clique-
based separator of weight $O(n^{2/3}\log n)$. If the pseudo-disks are
polygonal and of total complexity $O(n)$ then the weight of the separator
improves to $O(\sqrt{n}\log n)$.

In Section 4 we consider intersection graphs of geodesic disks inside a simple
polygon. At first sight, geodesic disks seem not much harder to deal with than
fat objects: they can have skinny parts only in narrow corridors and then
packing arguments may still be feasible. Unfortunately another obstacle
prevents us from applying a packing argument: geodesic distances in a simply
connected polygon induce a metric space whose doubling dimension depends on
the number of reflex vertices of the polygon. Nevertheless, by showing that
geodesic disks inside a simple polygon behave as pseudo-disks, we are able to
obtain a clique-based separator of weight $O(n^{2/3}\log n)$, independent of
the number of reflex vertices.

In Section 5 we study visibility-restricted unit-disk graphs. We give an
$\Omega(\min(n,r\log(n/r))+\sqrt{n})$ lower bound for the separator weight,
showing that a clique-based separator whose weight depends only on $n$, the
number of points defining the visibility graph, is not possible. We then show
how to construct a clique-based separator of weight
$O(\min(n,r\log(n/r))+\sqrt{n})$.

All separators can be computed in polynomial time. For map graphs and for the
pseudo-disk intersection graphs, we assume the objects have total complexity
$O(n)$. If the objects have curved edges, we assume that basic operations
(such as computing the intersection points of two such curves) take $O(1)$
time.

Applications. In Section 6 we apply our separator theorems to obtain
subexponential algorithms for Maximum Independent Set, Feedback Vertex Set,
and $q$-Coloring for constant $q$ in the graph classes discussed above. The
crucial property of these problems that makes our separator applicable, is
that the possible ways in which a solution can “interact” with a clique of
size $k$ is polynomial in $k$. We use known techniques (mostly from De Berg et
al. [11]) to solve the three problems on any graph class that has small
clique-based separators.

All our graph classes are subsumed by string graphs. Bonnet and Rzazewski [4]
showed that string graphs have $2^{O(n^{2/3}\log n)}$ algorithms for Maximum
Independent Set and $3$-Coloring, and a $2^{n^{2/3}\log^{O(1)}n}$ algorithm
for Feedback Vertex Set, and that string graphs do not have subexponential
algorithms for $q$-Coloring with $q\geqslant 4$ under ETH. One can also obtain
subexponential algorithms in some of our classes from results of Fomin et al.
[14, 7] or Marx and Philipczuk [22]. The running times we obtain match or
slightly improve the results that can be obtained from these existing results.
It should be kept in mind, however, that the existing results are for more
general graph classes. An exception are our results on map graphs, which were
explicitly studied before and where we improve the running time for Maximum
Independent Set and Feedback Vertex Set from $2^{O(\sqrt{n}\log n)}$ to
$2^{O(\sqrt{n})}$. (But, admittedly, the existing results apply in the
parameterized setting while ours don’t.) In any case, the main advantage of
our approach is that it allows us to solve Maximum Independent Set, Feedback
Vertex Set and $q$-Coloring on each of the mentioned graph classes in a
uniform manner.

##  2 Map graphs

Recall that a map graph is the intersection graph of a set $F$ of interior-
disjoint objects in the plane. We construct a clique-based separator for
$\mathcal{G}^{\times}(F)$ in four steps. First, we construct a bipartite plane
_witness graph_ $\mathcal{H}_{1}$ with node set $P\cup Q$, where the nodes in
$P$ correspond to the objects in $F$ and the nodes in $Q$ (with their incident
arcs) model the adjacencies in $\mathcal{G}^{\times}(F)$. Next, we replace
each node $q\in Q$ by a certain gadget whose “leaves” are the neighbors of
$q$, and we triangulate the resulting graph. We then apply the Planar
Separator Theorem to obtain a separator for the resulting graph
$\mathcal{H}_{2}$. Finally, we turn the separator for $\mathcal{H}_{2}$ into a
clique-based separator for $\mathcal{G}^{\times}(F)$. Next we explain these
steps in detail.

Step 1: Creating a witness graph. To construct a witness graph for
$\mathcal{G}^{\times}(F)$ we use the method of Chen et al. [8]: take a point
$p_{f}$ in the interior of each object $f\in F$, and take a _witness point_
$q\in\partial f\cap\partial f^{\prime}$ for each pair of touching objects
$f,f^{\prime}\in F$ and add arcs from $q$ to the points $p_{f}$ and
$p_{f^{\prime}}$.

Figure 2: (i) A witness graph for the map graph induced by the grey regions.
Points in $P$ are blue, points in $Q$ are red. (ii) The gadget used to replace
a witness point. The edges of $\mathcal{T}_{q}$ are black, the cycles
connecting nodes at the same level are grey and thick, the edges to
triangulate the 4-cycle are grey and thin. (iii) The green paths show an
example of how the separator can intersect a gadget. (Note that the tree
“wraps around”, as in part (ii) of the figure; see also one of the green
paths.) The objects added to the clique $C_{q}$ correspond to the leaves
indicated by the blue rectangles.

Let $P=\\{p_{f}:f\in F\\}$ and let $Q$ be the set of all witness points added.
We denote the resulting bipartite graph with node set $P\cup Q$ by
$\mathcal{H}_{1}$; see Figure 2(i) for an example. Observe that points where
many objects meet can serve as witness points for many neighboring pairs in
$\mathcal{G}^{\times}(F)$. Chen et al. [8, Lemma 2.3] proved that any map
graph admits a witness set $Q$ of size $O(n)$. If the objects in $F$ are
polygons with $O(n)$ vertices in total then $Q$ can be found in $O(n)$ time
(since the vertices can serve as the set $Q$.)

Step 2: Replacing witness points by gadgets and triangulating. We would like
to construct a separator for $\mathcal{H}_{1}$ using the Planar Separator
Theorem, and convert it to a clique-based separator for
$\mathcal{G}^{\times}(F)$. For every witness point $q\in Q$ in the separator
for $\mathcal{H}_{1}$, the conversion would add a clique $C_{q}$ to the
clique-based separator, namely, the clique corresponding to all objects $f\in
F$ such that $p_{f}$ is adjacent to $q$. However, the node $q$ adds 1 to the
separator size, but the clique $C_{q}$ adds $\log(|C_{q}|+1)$ to the weight of
the clique-based separator. To deal with this we modify $\mathcal{H}_{1}$, as
follows.

Consider a node $q\in Q$. Let $N(q)\subseteq P$ denote the set of neighbors of
$q$. For all nodes $q\in Q$ with $|N(q)|\geqslant 3$, we replace the star
induced by $\\{q\\}\cup N(q)$ by a gadget $G_{q}$, which is illustrated in
Figure 2(ii) and defined as follows.

First, we create a tree $\mathcal{T}_{q}$ with root $q$ and whose leaves are
the nodes in $N(q)$, as follows. Define the _level_ $\ell(v)$ of a node $v$ in
$\mathcal{T}_{q}$ to be the distance of $v$ to the root; thus the root has
level 0, its children have level 1, and so on. All leaves in $\mathcal{T}_{q}$
are at the same level, denoted $\ell_{\max}$. The root has degree 3, nodes at
level $\ell$ with $1\leqslant\ell<\ell_{\max}-1$ have degree 2, and nodes at
level $\ell_{\max}-1$ have degree 2 or 1. For each $\ell<\ell_{\max}$ we
connect the nodes at level $\ell$ into a cycle. After doing so, all faces in
the gadget (except the outer face) are triangles or 4-cycles. We finish the
construction by adding a diagonal in each 4-cycle. Define the _height_ of a
node $v$ as $0pt(v):=\ell_{\max}-\ell(v)$. The following observation follows
from the construction. Let $v$ be a node at height $h>0$ in the gadget
$G_{q}$.

  1. (i)

The subtree of $\mathcal{T}_{q}$ rooted at $v$, denoted $\mathcal{T}_{q}(v)$,
has at most $3\cdot 2^{h-1}$ leaves.

  2. (ii)

The distance from $v$ to any leaf in $\mathcal{T}_{q}$ is at least $h$.

To unify the exposition, it will be convenient to also create a gadget for the
case where $q$ has only two neighbors in $\mathcal{H}_{1}$, say $p_{f}$ and
$p_{f^{\prime}}$. We then define $\mathcal{T}_{q}$ to consist of the arcs
$(q,p_{f})$ and $(q,p_{f^{\prime}})$. Note that Observation 2 holds for this
gadget as well.

By replacing each witness point $q\in Q$ with a gadget $G_{q}$ as above, we
obtain a (still planar) graph. We triangulate this graph to obtain a maximal
planar graph $\mathcal{H}_{2}$.

Step 3: Constructing a separator for $\mathcal{H}_{2}$. We now want to apply
the Planar Separator Theorem to $\mathcal{H}_{2}$. Our final goal is to obtain
a balanced clique-based separator for $\mathcal{G}^{\times}(F)$. Hence, we
want the separator for $\mathcal{H}_{2}$ to be balanced with respect to $P$.
We will also need the separator for $\mathcal{H}_{2}$ to be connected. Both
properties are guaranteed by the following version of the Planar Separator
Theorem, which was proved by Djidjev and Venkatesan [13].

> Planar Separator Theorem. Let $\mathcal{G}=(V,E)$ be a maximal planar graph
> with $n$ nodes. Let each node $v\in V$ have a non-negative cost, denoted
> $\mathrm{cost}(v)$, with $\sum_{v\in V}\mathrm{cost}(v)=1$. Then $V$ can be
> partitioned in $O(n)$ time into three sets $A,B,\mathcal{\mathcal{S}}$ such
> that (i) $\mathcal{\mathcal{S}}$ is a simple cycle of size $O(\sqrt{n})$,
> (ii) $\mathcal{G}$ has no arcs between a node in $A$ and a node in $B$, and
> (iii) $\sum_{v\in A}\mathrm{cost}(v)\leqslant 2/3$ and $\sum_{v\in
> B}\mathrm{cost}(v)\leqslant 2/3$.

When applying the Planar Separator Theorem to $\mathcal{H}_{2}$, we set
$\mathrm{cost}(p):=1/n$ for all nodes $p_{f}\in P$ and $\mathrm{cost}(v):=0$
for all other nodes. We denote the resulting separator for $\mathcal{H}_{2}$
by $\mathcal{\mathcal{S}}(\mathcal{H}_{2})$ and the node sets inside and
outside the separator by $A(\mathcal{H}_{2})$ and $B(\mathcal{H}_{2})$,
respectively.

Step 4: Turning the separator for $\mathcal{H}_{2}$ into a clique-based
separator for $\mathcal{G}^{\times}(F)$. We convert
$\mathcal{\mathcal{S}}(\mathcal{H}_{2})$ into a clique-based separator
$\mathcal{\mathcal{S}}$ for $\mathcal{G}^{\times}(F)$ as follows.

  * •

For each node $p_{f}\in\mathcal{\mathcal{S}}(\mathcal{H}_{2})\cap P$ we put
the (singleton) clique $\\{f\\}$ into $\mathcal{\mathcal{S}}$.

  * •

For each gadget $G_{q}$ we proceed as follows. Let $V_{q}$ be the set of all
nodes $v\in\mathcal{T}_{q}$ that are in
$\mathcal{\mathcal{S}}(\mathcal{H}_{2})$, and define $C_{q}:=\\{f\in
F:\mbox{$p_{f}$ is a leaf of $\mathcal{T}_{q}(v)$ that has an ancestor in
$V_{q}$}\\}$; see Figure 2(iii). Observe that $C_{q}$ is a clique in
$\mathcal{G}^{\times}(F)$. We add555We tacitly assume that if an object is in
multiple cliques in $\mathcal{\mathcal{S}}$, we remove all but one of its
occurrences. $C_{q}$ to $\mathcal{\mathcal{S}}$.

The clique-based separator $\mathcal{\mathcal{S}}$ induces a partition of
$F\setminus\bigcup_{C\in\mathcal{\mathcal{S}}}C$ into two parts $A$ and $B$,
with $|A|,|B|\leqslant 2n/3$, in a natural way, namely as $A:=\\{f\in
F:f\not\in\bigcup_{C\in\mathcal{\mathcal{S}}}C\mbox{ and }p_{f}\in
A(\mathcal{H}_{2})\\}$ and $B:=\\{f\in
F:f\not\in\bigcup_{C\in\mathcal{\mathcal{S}}}C\mbox{ and }p_{f}\in
B(\mathcal{H}_{2})\\}$. The following lemma ensures that
$\mathcal{\mathcal{S}}$ is a valid separator.

######  Lemma 2.1.

There are no arcs in $\mathcal{G}^{\times}(F)$ between a node in $A$ and a
node in $B$.

######  Proof 2.2.

Suppose for a contradiction that there are objects $f\in A$ and $f^{\prime}\in
B$ such that $(f,f^{\prime})$ is an arc in $\mathcal{G}^{\times}(F)$. Let
$q\in Q$ be a witness point for the arc $(f,f^{\prime})$; thus $(p_{f},q)$ and
$(p_{f^{\prime}},q)$ are arcs in $\mathcal{H}_{1}$. Consider the gadget
$G_{q}$ and the tree $\mathcal{T}_{q}$. Let $\pi$ denote the path from $p_{f}$
to $p_{f^{\prime}}$ in $\mathcal{T}_{q}$. Note that none of the nodes on $\pi$
can be in $\mathcal{\mathcal{S}}(\mathcal{H}_{2})$, otherwise $V_{q}$ contains
an ancestor of $p_{f}$ or of $p_{f^{\prime}}$, and (at least) one of the nodes
$p_{f},p_{f^{\prime}}$ is in a clique that was added to
$\mathcal{\mathcal{S}}$. But then the nodes $p_{f},p_{f^{\prime}}$ are still
connected in $\mathcal{H}_{2}$ after the removal of
$\mathcal{\mathcal{S}}(\mathcal{H}_{2})$. Hence, we have
$p_{f},p_{f^{\prime}}\in A(\mathcal{H}_{2})$ or $p_{f},p_{f^{\prime}}\in
B(\mathcal{H}_{2})$, both contradicting that $f\in A$ and $f^{\prime}\in B$.

It remains to prove that $\mathcal{\mathcal{S}}$ has the desired weight.

######  Lemma 2.3.

The total weight of the separator $\mathcal{\mathcal{S}}$ satisfies
$\sum_{C\in\mathcal{\mathcal{S}}}\log(|C|+1)=O(\sqrt{n})$.

######  Proof 2.4.

Since $\mathcal{\mathcal{S}}(\mathcal{H}_{2})$ contains $O(\sqrt{n})$ nodes,
it suffices to bound the total weight of the cliques added for the gadgets
$G_{q}$. Consider a gadget $G_{q}$. Recall that $V_{q}$ is the set of all
nodes $v\in\mathcal{T}_{q}$ that are in
$\mathcal{\mathcal{S}}(\mathcal{H}_{2})$. We claim that
$\log(|C_{q}|+1)=O(|V_{q}|)$, which implies that
$\sum_{q}\log(|C_{q}|+1)=\sum_{q}O(|V_{q}|)=O(\sqrt{n}),$ as desired. It
remains to prove the claim.

Since $\mathcal{\mathcal{S}}(\mathcal{H}_{2})$ is a simple cycle, its
intersection with $G_{q}$ consists of one or more paths. Each path $\pi$
enters and exits $G_{q}$ at a node in $N(q)$. Let $D_{\pi}$ denote the set of
all descendants of the nodes in $\pi$. We will prove that
$\log(|D_{\pi}|+1)=O(|\pi|)$, where $|\pi|$ denotes the number of nodes of
$\pi$. This implies the claim since
$\log(|C_{q}|+1)\leqslant\sum_{\pi}\log(|D_{\pi}|+1)=\sum_{\pi}O(|\pi|)=O(|V_{q}|).$

To prove that $\log(|D_{\pi}|+1)=O(|\pi|)$, let $h_{\max}$ be the maximum
height of any node in $\pi$. Thus $|\pi|\geqslant h_{\max}$ by Observation
2(ii). Consider all subtrees of height $h_{\max}$ in $\mathcal{T}_{q}$. If
$\pi$ visits $t$ such subtrees, then $|\pi|\geqslant t$. Moreover,
$|D_{\pi}|\leqslant 3t\cdot 2^{h_{\max}-1}$ by Observation 2(i). Hence,
$\log(|D_{\pi}|+1)\leqslant\log\left(3t\cdot
2^{h_{\max}-1}+1\right)<h_{\max}+\log(3t)=O(\max(h_{\max},t))=O(|\pi|).$

By putting everything together we obtain the following theorem.

######  Theorem 2.5.

Let $F$ be a set of $n$ interior-disjoint regions in the plane. Then the
intersection graph $\mathcal{G}^{\times}(F)$ has a clique-based balanced
separator of weight $O(\sqrt{n})$. The separator can be computed in $O(n)$
time, assuming that the total complexity of the objects in $F$ is $O(n)$.

##  3 Pseudo-disk graphs

Our clique-based separator construction for a set $F$ of pseudo-disks uses so-
called planar supports, defined as follows. Let $\mathcal{H}$ be a hypergraph
with node set $Q$ and hyperedge set $H$. A graph $\mathcal{G}_{\mathrm{sup}}$
is a _planar support_ [29] for $\mathcal{H}$ if $\mathcal{G}_{\mathrm{sup}}$
is a planar graph with node set $Q$ such that for any hyperedge $h\in H$ the
subgraph of $\mathcal{G}_{\mathrm{sup}}$ induced by the nodes in $h$ is
connected. In our application we let the node set $Q$ correspond to a set of
points stabbing all pairwise intersections between the pseudo-disks, that is,
for each intersecting pair $f,f^{\prime}\in F$ there will be a point $q\in Q$
that lies in $f\cap f^{\prime}$. The goal is to keep the size of $Q$ small, by
capturing all intersecting pairs with few points. The hyperedges are defined
by the regions in $F$, that is, for every $f\in F$ there is a hyperedge
$h_{f}:=Q\cap f$. Let $\mathcal{H}_{Q}(F)$ denote the resulting hypergraph.

######  Lemma 3.1.

Let $F$ be a set of $n$ objects in the plane, let $Q$ be a set of points
stabbing all pairwise intersections in $F$, and let $\mathcal{H}_{Q}(F)$
denote the hypergraph as defined above. If $\mathcal{H}_{Q}(F)$ has a planar
support $\mathcal{G}_{\mathrm{sup}}$ then $\mathcal{G}^{\times}(F)$ has a
clique-based separator of size $O(\sqrt{|Q|})$ and weight $O(\sqrt{|Q|}\log
n)$.

######  Proof 3.2.

Let $\mathcal{\mathcal{S}}(\mathcal{G}_{\mathrm{sup}})$ be a separator for
$\mathcal{G}_{\mathrm{sup}}$ of size $O(\sqrt{|Q|})$, which exists by the
Planar Separator Theorem, and let $A(\mathcal{G}_{\mathrm{sup}})$ and
$B(\mathcal{G}_{\mathrm{sup}})$ be the corresponding separated parts. To
ensure an appropriately balanced separator we use the cost-balanced version of
the Planar Separator Theorem, as stated in the previous section. For each
object $f\in F$ we give one point $q_{f}\in Q\cap f$ a cost of $1/n$ and all
other points cost 0. We call $q_{f}$ the _representative_ of $f$. (We assume
for simplicity that each $f\in F$ intersects at least one other object
$f^{\prime}\in F$, so we can always find a representative. Objects $f\in F$
not intersecting any other object are singletons in $\mathcal{G}^{\times}(F)$
and can be ignored.) For a point $q\in Q$, define $C_{q}$ to be the clique in
$\mathcal{G}^{\times}(F)$ consisting of all objects $f\in F$ that contain $q$.
Our clique-based separator $\mathcal{\mathcal{S}}$ for
$\mathcal{G}^{\times}(F)$ is now defined as
$\mathcal{\mathcal{S}}:=\\{C_{q}:q\in\mathcal{\mathcal{S}}(\mathcal{G}_{\mathrm{sup}})\\}$,
and the two separated parts are defined as: $A:=\\{f\in
F:f\not\in\mathcal{\mathcal{S}}\mbox{ and }q_{f}\in
A(\mathcal{G}_{\mathrm{sup}})\\}$ and $B:=\\{f\in
F:f\not\in\mathcal{\mathcal{S}}\mbox{ and }q_{f}\in
B(\mathcal{G}_{\mathrm{sup}})\\}$. Clearly, the size of
$\mathcal{\mathcal{S}}$ is $O(\sqrt{|Q|})$ and its weight is $O(\sqrt{|Q|}\log
n)$. Moreover, $|A|,|B|\leqslant 2n/3$ because
$\mathcal{\mathcal{S}}(\mathcal{G}^{*})$ is balanced with respect to the node
costs.

We claim there are no arcs in $\mathcal{G}^{\times}(F)$ between a node in $A$
and a node in $B$. Suppose for a contradiction that there are intersecting
objects $f,f^{\prime}$ such that $f\in A$ and $f^{\prime}\in B$. By definition
of $Q$ there is a point $q\in Q$ that lies in $f\cap f^{\prime}$. By the
planar-support property, the hyperedge $h_{f}$ induces a connected subgraph of
$\mathcal{G}_{\mathrm{sup}}$, so there is a path $\pi$ that connects $q$ to
the representative $q_{f}$ and such that all nodes of $\pi$ are points in
$f\cap Q$. No node on the path $\pi$ can be in
$\mathcal{\mathcal{S}}(\mathcal{G}_{\mathrm{sup}})$, otherwise $f$ is in a
clique that was added to $\mathcal{\mathcal{S}}$. Similarly, there is a path
$\pi^{\prime}$ connecting $q_{f^{\prime}}$ to $q$ such that no point on
$\pi^{\prime}$ is in $\mathcal{\mathcal{S}}(\mathcal{G}_{\mathrm{sup}})$. But
then there is a path from $q_{f}$ to $q_{f^{\prime}}$ in
$\mathcal{G}_{\mathrm{sup}}$ after the removal of
$\mathcal{\mathcal{S}}(\mathcal{G}_{\mathrm{sup}})$. Hence, $q_{f}$ and
$q_{f^{\prime}}$ are in the same part of the partition, which contradicts that
$f$ and $f^{\prime}$ are in different parts.

We conclude that $\mathcal{\mathcal{S}}$ is a clique-based separator with the
desired properties.

######  Remark 3.3.

The witness set $Q$ in the previous section stabs all pairwise intersections
of objects in the map graph, and so $P\cup Q$ stabs all pairwise intersections
as well. $P\cap Q$ has planar support, so we can get a separator for map
graphs using Lemma 3.1. Its weight would be $O(\sqrt{n}\log n)$, however,
while in the previous section we managed to get $O(\sqrt{n})$ weight.

Polygonal pseudo-disks. We now apply Lemma 3.1 to obtain a clique-based
separator for a set $F$ of polygonal pseudo-disks. To this end, let $Q$ be the
set of vertices of the pseudo-disks in $F$. Observe that whenever two pseudo-
disks intersect, one must have a vertex inside the other. Indeed, either one
pseudo-disk is entirely inside the other, or an edge $e$ of $f$ intersects an
edge $e^{\prime}$ of $f^{\prime}$. In the latter case, one of the two edges
ends inside the other pseudo-disk, otherwise there are three intersections
between the boundaries. Furthermore, pseudo-disks have the _non-piercing_
property: $f\setminus f^{\prime}$ is connected for any two pseudo-disks
$f,f^{\prime}$. Raman and Ray [29] proved666Raman and Ray assume the sets $F$
and $Q$ defining the hypergraph are in general position. Therefore we first
slightly perturb the pseudo-disks in $F$ to get them into general position
(while keeping the same intersection graph), then we take $Q$ to be a point
set coinciding with the vertex set of $F$, and then we slightly move the
points in $Q$ such that the hypergraph remains the same. that the hypergraph
$\mathcal{H}_{Q}(F)$ of a set of non-piercing regions has a planar support for
any set $Q$, so in particular for the set $Q$ just defined. We can thus apply
Lemma 3.1 to compute a clique-based separator for $\mathcal{G}^{\times}(F)$.
The time to compute the separator is dominated by the computation of the
planar support, which takes $O(n^{3})$ time [29].

######  Theorem 3.4.

Let $F$ be a set of $n$ polygonal pseudo-disks in the plane with $O(n)$
vertices in total. Then the intersection graph $\mathcal{G}^{\times}(F)$ has a
clique-based balanced separator of size $O(\sqrt{n})$ and weight
$O(\sqrt{n}\log n)$, which can be found in $O(n^{3})$ time.

Arbitrary pseudo-disks. To construct a clique-based separator using Lemma 3.1
we need a small point set $Q$ that stabs all pairwise intersections.
Unfortunately, for general pseudo-disks a linear-size set $Q$ that stabs all
intersections need not exist: there is a collection of $n$ disks such that
stabbing all pairwise intersections requires $\Omega(n^{4/3})$ points. (Such a
collection can be derived from a construction with $n$ lines and $n$ points
with $\Omega(n^{4/3})$ incidences [26].) Hence, we need some more work before
we can apply Lemma 3.1.

Our separator result for arbitrary pseudo-disks works in a more general
setting, namely for sets from a family $\mathcal{F}$ with linear union
complexity. (We say that $\mathcal{F}$ has union complexity $U(n)$ if, for any
$n\geqslant 1$ and any subset $F\subset\mathcal{F}$ of size $n$, the union
complexity of $F$ is $U(n)$.) Recall that the union complexity of a family of
pseudo-disks is $O(n)$ [17]. The next theorem states that such sets admit a
clique-based separator of sublinear weight. Note that the bound only depends
on the number of objects, not on their complexity.

######  Theorem 3.5.

Let $F$ be a set of $n$ objects from a family $\mathcal{F}$ of union
complexity $U(n)$, where $U(n)\geqslant n$. Then $\mathcal{G}^{\times}(F)$ has
a clique-based separator of size $O((U(n))^{2/3})$ and weight
$O((U(n))^{2/3}\log n)$. In particular, if $F$ is a set of pseudo-disks then
$\mathcal{G}^{\times}(F)$ has a clique-based separator of size $O(n^{2/3})$
and weight $O(n^{2/3}\log n)$. The separator can be computed in $O(n^{3})$
time, assuming the total complexity of the objects is $O(n)$.

######  Proof 3.6.

We construct the separator $\mathcal{\mathcal{S}}$ in two steps.

The first step proceeds as follows. For a point $p$ in the plane, let $C_{p}$
denote the set of objects from the (current) set $F$ containing $p$. As long
as there is a point $p$ such that $|C_{p}|>n^{1/3}$, we remove $C_{p}$ from
$F$ and put $C_{p}$ into $\mathcal{\mathcal{S}}$; here $n$ refers to the size
of the initial set $F$. Thus the first step adds $O(n^{2/3})$ cliques to
$\mathcal{\mathcal{S}}$ with total weight $O(n^{2/3}\log n)$. This step can
easily be implemented in $O(n^{3})$ time.

In the second step we have a set $F^{*}\subseteq F$ of $n^{*}$ objects with
ply $k$, where $n^{*}\leqslant n$ and $k\leqslant n^{1/3}$. Let
$\mathcal{A}(F^{*})$ denote the arrangement induced by $F^{*}$. Since $F^{*}$
has ply $k$, the Clarkson-Shor technique [9] implies that the complexity of
the arrangement $\mathcal{A}(F^{*})$ is $O(k^{2}\cdot U(n^{*}/k))$. We can
compute this arrangement in $O(k^{2}\cdot U(n^{*}/k)\log n)=O(n^{2}\log n)$
time [12]. Take a point $q$ in each face of the arrangement, and let $Q$ be
the resulting set of $O(k^{2}\cdot U(n^{*}/k))$ points. The set $Q$ stabs all
pairwise intersections and the dual graph $\mathcal{G}^{*}$ of the arrangement
$\mathcal{A}(F^{*})$ is a planar support for the hypergraph
$\mathcal{H}_{Q}(F)$. Hence, by Lemma 3.1 there is a clique-based separator
$\mathcal{\mathcal{S}}^{*}$ for $\mathcal{G}^{\times}(F)$ of size
$O\left(k\sqrt{U\left(n^{*}/k\right)}\right)$ and weight
$O\left(k\sqrt{U\left(n^{*}/k\right)}\log{n^{*}}\right)$. Note that $U(n)$ is
a superadditive function [1] which implies that $U(n/k)\leqslant U(n)/k$ and
therefore $k\sqrt{U\left(n^{*}/k\right)}\leqslant\sqrt{k\leavevmode\nobreak\
U(n)}\leqslant(U(n))^{2/3}$. By adding $\mathcal{\mathcal{S}}^{*}$ to the set
$\mathcal{\mathcal{S}}$ of cliques generated in the first step, we obtain a
clique-based separator with the desired properties.

##  4 Geodesic disks inside a simple polygon

Let $P$ be a simple polygon. We denote the shortest path (or: _geodesic_) in
$P$ between two points $p,q\in P$ by $\pi(p,q)$; note that $\pi(p,q)$ is
unique since $P$ is simple. The _geodesic distance_ between $p$ and $q$ is
defined to be $\|\pi(p,q)\|$, where $\|\pi\|$ denotes the Euclidean length of
a path $\pi$. For a given point $q\in P$ and radius $r>0$, we call the region
$D(q,r):=\\{p\in P:\|\pi(p,q)\|\leqslant r\\}$ a _geodesic disk_. Let
$\mathcal{D}=\\{D_{1},\ldots,D_{n}\\}$ be a set of geodesic disks in $P$. To
construct a clique-based separator for $\mathcal{G}^{\times}(\mathcal{D})$ we
will show that $\mathcal{D}$ behaves as a set of pseudo-disks so we can apply
the result of the previous section.

The structure of a geodesic disk. The boundary $\partial D(q,r)$ of a geodesic
disk $D(q,r)$ consists of circular arcs lying in the interior of $P$ (centered
at $q$ or at a reflex vertex of $P$) and parts of the edges of $P$. We split
$\partial D(q,r)$ into _boundary pieces_ at the points where the circular arcs
meet $\partial P$. This generates two sets of boundary pieces: a set
containing the pieces that consist of circular arcs, and a set $\Gamma(D)$
containing the pieces that consist of parts of edges of $P$. An example can be
seen in Fig. 3.

Figure 3: (i) A geodesic disk $D$ with center $q$ and radius $r$. The set
$\Gamma(D)$ has three pieces, $\gamma_{1},\gamma_{2}$ and $\gamma_{3}$, shown
in blue. (ii) The result of the perturbation. Note that
$|\gamma_{1}|<|\gamma_{2}|<|\gamma_{3}|$ and so
$\varepsilon_{\gamma_{1}}>\varepsilon_{\gamma_{2}}>\varepsilon_{\gamma_{3}}$.
(iii) Illustration for the proof of Theorem 4.3.

A region $R\subseteq P$ is _geodesically convex_ if for any points $p,q\in R$
we have $\pi(p,q)\subseteq R$. Pollack et al. [28] showed that geodesic disks
inside a simple polygon are geodesically convex. An immediate consequence is
that the intersection of two geodesic disks is connected.

Geodesic disks behave as pseudo-disks. Geodesic disks in a simple polygon are
not proper pseudo-disks. For example, if $D_{1}$ and $D_{2}$ are the blue and
pink pseudo-disk in the third image in Fig. 1, then $D_{1}\setminus D_{2}$ has
two components, which is not allowed for pseudo-disks. Nevertheless, we will
show that $\mathcal{D}$ behaves as a set of pseudo-disks in the sense that a
small perturbation turns them into pseudo-disks, while keeping the
intersection graph the same.

As a first step in the perturbation, we increase the radius of each geodesic
disk $D_{i}\in\mathcal{D}$ by some small $\varepsilon_{i}$. We pick these
$\varepsilon_{i}$ such that the intersection graph
$\mathcal{G}^{\times}(\mathcal{D})$ stays the same while all degeneracies
disappear. In particular, the boundary pieces of different geodesic disks have
different lengths after this perturbation, and no two geodesic disks touch.
With a slight abuse of notation, we still denote the resulting set of geodesic
disks by $\mathcal{D}$.

The second step in the perturbation moves each
$\gamma\in\cup_{i=1}^{n}\Gamma(D_{i})$ into the interior of the polygon over
some distance $\varepsilon_{\gamma}$, which is smaller than any of the
perturbation distances chosen in the first step. More formally, for each
$\gamma\in\Gamma(D_{i})$ we remove all points from $D_{i}$ that are at
distance less than $\varepsilon_{\gamma}$ from $\gamma$; see Fig. 3(ii). To
ensure this gives a set of pseudo-disks we choose the perturbation distances
$\varepsilon_{\gamma}$ according to the reverse order of the Euclidean lengths
of the pieces. That is, if $\|\gamma\|>\|\gamma^{\prime}\|$ then we pick
$\varepsilon_{\gamma}<\varepsilon_{\gamma^{\prime}}$. The crucial property of
this scheme is that whenever $\gamma_{i}\subset\gamma_{j}$ then $\gamma_{i}$
is moved more than $\gamma_{j}$.

We denote the perturbed version of $D_{i}$ by $D_{i}^{*}$ and define
$\mathcal{D}^{*}:=\\{D^{*}_{i}:D_{i}\in\mathcal{D}\\}$. The perturbed versions
have the following important property:

######  Lemma 4.1.

Let $D^{*}_{i},D^{*}_{j}\in\mathcal{D}^{*}$. Every connected component of
$D_{i}^{*}\setminus D_{j}^{*}$ contains a point $u$ with $u\in D_{i}\setminus
D_{j}$.

######  Proof 4.2.

The only case of interest is when there exist $\gamma_{i}\in\Gamma(D_{i})$ and
$\gamma_{j}\in\Gamma(D_{j})$ such that
$\gamma_{i}\cap\gamma_{j}\neq\emptyset$. Suppose now there is a connected
component of $D_{i}^{*}\setminus D_{j}^{*}$ which does not contain such a
point. Since $D_{i}^{*}\subset D_{i}$ and $D_{j}^{*}\subset D_{j}$, this
connected component must have been introduced due to the perturbation (in
other words its intersection with all connected components of $D_{i}\setminus
D_{j}$ must be empty). This means that this connected component must be the
region contained between $\gamma_{i}^{*}$ and $\gamma_{j}^{*}$ and which was
previously contained in $D_{i}\cap D_{j}$. It is enough to only examine the
case when $\gamma_{i}$ is bigger than $\gamma_{j}$ as otherwise this component
only contains points of $D_{j}^{*}$. There are two cases:
$\gamma_{j}\subset\gamma_{i}$, or $\gamma_{j}\not\subset\gamma_{i}$. In both
cases note that there will exist an endpoint $p$ of $\gamma_{j}^{*}$ that lies
inside $D_{i}^{*}$. Choose now a point $q$ in $(D_{j}\setminus
D_{j}^{*})\setminus(D_{i}\setminus D_{i}^{*})$ at distance $\varepsilon$ from
$\gamma_{j}$ with
$\varepsilon_{\gamma_{i}}<\varepsilon<\varepsilon_{\gamma_{j}}$. See Fig. 4
for an illustration of the case $\gamma_{j}\subset\gamma_{i}$. Consider the
dashed path starting at $q$ that stays at distance $\varepsilon$ from
$\partial P$ going towards $p$. Due to the definition of our perturbation this
path will stay inside $D^{*}_{i}$ and remain outside $D_{j}^{*}$. Hence, after
exiting $D^{*}_{j}$ near the point $p$ we reach a point $u\in D_{i}\setminus
D_{j}$, which is a contradiction.

Figure 4: Illustration for proof of Lemma 4.1.

######  Theorem 4.3.

Any set $\mathcal{D}$ of geodesic disks inside a simple polygon $P$ can be
slightly perturbed such that the resulting set $\mathcal{D}^{*}$ is a set of
pseudo-disks with
$\mathcal{G}^{\times}(\mathcal{D})=\mathcal{G}^{\times}(\mathcal{D}^{*})$.

######  Proof 4.4.

Consider the set $\mathcal{D}^{*}$ resulting from the perturbation described
above. Suppose for a contradiction that there exist two objects
$D_{1}^{*},D_{2}^{*}\in\mathcal{D}^{*}$ such that $\partial D^{*}_{1}$ and
$\partial D^{*}_{2}$ cross four or more times. Recall that the intersection of
two geodesic disks is connected. This property is not invalidated by the
perturbation. Hence, if $\partial D^{*}_{1}$ and $\partial D^{*}_{2}$ cross
four or more times then $D^{*}_{1}\setminus D^{*}_{2}$ (and, similarly,
$D^{*}_{2}\setminus D^{*}_{1}$) has two or more components.

For $i=1,2$, let $q_{i}$ and $r_{i}$ denote the center and radius of $D_{i}$.
Without loss of generality assume that $r_{1}\leqslant r_{2}$. Let $x$ and $y$
be points in different components of $D^{*}_{1}\setminus D^{*}_{2}$; see Fig.
3 (iii). By Lemma 4.1 we can pick $x$ and $y$ such that $x,y\in D_{1}\setminus
D_{2}$. By concatenating the geodesics $\pi(x,q_{1})$ and $\pi(q_{1},y)$ we
obtain a curve that splits $D_{2}^{*}$ into at least two parts—this is
independent of where $q_{1}$ lies, or whether $\pi(x,q_{1})$ and
$\pi(q_{1},y)$ partially overlap. (Note that these geodesics lie in $D_{1}$
but not necessarily in $D^{*}_{1}$. However, they cannot “go around” a
component of $D_{2}^{*}\setminus D^{*}_{1}$, because $D_{1}$ cannot fully
contain such a component by Lemma 4.1. Hence, $\pi(x,q_{1})\cup\pi(q_{1},y)$
must indeed go through $D^{*}_{2}$.) Not all components of $D^{*}_{2}\setminus
D^{*}_{1}$ can belong to the same part, otherwise $x$ and $y$ would not be in
different components of $D^{*}_{1}\setminus D^{*}_{2}$. Take a point $z\in
D^{*}_{2}\setminus D^{*}_{1}$ that lies in a different part than $q_{2}$, the
center of $D_{2}$. Again by Lemma 4.1 we can pick $z$ such that $z\in
D_{2}\setminus D_{1}$. Then the geodesic $\pi(q_{2},z)$ must cross
$\pi(x,q_{1})\cup\pi(q_{1},y)$, say at a point $w\in\pi(q_{1},y)$. Since
$z\not\in D_{1}$ and $y\not\in D_{2}$ we must have
$\|\pi(q_{1},w)\cup\pi(w,z)\|+\|\pi(q_{2},w)\cup\pi(w,y)\|>r_{1}+r_{2}$. But
this gives a contradiction because $y\in D_{1}$ and $z\in D_{2}$ implies
$\|\pi(q_{1},w)\cup\pi(w,y)\|+\|\pi(q_{2},w)\cup\pi(w,z)\|\leqslant
r_{1}+r_{2}$.

It remains to show that
$\mathcal{G}^{\times}(\mathcal{D})=\mathcal{G}^{\times}(\mathcal{D}^{*})$. As
mentioned earlier, the increase of the radii in the first step of the
perturbation is chosen sufficiently small so that no new intersections are
introduced. The second step shrinks the geodesic disks, so no new
intersections are introduced in that step either. Finally, the fact that the
perturbations in the second step are smaller than in the first step guarantees
that no intersections are removed.

Theorem 4.3 allows us to apply Theorem 3.5. When doing so, we actually do not
need to perturb the geodesic disks. We only use the perturbation to argue that
the number of faces in the arrangement defined by $n$ geodesic disks of ply
$k$ is $O(nk)$. Computing the geodesic disks (and then computing the
separator) can be done in polynomial time in $n$ and the number of vertices of
$P$. We obtain the following result.

######  Corollary 4.5.

Let $\mathcal{D}$ be a set of $n$ geodesic disks inside a simple polygon with
$m$ vertices. Then $\mathcal{G}^{\times}(\mathcal{D})$ has a clique-based
separator of size $O(n^{2/3})$ and weight $O(n^{2/3}\log n)$, which can be
computed in time polynomial in $n$ and $m$.

##  5 Visibility-restricted unit-disk graphs inside a polygon

Let $P$ be a simple polygon, possibly with holes, and let $Q$ be a set of $n$
points inside $P$. We define $\mathcal{G}^{\times}_{\mathrm{vis},P}(Q)$ to be
the visibility-restricted unit-disk graph of $Q$. The nodes in
$\mathcal{G}^{\times}_{\mathrm{vis},P}(Q)$ correspond to the points in $Q$ and
there is an edge between two points $p,q\in Q$ iff $|pq|\leqslant 1$ and $p$
and $q$ see each other. A vertex of $P$ is _reflex_ if its angle within the
polygon is more than 180 degrees; note that for a vertex of a hole we look at
the angle within $P$, not within the hole. Our separator construction will
make use of the notion of a _centerpoint of $P$_ which we introduce below.

###  5.1 Centerpoint of a simple polygon

This is a natural extension of the notion of the centerpoint for a set $Q$ of
$n$ points in the plane, which is a point $p$ (not necessarily from $Q$) such
that any line through $p$ divides the plane in two half-planes each containing
at most $2n/3$ of the points from $Q$. Recall that a _chord_ in $P$ is a line
segment $s\subset P$ that connects two points on the boundary of $P$. Since we
consider $P$ to be a closed set, a chord may pass through one or more reflex
vertices of $P$. We say that a chord is _maximal_ if it cannot be extended
without exiting the polygon. We define a _half-polygon_ of $P$ to be a sub-
polygon of $P$ that is bounded by a (not necessarily maximal) chord $s$ and a
portion $\gamma\subset\partial P$ of the boundary of $P$ such that
$s\cap\gamma=\\{z_{1},z_{2}\\}$, where $z_{1},z_{2}$ are the endpoints of $s$.
Note that any chord splits $P$ into two or more half-polygons.

######  Definition 5.1 (Centerpoint in a Simple Polygon).

Let $P$ be a simple polygon and $Q$ be a set of $n$ points in $P$. A
_centerpoint for $Q$ in $P$_ is a point $p\in P$ such that any maximal chord
through $p$ splits $P$ into half-polygons that each contain at most $2n/3$
points from $Q$ in their interior.

######  Theorem 5.2.

For any simple polygon $P$ and point set $Q\subset P$, a centerpoint for $Q$
in $P$ exists.

######  Proof 5.3.

To prove the theorem we can follow the standard proof [23] of the existence of
a centerpoint in the plane almost verbatim. Thus, consider the family $H$ of
all half-polygons of $P$ whose interior contains more than $2n/3$ points of
$Q$. Any three of these half-polygons must intersect, because the complement
of each of them contains less than $n/3$ points from $Q$. Recall that Helly’s
Theorem states that if we have a family of convex sets in the plane such that
any three of them intersect, then they all intersect in a common point. While
our half-polygons are not convex, the same result is true here, as follows
from Molnar’s Theorem [5] which states that if a family of simply connected
compact sets in the plane is such that any two members have a connected
intersection and any three members have a non-empty intersection, then the
intersection of the family is non-empty. Our family $H$ satisfies these
conditions and hence $\bigcap H\neq\emptyset$.

We claim that any point $c$ in the common intersection of the half-polygons in
$H$ is a centerpoint for $Q$ in $P$. To see this take a chord $s$ through $c$
and let $H_{1},H_{2},\ldots$ be the half-polygons into which $s$ splits $P$.
Suppose for contradiction that some $H_{i}$ contains more than $2n/3$ points
of $Q$. Let $s_{i}\subseteq s$ be the part of $s$ bounding $H_{i}$. Then, if
we slightly shrink $H_{i}$ by moving $s_{i}$ infinitesimally, we obtain a
half-polygon $H^{\prime}_{i}$ that contains more than $2n/3$ vertices,
contradicting the definition of $c$.

Our main result is the following:

######  Theorem 5.4.

Let $Q$ be a set of $n$ points inside a polygon (possibly with holes) with $r$
reflex vertices. Then $\mathcal{G}^{\times}_{\mathrm{vis},P}(Q)$ admits a
clique-based separator of size $O(\min(n,r)+\sqrt{n})$ and weight
$O(\min(n,r\log(n/r)+\sqrt{n}))$. The bounds on the size and weight of the
separator are tight in the worst case, even for simple polygons.

The lower bound. Recall that even for non-visibility restricted unit-disk
graphs, $\Omega(\sqrt{n})$ is a lower bound on the worst-case size of the
separator. Hence, to prove the lower bound of Theorem 5.4 it suffices to give
an example where the size and weight are $\Omega(\min(n,r))$ and
$\Omega(\min(n,r\log(n/r)))$, respectively. This example is given in Fig.
5(i).

Figure 5: (i) Each cluster $A_{i}$ sees any of the clusters $B_{j}$ completely
and all distances are at most 1, so a separator that splits
$\mathcal{G}^{\times}_{\mathrm{vis},P}\left(\bigcup A_{i}\cup\bigcup
B_{j}\right)$ into two or more components must fully contain $\bigcup A_{i}$
or $\bigcup B_{j}$. Since the clusters $A_{i}$ (and similarly $B_{j}$) do not
see each other, such a separator has size at least $r/2$ and weight at least
$((r/2)\log(n/r))$. (ii) Splitting $R^{*}(u)$ into two convex parts.

The upper bound. We first describe our construction for polygons without
holes. Our separator construction has two steps. In the first step we put all
points that can see a reflex vertex within distance $\sqrt{2}$ into the
separator. We will argue that we can do this in such a way that we put $O(1)$
cliques per reflex vertex into the separator. In the second step we handle the
remaining points. We take a centerpoint $c$ inside $P$ and then define
$\sqrt{n}$ chords through $c$. For each chord $s_{i}$ we put the points within
distance 1/2 into the separator, suitably grouped into cliques. We will argue
that the total weight of the cliques, over all chords $s_{i}$ is $O(n)$.
Hence, there is a chord whose cliques have total weight $O(\sqrt{n})$. Adding
the weight of the cliques we added in Step 1 then gives us the desired
separator.

#### Step 1: Handling points that see a nearby reflex vertex

Let $V_{\mathrm{ref}}$ be the set of reflex vertices of $P$, and let
$Q_{1}\subseteq Q$ be the set of points that can see a reflex vertex within
distance $\sqrt{2}$. Consider the geodesic Voronoi diagram of
$V_{\mathrm{ref}}$ within $P$. Let $R(u)$ be the Voronoi region of vertex
$u\in V_{\mathrm{ref}}$ and define $R^{*}(u):=R(u)\cap D(u,\sqrt{2})$. Note
that all points in $R(u)$ can see $u$ and that all points in $Q_{1}$ are in
$R*(u)$ for some vertex $u\in V_{\mathrm{ref}}$. The following lemma is
illustrated in Fig. 5(ii).

######  Lemma 5.5.

Let $e$ be an edge incident to $u$. If we extend $e$ until it hits $\partial
R^{*}(u)$ then $R^{*}(u)$ is split into two convex parts.

######  Proof 5.6.

It suffices to argue that the angle of $R(u)$ corresponding to $u$ is the only
reflex angle within $R(u)$. Then the result will follow from the fact that
$D(u,\sqrt{2})$ is convex. Clearly the shortest path connecting any point
$p\in R(u)$ to $u$ is the segment $pu$. This implies that $\partial R(u)$
consists of straight line segments that are parts of perpendicular bisectors
of the segments connecting $u$ to other reflex vertices of $P$. Any two such
consecutive edges then cannot form a reflex angle within $R(u)$.

Since $R^{*}(u)$ has diameter $O(1)$, Lemma 5.5 implies that $Q_{1}\cap
R^{*}(u)$ can be partitioned into $O(1)$ cliques. We collect all these cliques
into a set $\mathcal{\mathcal{S}}_{1}$. Since there are $r$ reflex vertices,
$\mathcal{\mathcal{S}}_{1}$ consists of $O(r)$ cliques whose total weight is
$O(r\log(n/r))$.

#### Step 2: Handling points that do not see a nearby reflex vertex

Our separator $\mathcal{\mathcal{S}}$ consists of the cliques in
$\mathcal{\mathcal{S}}_{1}$ plus a set $\mathcal{\mathcal{S}}_{2}$ of cliques
that are found as follows. Let $Q_{2}:=Q\setminus Q_{1}$ be the set of points
that do not see a reflex vertex within distance $\sqrt{2}$. Let $c$ be a
_centerpoint for $Q_{2}$ inside $P$_, that is, a point such that any chord
through $c$ splits $P$ into two half-polygons containing at most $2|Q_{2}|/3$
points from $Q$. Such a point exists by Theorem 5.2. Let $G$ be a
$\sqrt{n}\times\sqrt{n}$ grid centered at $c$, where we assume for simplicity
that $\sqrt{n}$ is integer. For each of the $\sqrt{n}$ points $g_{i}$ in the
rightmost column of the grid (even if $g_{i}\not\in P$), we define a maximal
chord $s_{i}$ by taking the line $\ell_{i}$ through $c$ and $g_{i}$ and then
taking the component of $\ell_{i}\cap P$ that contains $c$; see Fig. 6(i). We
assume for simplicity that the chords $s_{i}$ doe not pass through reflex
vertices; this can be ensured by slightly rotating the grid, if necessary.

For each chord $s_{i}$, we define $Q_{2}(s_{i})$ be the set of points $q\in
Q_{2}$ such that there is a point $z\in s_{i}$ that sees $q$ with
$|qz|\leqslant 1/2$.

Figure 6: (i) The grid $G$ defining the chords $s_{i}$. (ii) The points in the
top-left cell do not see each other, but they see a reflex vertex and so they
are not in $Q_{2}(s_{i})$. The points in the top-right cell can be partitioned
into $O(1)$ cliques.

Note that $\mathcal{G}^{\times}_{\mathrm{vis},P}(Q)$ cannot have an arc
between a point $p\in Q_{2}\setminus Q_{2}(s_{i})$ above $s_{i}$ and a point
$q\in Q_{2}\setminus Q_{2}(s_{i})$ below $s_{i}$; otherwise $p$ and/or $q$ see
a point on $z$ within distance 1/2, and so at least one of $p,q$ is in
$Q_{2}(s_{i})$. Since $s_{i}$ is a chord through the centerpoint $c$, this
means that $s_{i}$ induces a balanced separator.

It remains to argue that at least one of the chords $s_{i}$ induces a
separator whose weight is small enough. We will do this by creating a set
$\mathcal{\mathcal{S}}(s_{i})$ of cliques for each chord $s_{i}$, and prove
that the total weight of these cliques, over all chords $s_{i}$, is $O(n)$.
Since there are $\sqrt{n}$ chords, one of them has the desired weight.

Step 2.1: Points outside the grid. We simply put all points from
$Q_{2}(s_{i})$ that lie outside the grid $G$—that is, the points that do not
lie inside a grid cell—into $\mathcal{\mathcal{S}}(s_{i})$, as singletons. Let
$q$ be a point that does not lie in any of the cells of the grid $G$. Then $q$
lies within distance $1/2$ of at most two chords $s_{i}$. Observation 5.1
implies that the total number of singleton cliques of points outside grid
cells, summed over all chords $\mathcal{\mathcal{S}}(s_{i})$, is $O(n)$.

Step 2.2: Points inside the grid. Next, consider a cell $T$ of the grid $G$.
Suppose a point $q\in Q_{2}(s_{i})$ sees a point $z\in T\cap s_{i}$ such that
$|qz|\leqslant 1/2$. Then $q$ must lie inside one of the at most nine grid
cells surrounding and including $T$. Consider such a cell $T^{\prime}$.

######  Lemma 5.7.

The points from $Q_{2}(s_{i})\cap T^{\prime}$ that can see a point on
$s_{i}\cap T$ within distance $1/2$ can be partitioned into $O(1)$ cliques.

######  Proof 5.8.

We will show that we can split these points into at most four cliques. To this
end we split $T^{\prime}$ in four equal-sized subcells; see Fig. 7. Clearly
each subcell has a diameter $\frac{1}{2}\sqrt{2}<1$. It suffices now to show
that if two points $p,q$ in the same subcell do not see each other, then they
see a reflex vertex within distance $\sqrt{2}$; hence they are in $Q_{1}$ and
not in $Q_{2}(s_{i})\cap T^{\prime}$.

Figure 7: Illustration for the proof of Lemma 5.7.

Let $z_{1}$ and $z_{2}$ be points on $s_{i}\cap T$ that see $p,q$,
respectively, with $|pz_{1}|\leqslant 1/2$ and $|qz_{2}|\leqslant 1/2$. The
quadrilateral formed by the points $p,q,z_{1},z_{2}$ must always lie within a
square of side length 1. This square is shown in green in Fig. 7, for three
different cases depending on the relative position of $T^{\prime}$ and $T$. In
this quadrilateral, the side $pq$ has to be crossed by the $\partial P$, since
we assumed $p$ and $q$ do not see each other. Moreover, $\partial P$ cannot
cross $s_{i}$ or the segments $pz_{1},qz_{2}$. Thus at least one reflex vertex
of $\partial P$ lies within the quadrilateral. It’s then clear that both $p,q$
will be able to see a reflex vertex within the quadrilateral (possibly not the
same); since all points lie within a square of side length 1, the result
follows. Note that in Fig. 7 (iii) we have made the edges $pz_{1},qz_{2}$
cross each other to showcase that the proof still goes through in this case.

We thus create $O(1)$ cliques for each cell $T^{\prime}$ that is one of the at
most nine cells surrounding a cell $T$ crossed by $s_{i}$, and put them into
$\mathcal{\mathcal{S}}(s_{i})$. This adds at most $O(\log(n_{T^{\prime}}+1))$
weight to $\mathcal{\mathcal{S}}(s_{i})$, where $n_{T^{\prime}}:=|Q_{2}\cap
T^{\prime}|$. Since there are $n$ cells in total, this immediately gives a
total weight of $O(n\log n)$ over all sets $\mathcal{\mathcal{S}}(s_{i})$.
Next we show that the the total weight of the cliques is actually $O(n)$. In
what follows we denote by $\mathrm{weight}(\mathcal{\mathcal{S}}(s_{i}))$ the
total weight of the cliques corresponding to chord $s_{i}$.

######  Lemma 5.9.

The total weight of the cliques corresponding to the chords $s_{i}$ is $O(n)$,
that is:

$\sum_{i=1}^{\sqrt{n}}\mathrm{weight}(\mathcal{\mathcal{S}}(s_{i}))=O(n).$

######  Proof 5.10.

Let $\mathcal{T}(s_{i})$ denote the cells crossed by a chord $s_{i}$, and let
$N[T]$ denote the at most nine cells surrounding a cell $T$, including $T$
itself. By the arguments above, the total weight of all separators is.

$\sum_{i=1}^{\sqrt{n}}\sum_{T\in\mathcal{T}(s_{i})}\sum_{T^{\prime}\in
N[T]}O(\log(n_{T^{\prime}}+1))$ (1)

Let $K_{1}$ be the set of cells in the central column of the grid, that is,
the column containing the centerpoint $c$. For $2\leqslant j\leqslant m$,
where $m:=\lceil\sqrt{n}/2\rceil,$ let $K_{j}$ be the cells in the pair of
columns at distance $j-1$ from $K_{1}$. For example, $K_{2}$ are the cells in
the columns immediately to the left and right of $K_{1}$. Then we can make the
following observations.

  * •

The set $K_{j}$ contains $4j-2=O(j)$ cells that are crossed by at least one
chord $s_{j}$.

  * •

Cells in $K_{j}$ are crossed by $O(\sqrt{n}/j)$ chords.

Now define $K^{*}_{j}$ to be the set of cells $T^{\prime}$ in $K_{j}$ such
that one of the nine cells surrounding $T^{\prime}$ is crossed by at least one
chord. Note that each $T^{\prime}\in K^{*}_{j}$ is in $N[T]$ for at most nine
cells $T$, which are all in $K_{j-1}\cup K_{j}\cup K_{j+1}$. (Here we define
$K_{-1}=K_{m+1}=\emptyset$.) It then follows from the above observations that
$|K_{j}^{*}|=O(j)$. Moreover, if $T^{\prime}\in K^{*}_{j}$ and $T^{\prime}\in
N[T]$, then $T$ is crossed by $O(\sqrt{n}/j)$ chords. Hence, we can rewrite
(1) as

$\sum_{j=1}^{m}\left(O\left(\frac{\sqrt{n}}{j}\right)\cdot\sum_{T^{\prime}\in
K^{*}_{j}}O(\log(n_{T^{\prime}}+1))\right)=O\left(\sum_{j=1}^{m}\frac{\sqrt{n}}{j}\cdot\sum_{T^{\prime}\in
K^{*}_{j}}\log(n_{T^{\prime}}+1)\right)$ (2)

Now we are ready to compute the total weight of the separator. Note that

$\sum_{T^{\prime}\in
K^{*}_{j}}\log(n_{T^{\prime}}+1)=\log\left(\prod_{T^{\prime}\in
K^{*}_{j}}(n_{T^{\prime}}+1))\right)$

Now define $n_{j}$ to be the total number of points in the cells in
$K^{*}_{j}$. The AM-GM inequality gives us:

$\log\left({\prod_{T^{\prime}\in
K^{*}_{j}}(n_{T^{\prime}}+1)}\right)\leqslant\log\left(\left(\frac{\sum_{T^{\prime}\in
K^{*}_{j}}(n_{T^{\prime}}+1)}{|K_{j}^{*}|}\right)^{|K_{j}^{*}|}\right)=|K_{j}^{*}|\log\left(\frac{n_{j}}{|K^{*}_{j}|}+1\right),$

Since $|K^{*}_{j}|=O(j)$ we have

$|K_{j}^{*}|\log\left(\frac{n_{j}}{|K^{*}_{j}|}+1\right)=O\left(j\cdot\log\left(\frac{n_{j}}{j}+1\right)\right)$

Combining this with the previous we conclude that the total weight over all
separators is bounded by

$O\left(\sum_{j=1}^{m}\frac{\sqrt{n}}{j}\cdot
j\log\left(\frac{n_{j}}{j}+1\right)\right)=O\left(\sum_{j=1}^{m}\sqrt{n}\cdot\log\left(\frac{n_{j}}{j}+1\right)\right)$
(3)

We have that:

$\sum_{j=1}^{m}\log\left(\frac{n_{j}}{j}+1\right)=O\left(\log\left(\frac{\prod_{j=1}^{m}n_{j}}{m!}\right)\right)$
(4)

Recall that $m=\lceil\sqrt{n}/2\rceil$, which implies that $n/m\leqslant 2m$.
Furthermore, Stirling’s approximation tells us that $\log(m!)=m\log m-m+O(\log
m)$. Since $\sum_{j=1}^{m}n_{j}\leqslant n$ and using the AM-GM inequality we
derive

$\begin{array}[]{lll}\log\left(\frac{\prod_{j=1}^{m}n_{j}}{m!}\right)&\leqslant&\log\left((n/m)^{m}\right)-\log(m!)\\\
&=&m\log(n/m)-\left(m\log m-m+O(\log m)\right)\\\
&\leqslant&m\log(2m)-\left(m\log m-m+O(\log m)\right)\\\ &=&2m+O(\log m)\\\
&=&O(\sqrt{n})\end{array}$

Combing this with Equations (3) and (4) we conclude that the total weight of
the sets $\mathcal{\mathcal{S}}(s)$ is $O(n)$, as claimed.

We conclude that there will be a chord $s_{i}$ whose cliques have total weight
$O(\sqrt{n})$. Then our desired separator is the set
$\mathcal{\mathcal{S}}=\mathcal{\mathcal{S}}_{1}\cup\mathcal{\mathcal{S}}(s_{i})$.

###  5.2 Extension to polygons with holes

We now show how to extend the previous approach so that it also works for a
polygon $P$ with holes. The key ideas remain the same.

As previously, the first step is to put the points that see a reflex vertex
within distance $\sqrt{2}$ into the separator. This can again be done using
the geodesic Voronoi diagram of the reflex vertices. Recall that a vertex of a
hole is defined to be reflex if its angle within $P$ (not: within the hole) is
more than 180 degrees.

In the second step we again construct $\sqrt{n}$ potential separators. When
$P$ has holes, a chord may not split $P$ into two half-polygons. Hence,
instead of taking chords though a centerpoint for $Q_{2}$ in $P$, we proceed
slightly differently. We take a regular centerpoint for $Q_{2}$, and for each
point $g_{i}$ in the rightmost column of the grid $G$ we take the full line
$\ell_{i}$ through $c$ and $p_{i}$. Note that $\ell_{i}\cap P$ can consist of
many chords. Together, these chords split $P$ into several parts; the parts
above $\ell_{i}$ contain at most $2|Q_{2}|/3$ points, and the parts below
$\ell_{i}$ contain at most $2|Q_{2}|/3$ points as well. Hence, the resulting
separators will be balanced.

Points in $Q_{2}$ that lie outside the grid $G$ can be handled as before. They
are added as a singleton to $O(1)$ lines $\ell_{i}$, so they contribute weight
$O(n)$ in total.

Figure 8: A line $\ell_{i}$ which crosses a cell $T$ that has three holes,
colored in red. The blue piece of $\ell_{i}$ is the entrance piece, while the
two green pieces are the non-entrance pieces. Note that each green piece can
be uniquely associated to the pair of entrance-exit points of the hole
preceding it. Marked with a cross are two possible choices of reflex vertices
that are then associated with the green pieces.

We now proceed to describe how to split points in $Q_{2}$ within the grid into
cliques. For each line $\ell_{i}$ and each grid cell $T$ we define an
_entrance piece_ to be the first piece of $\ell_{i}\cap T\cap P$. The
remaining pieces will be referred to as _non-entrance pieces_ (see Fig. 8).
Entrance pieces can be handled exactly as in the case without holes: we look
at all the points in the nine cells surrounding and including $T$ which see
this piece within a distance $1/2$ and split them in a constant number of
cliques. Then the total sum of the weights of these cliques for all the lines
will be $O(n)$ as before. Thus we can select a line $\ell_{i}$ such that the
weight of the cliques we add for their for the entrance pieces is
$O(\sqrt{n})$.

It remains now to handle the non-entrance pieces. Let $\ell_{i}$ be the line
we selected. We will show that $\ell_{i}$ has $O(r)$ non-entrance pieces and
that for each of them we only need to add $O(1)$ cliques. For the first part,
observe that if a line $\ell_{i}$ intersects a hole $2k$ times then the hole
must have at least $k$ reflex vertices of $P$. These $2k$ points of
intersection can be split into $k$ pairs of entrance-exit points. Now note
that a non-entrance piece can be uniquely associated with a unique pair of
entrance-exit points. Therefore we have associated each non-entrance piece
with a unique reflex vertex of $P$ and as a result the number of these pieces
is indeed $O(r)$. The second part is handled as before by adding a constant
number of cliques from the nine cells that surround the cell that contains
each non-entrance piece. Therefore the cliques that correspond to these pieces
add a total weight of $O(r\log\frac{n}{r})$.

To summarize, after having found a separator such that the total weight of the
entrance pieces is $O(\sqrt{n})$ we can add the cliques for the non-entrance
pieces to obtain a separator of weight $O(r\log\frac{n}{r}+\sqrt{n})$.
Together with the cliques from $\mathcal{\mathcal{S}}_{1}$ this gives the
final separator. This finishes the proof of Theorem 5.4.

##  6 Applications

In this section, we show how one can use clique-based separators to get
subexponential algorithms for several classic graph problems, namely Maximum
Independent Set, Feedback Vertex Set, and $q$-Coloring for constant $q$. The
algorithms are very generic: they only use the fact that the clique-based
separators exist and can be computed in polynomial time, so they can
immediately be combined with any of our separator theorems.

There are subexponential algorithms for Maximum Independent Set, Feedback
Vertex Set, and $3$-Coloring in the class of string graphs. In particular,
Bonnet and Rzazewski [4] obtain a running time of $2^{O(n^{2/3}\log n)}$ for
Maximum Independent Set and $3$-Coloring, and $2^{O(n^{2/3}\log^{O(1)}n)}$ for
Feedback Vertex Set. They also show that there is no subexponential algorithm
for $q$-Coloring in string graphs in case of $q\geqslant 4$. All graph classes
studied in this paper are a subclass of string graphs, therefore the
algorithmic results of Bonnet and Rzazewski carry over. In the case of map
graphs, one can derive $2^{O(\sqrt{n}\log n)}$ algorithms for Maximum
Independent Set and Feedback Vertex Set by using the trivial bound $k\leqslant
n$ in the subexponential parameterized algorithms of Fomin et al. [14].
Moreover, the separator theorem of Matoušek [7] can be used to directly get a
$2^{O(\sqrt{n})}$ algorithm for $q$-Coloring for fixed constant $q$. Finally,
for polygons of total complexity $O(n)$, one can use the parameterized
algorithm of Marx and Philipczuk [22] to derive a $2^{O(\sqrt{n}\log n)}$
algorithm for Maximum Independent Set.

Using our separator theorems, we get subexponential algorithms for the three
problems mentioned above in the various graph classes under consideration. The
running times we obtain match or slightly improve the results that can be
obtained by applying the existing results mentioned above. It should be kept
in mind, of course, that the existing results are for more general graph
classes. An exception are our results on map graphs, which were explicitly
studied before and where we improve the running time for Maximum Independent
Set and Feedback Vertex Set from $2^{O(\sqrt{n}\log n)}$ to $2^{O(\sqrt{n})}$.
(Admittedly, the existing results apply in the parameterized setting while
ours don’t.) In any case, the main advantage of our approach is that it allows
us to solve Maximum Independent Set, Feedback Vertex Set and $q$-Coloring on
each of the mentioned graph classes in a uniform manner. Specifically, our
result are as follows.

In map graphs that are given by a linear-sized representation we obtain
$2^{O(\sqrt{n})}$ algorithms for all three problems. In pseudodisk graphs and
in intersection graphs of objects with linear union complexity, we get
$2^{O(n^{2/3}\log n)}$ algorithms for Maximum Independent Set and Feedback
Vertex Set, and a $2^{O(n^{2/3})}$ algorithm for $q$-Coloring with constant
$q$. In intersection graphs of polygonal pseudodisks of total complexity
$O(n)$, the obtained running times are $2^{O(\sqrt{n}\log n)}$ for Maximum
Independent Set and Feedback Vertex Set, and $2^{O(\sqrt{n})}$ for
$q$-Coloring with constant $q$. For intersection graphs of geodesic disks in a
simple polygon, our separators yield the same running times as for
pseudodisks: $2^{O(n^{2/3}\log n)}$ algorithms for Maximum Independent Set and
Feedback Vertex Set, and a $2^{O(n^{2/3})}$ algorithm for $q$-Coloring with
constant $q$.

We also get subexponential algorithms for each of our problems in visibility-
restricted unit-disk graphs in polygons with $r$ reflex vertices (assuming the
total number of vertices is polynomial in $n$). The running time is
$2^{f(n,r)}$, where $f(n,r)=O(\min(n,r\log(n/r))+\sqrt{n})$.

The algorithms. Recall that the Maximum Independent Set problem is to find a
maximum-size subset of pairwise non-adjacent nodes in a given graph $G$. The
Feedback Vertex Set problem asks to find a minimum-size subset of nodes whose
deletion makes $G$ cycle-free. Here it will be more convenient to work with
the complement of the solution, which corresponds to the Maximum Induced
Forest problem: find a maximum-size subset of nodes that induce a forest in
$G$. Finally, in the $q$-Coloring problem, the goal is to decide if $G$ has a
proper $q$-coloring (that is, a coloring of the nodes using $q$ colors such
that adjacent nodes have different colors). For $q$-Coloring, we can
immediately reject any instance that contains a clique of size at least $q+1$,
as such a clique has no proper $q$-coloring. Therefore the weight of each
clique is at most $\log(q+1)=O(1)$, and we only need to deal with instances of
maximum clique size $q$. Consequently, if we have a clique-based separator
$\mathcal{S}$ with $s$ cliques in the graph, then the weight of the separator
is at most $s\cdot\log(q+1)=O(s)$.

We can simplify the presentation by abstracting away the geometry. In what
follows, we fix a graph class $\mathcal{G}$, and we assume that for any
$n$-node graph $G\in\mathcal{G}$ we can compute a balanced clique-based
separator $\mathcal{S}$ of $G$ in polynomial time of size $s_{\mathcal{G}}(n)$
and weight $w_{\mathcal{G}}(n)$. Note that our separator computations rely on
having a geometric representation of the input graph $G$. We will prove the
following theorem.

######  Theorem 6.1.

Let $\mathcal{G}$ be a class of geometric intersection graphs, and suppose
that $\mathcal{G}$ has a clique-based separator theorem of weight
$w_{\mathcal{G}}(n)$ and size $s_{\mathcal{G}}(n)=n^{c}$ for some constant
$0<c<1$. Suppose moreover that these separators can be computed in polynomial
time. Then for an $n$-node graph $G\in\mathcal{G}$ given by its geometric
representation, one can solve:

  1. (1)

Maximum Independent Set in $2^{O(w_{\mathcal{G}}(n))}$ time,

  2. (2)

Feedback Vertex Set in $2^{O(w_{\mathcal{G}}(n))}$ time,

  3. (3)

and $q$-Coloring for fixed constant $q$ in $2^{O(s_{\mathcal{G}}(n))}$ time.

######  Proof 6.2.

(1) We use the same algorithm as De Berg et al. [11], which we recall here.
Let $X$ be a maximum independent set. Notice that any clique $C$ can contain
at most one node from $X$. Therefore, the number of ways that a given set $X$
can intersect a clique-based separator $\mathcal{S}$ is at most

$\prod_{C\in\mathcal{S}}(|C|+1)=2^{\sum_{C\in\mathcal{S}}\log(|C|+1)}=2^{\mathrm{weight}(\mathcal{S})}.$

We can use a simple divide-and-conquer strategy to find the set $X$. We
compute a separator $\mathcal{S}$, and for all independent sets
$X_{\mathcal{S}}$ in $\bigcup_{C\in\mathcal{S}}C$, we will find the largest
independent set that $X_{\mathcal{S}}$ is a part of. To this end we consider
the graph
$G_{X_{\mathcal{S}}}:=G[V\setminus(N(X_{\mathcal{S}})\cup\bigcup_{C\in\mathcal{S}}C)]$,
that is, the graph $G$ where we remove the nodes of the separator as well as
those nodes that neighbor a node in $X_{S}$. We compute a maximum independent
set on each side of the separator, restricting ourselves to
$G_{X_{\mathcal{S}}}$, in a recursive fashion. The correctness follows from
the fact that the set $X^{*}_{\mathcal{S}}:=X\cap(\bigcup_{C\in\mathcal{S}}C)$
will be considered by the algorithm, and then the remainder of $X$ on each
side of the separator will form maximum independent sets within that side.

Since the number of sets $X_{S}$ to enumerate is at most
$2^{\mathrm{weight}(\mathcal{S})}\leqslant 2^{w_{\mathcal{G}}(n)}$, we get the
following recursion for the running time:

$T(n)=2^{w_{\mathcal{G}}(n)}\big{(}2T(\beta n)+\mathrm{poly}(n)\big{)},$

where $\beta<1$ is the balance factor of the separator theorem. Solving this
recursion yields that $T(n)=2^{O(w_{G}(n))}$, as required.

(2) We solve the complement problem, Maximum Induced Forest. Observe that an
induced forest can have at most two nodes in each clique, therefore an induced
forest with node set $X$ can intersect a clique-based separator $\mathcal{S}$
in at most

$\prod_{C\in\mathcal{S}}\left(\binom{|C|}{2}+|C|+1\right)<\prod_{C\in\mathcal{S}}(|C|+1)^{2}=2^{\sum_{C\in\mathcal{S}}2\log(|C|+1)}=2^{2\cdot\mathrm{weight}(\mathcal{S})}$

many ways. However, unlike with Maximum Independent Set, the solutions on the
two sides of the separator are not completely independent: we must ensure that
their union is a forest, and does not induce any cycles. Let $B$ be a set of
nodes in $G$, called _boundary nodes_ , and let $\pi$ be a partition of $B$.
We say that a forest $X$ _realizes_ $\pi$ if $B\subseteq X$ and $x,y\in B$ are
in the same connected component of $G[X]$ if and only if they are in the same
partition class of $\pi$.

A separator can contain up to $O(|\mathcal{S}|)$ nodes of the solution forest,
which will become boundary nodes in $A\cup S$ and $B\cup S$ with some specific
partitions. Formally, we need to solve the following problem: given a graph
$G$, a boundary node set $B$ and a partition $\pi$, find the maximum induced
forest of $G$ that realizes $\pi$ on $B$. In order to keep the running time
small, we need to ensure that this boundary set stays small compared to the
size of the instance in the recursion tree. We observe that all of our
separators can be extended to achieve balance with respect to any node set
$W\subset V(G)$. Using such separators, we can ensure that the number of
boundary nodes for an instance of size $n$ during the recursion is at most
$O(s_{\mathcal{G}}(n))$ by for example taking separators that are balanced
with respect to all nodes and the boundary set $B$ alternatingly. See [10] for
a different way to keep the boundary set small. As $B$ has
$|B|^{O(|B|)}=2^{O(|B|\log|B|)}=2^{O(s_{\mathcal{G}}(n)\log n)}$ partitions,
the running time recursion is

$T(n)=2^{2w_{\mathcal{G}}(n)+O(s_{G}(n)\log
n)}(T(\beta^{\prime}n)+\mathrm{poly}(n)),$

where $\beta^{\prime}<1$ is a constant that depends only on the separator
balance factor $\beta$ and the size function $s_{\mathcal{G}}$. This gives a
running time of

$T(n)=2^{O(w_{\mathcal{G}}(n)+s_{G}(n)\log n)}.$

The running time can be further reduced by using the rank-based approach of
Bodlaender et al. [3]. Here instead of trying all partitions, one only needs
to keep track of a so-called _representative set_ of $2^{O(|B|)}$ weighted
partitions, and update these representative sets bottom-up in the recursion
tree. We can implement this technique similarly to earlier implementations.
See [11] for an example with maximum induced forest and [10] for using the
technique in a separator-based divide-and-conquer algorithm) without a tree-
decomposition. The resulting algorithm has the following running time
recursion:

$T(n)=2^{2w_{\mathcal{G}}(n)+O(s_{G}(n))}(T(\beta^{\prime}n)+\mathrm{poly}(n))=2^{O(w_{\mathcal{G}}(n))}(T(\beta^{\prime}n)+\mathrm{poly}(n)).$

Solving the recursion gives the desired running time of
$T(n)=2^{O(w_{\mathcal{G}}(n))}$.

(3) We start by checking if there is a clique of size at least $q+1$. This can
be done by brute force in $O(n^{q+1})=\mathrm{poly}(n)$ time. If such a clique
is found then we can reject. Otherwise, we use a divide-and-conquer strategy:
for all proper $q$-colorings of the separator node set
$S=\bigcup_{C\in\mathcal{S}}C$, we solve the problem recursively for the node
sets $S_{1}=S\cup A$ and $S_{2}=S\cup B$, where $A$ and $B$ are the two sides
of the separator. Note that in order to make this work, we in fact solve a
slightly extended problem, where some arbitrary subset of nodes are already
colored, and the task is to extend this coloring to a proper $q$-coloring.

As cliques have size at most $q=O(1)$, a separator consisting of
$s_{\mathcal{G}}(n)$ cliques has $O(s_{\mathcal{G}}(n))$ nodes, and its nodes
can be colored in at most
$q^{O(s_{\mathcal{G}}(n))}=2^{O(s_{\mathcal{G}}(n))}$ many ways. The running
time obeys the recurrence

$T(n)=2^{O(s_{\mathcal{G}}(n))}(T(\beta^{\prime}n)+\mathrm{poly}(n)),$

where $\beta^{\prime}<1$ is a constant such that
$\max(|A|,|B|)+|S|<\beta^{\prime}n$ is guaranteed by the separator for $n$
large enough. The recursion solves to $T(n)=2^{O(s_{\mathcal{G}}(n))}$.

##  7 Concluding Remarks

We showed how clique-based separators with sub-linear weight can be
constructed for various classes of intersection graphs which involve non-fat
objects. The main advantage of our approach is that we can solve different
problems in the graph classes we study in a uniform manner. There are several
natural questions that are left open. Some are listed below.

  * •

Improving the bound for geodesic disks and adding holes. Our bound on geodesic
disks is directly derived by our result on pseudo-disks. However, geodesic
disks are much less general than pseudo-disks (and “closer” to regular disks).
Hence, one would expect that the optimal weight is closer to $O(\sqrt{n})$. If
we allow our polygon to have holes, then our approach for geodesic disks no
longer works. Indeed, it is easy to see that even after applying our
perturbation scheme, the resulting objects can intersect each other more than
two times.

  * •

Improving the bound for pseudo-disks. Regarding pseudo-disks, an interesting
result [27] states that in every finite family of pseudo-disks in the plane
one can find a “small” one, in the sense that it is intersected by only a
constant number of disjoint pseudo-disks. This property is also shared by, for
instance, convex fat objects. Does this mean that the two graph classes are
related in some natural way? If yes, could this connection be exploited to
construct separators with better bounds?

## References

  * [1] B. Aronov, M.T. Berg, de, E. Ezra, and M. Sharir.  Improved bounds for the union of locally fat objects in the plane.  SIAM Journal on Computing, 43(2):543–572, 2014.  doi:10.1137/120891241.
  * [2] Boaz Ben-Moshe, Olaf A. Hall-Holt, Matthew J. Katz, and Joseph S. B. Mitchell.  Computing the visibility graph of points within a polygon.  In Proc. 20th ACM Symposium on Computational Geometry, pages 27–35. ACM, 2004.  doi:10.1145/997817.997825.
  * [3] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof.  Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.  Inf. Comput., 243:86–111, 2015.  doi:10.1016/j.ic.2014.12.008.
  * [4] Édouard Bonnet and Pawel Rzazewski.  Optimality program in segment and string graphs.  Algorithmica, 81(7):3047–3073, 2019.  doi:10.1007/s00453-019-00568-7.
  * [5] Michael Breen.  A Helly-type theorem for intersections of compact connected sets in the plane.  Geometriae Dedicata, 71:111–117, 1998.  doi:10.1023/A:1005003212822.
  * [6] Timothy M. Chan.  Polynomial-time approximation schemes for packing and piercing fat objects.  J. Algorithms, 46(2):178–189, 2003.  doi:10.1016/S0196-6774(02)00294-8.
  * [7] Zhi-Zhong Chen.  Approximation algorithms for independent sets in map graphs.  J. Algorithms, 41(1):20–40, 2001.  doi:10.1006/jagm.2001.1178.
  * [8] Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou.  Map graphs.  J. ACM, 49(2):127–138, 2002.  doi:10.1145/506147.506148.
  * [9] Kenneth L. Clarkson and Peter W. Shor.  Application of random sampling in computational geometry, II.  Discret. Comput. Geom., 4:387–421, 1989.  doi:10.1007/BF02187740.
  * [10] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay.  An ETH-tight exact algorithm for euclidean TSP.  In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 450–461, 2018.  doi:10.1109/FOCS.2018.00050.
  * [11] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden.  A framework for Exponential-Time-Hypothesis-tight algorithms and lower bounds in geometric intersection graphs.  SIAM J. Comput., 49:1291–1331, 2020.  doi:10.1137/20M1320870.
  * [12] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars.  Computational Geometry: Algorithms and Applications (3rd Edition).  Springer, 2008.  URL: https://www.worldcat.org/oclc/227584184.
  * [13] Hristo Djidjev and Shankar M. Venkatesan.  Reduced constants for simple cycle graph separation.  Acta Informatica, 34(3):231–243, 1997.  doi:10.1007/s002360050082.
  * [14] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Decomposition of map graphs with applications.  In Proc. 46th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 60:1–60:15, 2019.  doi:10.4230/LIPIcs.ICALP.2019.60.
  * [15] Jacob Fox, János Pach, and Csaba D. Tóth.  A bipartite strengthening of the crossing lemma.  J. Comb. Theory, Ser. B, 100(1):23–35, 2010.  doi:10.1016/j.jctb.2009.03.005.
  * [16] Sariel Har-Peled and Kent Quanrud.  Approximation algorithms for polynomial-expansion and low-density graphs.  SIAM J. Comput., 46(6):1712–1744, 2017.  doi:10.1137/16M1079336.
  * [17] Klara Kedem, Ron Livne, János Pach, and Micha Sharir.  On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles.  Discret. Comput. Geom., 1:59–70, 1986.  doi:10.1007/BF02187683.
  * [18] Sándor Kisfaludi-Bak.  Hyperbolic intersection graphs and (quasi)-polynomial time.  In Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1621–1638, 2020.  doi:10.1137/1.9781611975994.100.
  * [19] Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden.  How does object fatness impact the complexity of packing in $d$ dimensions?  In 30th International Symposium on Algorithms and Computation, ISAAC 2019, volume 149 of LIPIcs, pages 36:1–36:18, 2019.  doi:10.4230/LIPIcs.ISAAC.2019.36.
  * [20] James R. Lee.  Separators in region intersection graphs.  In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, volume 67 of LIPIcs, pages 1:1–1:8, 2017.  doi:10.4230/LIPIcs.ITCS.2017.1.
  * [21] Richard J. Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM J. Appl. Math, 36(2):177–189, 1977.  doi:doi/10.1137/0136016.
  * [22] Dániel Marx and Michal Pilipczuk.  Optimal parameterized algorithms for planar facility location problems using voronoi diagrams.  In Proc. 23rd Annual European Symposium on Algorithms (ESA), volume 9294 of Lecture Notes in Computer Science, pages 865–877. Springer, 2015.  doi:10.1007/978-3-662-48350-3\\_72.
  * [23] Jirí Matousek.  Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics.  Springer, 2002.
  * [24] Jirí Matoušek.  Near-optimal separators in string graphs.  Comb. Probab. Comput., 23(1):135–139, 2014.  doi:10.1017/S0963548313000400.
  * [25] 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.  doi:10.1145/256292.256294.
  * [26] János Pach and Micha Sharir.  Geometric incidences.  In János Pach, editor, Towards a Theory of Geometric Graphs (Contemporary Mathematics, Vol. 342), pages 185–223. Amer. Math. Soc., 2004\.
  * [27] Rom Pinchasi.  A finite family of pseudodiscs must include a “small” pseudodisc.  SIAM Journal on Discrete Mathematics, 28:1930–1934, 10 2014.  doi:10.1137/130949750.
  * [28] Ricky Pollack, Micha Sharir, and Günter Rote.  Computing the geodesic center of a simple polygon.  Discret. Comput. Geom., 4(6):611–626, 1989.  doi:10.1007/BF02187751.
  * [29] Rajiv Raman and Saurabh Ray.  Constructing planar support for non-piercing regions.  Discrete & Computational Geometry, pages 1–25, 2020.
  * [30] Warren D. Smith and Nicholas C. Wormald.  Geometric separator theorems & applications.  In 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 232–243. IEEE Computer Society, 1998.  doi:10.1109/SFCS.1998.743449.