# ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs111This work was
supported by the National Research Foundation of Korea(NRF) grant funded by
the Korea government(MSIT) (No.RS-2023-00209069).

Shinwoo An222Pohang University of Science and Technology, Korea. Email:
<EMAIL_ADDRESS>Eunjin Oh333Pohang University of Science and
Technology, Korea. Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider the Cycle Packing problem on unit disk graphs
defined as follows. Given a unit disk graph $G$ with $n$ vertices and an
integer $k$, the goal is to find a set of $k$ vertex-disjoint cycles of $G$ if
it exists. Our algorithm runs in time $2^{O(\sqrt{k})}n^{O(1)}$. This improves
the $2^{O(\sqrt{k}\log k)}n^{O(1)}$-time algorithm by Fomin et al. [SODA 2012,
ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time
hypothesis.

##  1 Introduction

The Cycle Packing problem is a fundamental graph problem defined as follows.
Given an undirected graph $G$ and an integer $k$, the goal is to check if
there is a set of $k$ vertex-disjoint cycles of $G$. This problem is NP-hard
even for planar graphs. This motivates the study from the viewpoints of
parameterized algorithms [30] and approximation algorithms [20, 27]. For
approximation algorithms, we wish to approximate the maximum number of vertex-
disjoint cycles of $G$ in polynomial time. The best known polynomial time
algorithm has approximation factor of $O(\sqrt{\log n})$ [27]. This is almost
optimal in the sense that it is quasi-NP-hard to approximate the maximum
number of vertex-disjoint cycles of a graph within a factor of
$O(\log^{1/2-\epsilon}n)$ for any $\epsilon>0$ [27]. Several variants also
have been considered, for instance, finding a maximum number of vertex-
disjoint triangles [22], finding a maximum number of vertex-disjoint odd
cycles [26], finding a maximum number of edge-disjoint cycles [20], and
finding a maximum number of vertex-disjoint cycles in directed graphs [20].

In this paper, we study the Cycle Packing problem from the viewpoint of
parameterized algorithms when the parameter $k$ is the number of vertex-
disjoint cycles. This problem is one of the first problems studied from the
perspective of Parameterized Complexity. By combining the Erdős-Pósa theorem
[13] with a $2^{O(tw\log tw)}n^{O(1)}$-time standard dynamic programming
algorithm for this problem, where $tw$ is the treewidth of the input graph,
one can solve the Cycle Packing problem in $2^{O({k}\log^{2}k)}n^{O(1)}$ time.
This algorithm was improved recently by Lokshtanov et al. [30]. They improved
the exponent on the running time by a factor of $O(\log\log k)$. As a lower
bound, no algorithm for the Cycle Packing problem runs in $2^{o(tw\log
tw)}n^{O(1)}$ time assuming the exponential-time hypothesis (ETH) [8].

For several classes of graphs, the Cycle Packing problem can be solved
significantly faster. For planar graphs, Bodlaender et al. [4] presented a
$2^{O(\sqrt{k})}n^{O(1)}$-time algorithm, and showed that the Cycle Packing
problem admits a linear kernel. Also, one can obtain an algorithm with the
same time bound using the framework of Dorn et al. [12]. Later, Dorn et al.
[11] presented a $2^{O(\sqrt{k})}n^{O(1)}$-time algorithm which works on
$H$-minor-free graphs for a fixed graph $H$. As a main ingredient, they
presented a branch decomposition of a $H$-minor-free graph which has a certain
structure called the _Catalan structure_. This structure allows them to bound
the ways a cycle may cross a cycle separator of an $H$-minor-free graph. Also,
there is a subexponential-time parameterized algorithm for the Cycle Packing
problem for map graphs [17]. These results raise a natural question whether a
subexponential-time algorithm for the Cycle Packing problem can be obtained
for other graph classes.

In this paper, we focus on _unit disk graphs_. For a set $V$ of points in the
plane, the _unit disk graph_ $G$ is defined as the undirected graph whose
vertices correspond to the points of $V$ such that two vertices are connected
by an edge in $G$ if and only if their Euclidean distance is at most one. It
can be used as a model for broadcast networks: The points of $V$ represent
transmitter-receiver stations with the same transmission power. Unit disk
graphs have been studied extensively for various algorithmic problems [5, 7,
14, 23, 24, 25]. Also, several NP-complete problems have been studied for unit
disk graphs (and geometric intersection graphs) from the viewpoint of
parameterized algorithms, for example, the Steiner Tree, Bipartization,
Feedback Vertex Set, Clique, Vertex Cover, Long Path and Cycle Packing
problems [1, 2, 3, 6, 15, 16, 19, 31, 32]. All problems listed above, except
for the Steiner Tree problem, admit subexponential-time parameterized
algorithms for unit disk graphs. The study of parameterized algorithms for
unit disk graphs and geometric intersection graphs is currently a highly
active research area in Computational Geometry.

To the best of our knowledge, the study of subexponential-time _parameterized
algorithms_ for unit disk graphs was initiated by Fomin et al. [19]. They
focused on the Feedback Vertex Set444Given a graph $G$ and an integer $k$,
find a set $F$ of $k$ vertices such that $G-F$ does not have a cycle. and
Cycle Packing problems and presented $2^{O({k}^{0.75}\log k)}n^{O(1)}$-time
algorithms. Later, they were improved to take $2^{O({\sqrt{k}}\log
k)}n^{O(1)}$ time by [16], and this approach also works for the Long Path and
Long Cycle problems555Given a graph $G$ and an integer $k$, find a path and a
cycle of $G$ with $k$ vertices, respectively. with the same time bound. Since
the best known lower bound for all these problems is
$2^{\Omega({\sqrt{k}})}n^{O(1)}$ assuming ETH [16], it is natural to ask if
these problems admit ETH-tight algorithms. Recently, this question was
answered affirmatively for all problems mentioned above, except for the Cycle
Packing problem [1, 18]. It seems that the approaches used in [1, 18] are not
sufficient for obtaining a faster algorithm for the Cycle Packing problem.
After preprocessing, they reduce the original problems for unit disk graphs to
the weighted variants of the problems for graphs with treewidth $O(\sqrt{k})$,
and then they use $2^{O(tw)}n^{O(1)}$-time algorithms for the weighted
variants of the problems for a graph with treewidth $tw$. However, no
algorithm for the Cycle Packing problem runs in $2^{o(tw\log tw)}n^{O(1)}$
time for a graph with treewidth $tw$ assuming ETH [8].

##### Our Result.

In this paper, we present an ETH-tight parameterized algorithm for the Cycle
Packing problem on unit disk graphs with $n$ vertices, which runs in
$2^{O(\sqrt{k})}n^{O(1)}$ time. No ETH-tight algorithm even for the non-
parameterized version was known prior to this work. In the case of the Long
Path/Cycle and Feedback Vertex Set problems, ETH-tight algorithms running in
$2^{O(\sqrt{n})}$ time were already known [9] before the ETH-tight
parameterized algorithms were presented [1, 18]. As a tool, we introduce a new
recursive decomposition of the plane into regions with $O(1)$ boundary
components with respect to a unit disk graph $G$ such that the edges of $G$
crossing the boundary of each region form a small number of cliques. It can be
used for other problems such as the non-parameterized version of the Odd Cycle
Packing problem, and the parameterized versions of the $d$-Cycle Packing and
$2$-Bounded-Degree Vertex Deletion problems on unit disk graphs. For details,
see Appendix A.

##  2 Overview of Our Algorithm

In this section, we give an overview of our algorithm for the Cycle Packing
problem on unit disk graphs. We are given a unit disk graph $G=(V,E)$ along
with its geometric representation. Here, each edge of $G$ is drawn as a line
segment connecting its endpoints. We do not distinguish a vertex of $G$ and
its corresponding point of $\mathbb{R}^{2}$ where it lies. Let $\mathcal{M}$
be a partition of the plane into interior-disjoint squares of diameter one. We
call it a _map_ of $G$,666It is a grid in the case of unit disk graphs, but we
define a map as general as possible in the appendices. and a square of
$\mathcal{M}$ a _cell_ of $\mathcal{M}$. Notice that the subgraph of $G$
induced by $M\cap V$ is a clique. Throughout this paper, we let $\alpha$ be
the maximum number of cells of $\mathcal{M}$ intersected by one edge of $G$.
Note that $\alpha=O(1)$. For any integer $r$, a cell $M$ of $\mathcal{M}$ is
called an _$r$ -neighboring cell_ of $M^{\prime}$ of $\mathcal{M}$ if a line
segment connecting $M$ and $M^{\prime}$ intersects at most $r$ cells of
$\mathcal{M}$. Note that a cell of $\mathcal{M}$ has $O(1)$
$\alpha$-neighboring cells.

For a region $A\subseteq\mathbb{R}^{2}$, we use $\partial A$ to denote the
boundary of $A$. For a subset $U$ of $V$, we let $G[U]$ be the subgraph of $G$
induced by $U$. For convenience, we let $G[V\setminus U]=G\setminus U$. We
often use $V(G)$ and $E(G)$ to denote the vertex set of $G$ and the edge set
of $G$, respectively. For a set $\Gamma^{\prime}$ of paths and cycles of $G$,
we let $\textsf{end}(\Gamma^{\prime})$ be the set of end points of the _paths_
of $\Gamma^{\prime}$. Moreover, we may seen $\Gamma^{\prime}$ as a set of
edges, and we let $V(\Gamma^{\prime})$ be the set of all vertices of the
_paths and cycles_ of $\Gamma^{\prime}$.

###  2.1 Standard Approach and Main Obstacles

Let $\Gamma$ be a set of $k$ vertex-disjoint cycles of $G$. Ideally, we want
to recursively decompose the plane into smaller regions each consisting of
$O(1)$ boundary curves so that “very few” edges of $\Gamma$ cross the boundary
of each region. Then we want to compute $\Gamma$ using dynamic programming on
the recursive decomposition of the plane. For each region $A$, we want to
guess the set $E^{\prime}$ of edges of $\Gamma$ crossing the boundary of $A$,
and then want to guess the pairing $\mathcal{P}$ of the vertices of
$\textsf{end}(E^{\prime})\cap A$ such that two vertices of
$\textsf{end}(E^{\prime})\cap A$ belong to the same pair of $\mathcal{P}$ if
and only if a path of $\Gamma\setminus E^{\prime}$ has them as its endpoints.
Then for a fixed pair $(E^{\prime},\mathcal{P})$, it suffices to compute the
maximum number of vertex-disjoint cycles of $\Gamma^{\prime}$ contained in $A$
over all sets $\Gamma^{\prime}$ of vertex-disjoint cycles and paths of the
subgraph of $G$ induced by the edges fully contained in $A$ and the edges of
$E^{\prime}$ which match the given information. In fact, this is a standard
way to deal with this kind of problems.

The Cycle Packing problem on planar graphs can be solved using this approach
[12]. Given a simple closed curve $\eta$ intersecting a planar graph only at
its vertices, consider the maximal paths of the cycles of $\Gamma$ contained
in the interior of $\eta$. Clearly, they do not intersect in its drawing, and
thus they have a Catalan structure. Thus once the crossing points of the
cycles of $\Gamma$ with $\eta$ are fixed, we can enumerate $2^{O(w)}$ pairings
one of which is the correct pairing of the endpoints of the paths, where $w$
is the number of crossing points between $\Gamma$ and $\eta$. However, we
cannot directly apply this approach to unit disk graphs mainly because $G$ has
a large clique, and two vertex-disjoint cycles of $G$ cross in their drawings.
More specifically, we have the following three obstacles.

##### First issue.

We do not have any tool for recursively decomposing the plane into smaller
regions such that the boundary of each region is crossed by a small number of
edges of $\Gamma$. De Berg et al. [9] presented an algorithm for computing a
rectangle separating $V$ in a balanced way such that the total _clique-weight_
of the cells of $\mathcal{M}$ crossing the boundary of the rectangle is
$O(\sqrt{n})$, where the clique-weight of a cell $M$ is defined as
$\log(|M\cap V|+1)$. Using this, we can show that the boundary of this
rectangle is crossed by $O(\sqrt{n})$ edges of $\Gamma$. However, this only
works for a single recursion step. If we apply the algorithm by de Berg et al.
[9] recursively, a region we obtained after $d$ steps can have $\Theta(d)$
boundary components. Note that $d=\omega(1)$ in the worst case. To handle
this, whenever the number of boundary components of a current region exceeds a
certain constant, we have to reduce the number of boundary components using a
balanced separator separating the boundary components. However, it seems
unclear if it is doable using the algorithm by de Berg et al. [9] as their
separator works for fat objects, but the boundary components are not
necessarily fat. Another issue is that we need a separator of complexity
$O(\sqrt{k})$ instead of $O(\sqrt{n})$.

##### Second issue.

Even if we have a recursive decomposition of the plane into regions such that
the boundary of each region $A$ is crossed by $O(\sqrt{k})$ edges of $\Gamma$,
we have to guess the number of edges of $\Gamma$ crossing $\partial A$ among
all edges of $G$ crossing $\partial A$. Since the number of edges of $G$
crossing $\partial A$ can be $\Theta(n)$, a naive approach gives
$n^{O(\sqrt{k})}$ candidates for the correct guess. This issue happens also
for other problems on unit disk graphs such as Long Path/Cycle and Feedback
Vertex Set. The previous results on these problems [1, 18] handle this issue
by using the concept of the clique-weight of a cell of $\mathcal{M}$, which
was introduced by de Berg et al. [9]. We can handle this issue as they did.

##### Third issue.

Suppose that we have a recursive decomposition with desired properties, and we
have the set $E^{\prime}$ of $O(\sqrt{k})$ edges of $\Gamma$ crossing the
boundary of $A$ for each region $A$. For convenience, assume that $\partial A$
is connected. The number of all pairings of
$\textsf{end}(E^{\prime})\cap\partial A$ is $2^{O(\sqrt{k}\log k)}$, which
exceeds the desired bound. But not all such pairings can be the correct
pairing of a set of maximum-number of cycles of $G$. For a vertex $a$ of
$\textsf{end}(E^{\prime})\cap\partial A$, let $\bar{a}$ be the first point on
$A$ from $a$ along the edge of $E^{\prime}$ incident to $a$. If no two cycles
of $\Gamma$ cross in their drawings, the cyclic order of
$\bar{a},\bar{b},\bar{a}^{\prime}$ and $\bar{b}^{\prime}$ along $\partial A$
is either $\langle\bar{a},\bar{b},\bar{a}^{\prime},\bar{b}^{\prime}\rangle$ or
$\langle\bar{b},\bar{a},\bar{a}^{\prime},\bar{b}^{\prime}\rangle$ for any two
pairs $(a,b)$ and $(a^{\prime},b^{\prime})$ of $\mathcal{P}$, where
$\mathcal{P}$ denotes the correct pairing of $\textsf{end}(E^{\prime})\cap A$.
That is, $\mathcal{P}$ is a _non-crossing pairing_. It is known that for a
fixed set $P$ (which is indeed $\textsf{end}(E^{\prime})\cap A$), the number
of non-crossing pairings of $P$ is $2^{O(|P|)}$ (which is indeed
$2^{O(\sqrt{k})}$). However, two cycles of $\Gamma$ can cross in general, and
thus $\mathcal{P}$ is not necessarily non-crossing.

###  2.2 Our Methods

We can handle the three issues using the following two main ideas.

##### Surface cut decomposition of small clique-weighted width.

We handle the first issue by introducing a new decomposition for unit disk
graphs, which we call a _surface cut decomposition_. It is a recursive
decomposition of the plane into regions (called _pieces_) with $O(1)$ boundary
components such that each piece has _clique-weight_ $O(\sqrt{\ell})$, where
$\ell$ denotes the number of vertices of degree at least three in $G$. Let
$\textsf{cut}({A})$ denote the set of edges with at least one endpoint on $A$
that intersect $\partial A$. An edge of $\textsf{cut}({A})$ might have both
endpoints in $A$. For an illustration, see Figure 3. We show that the total
clique-weight of the cells of $\mathcal{M}$ containing the endpoints of the
edges of $\textsf{cut}({A})$ is small for each piece $A$. The clique-weight of
$A$ is defined as the total clique-weight of the cells containing the
endpoints of $\textsf{cut}({A})$. Recall that the clique-weight of a cell $M$
is defined as $\log(|M\cap V|+1)$.

To handle the second issue, we show that $O(1)$ vertices contained in $M$ lie
on the cycles of $\Gamma^{\prime}$ for each cell $M$, and every cycle of
$\Gamma\setminus\Gamma^{\prime}$ is a triangle, where $\Gamma^{\prime}$ is the
set of cycles of $\Gamma$ visiting at least two vertices from different cells
of $\mathcal{M}$. We call this property the _bounded packedness property_.
Assume that we have a cell $M$ of clique-weight $\omega$. It is sufficient to
specify the vertices in $M$ appearing in $\Gamma^{\prime}$. For the other
vertices in $M$, we construct a maximum number of triangles. By the bounded
packedness property of $\Gamma$, the number of choices of the edges in $M$
appearing in $\Gamma^{\prime}$ is reduced to $|M\cap
V|^{O(1)}=2^{O(|\log(|M\cap V|+1)|}=2^{O(\omega)}$. This also implies that the
boundary of each region $A$ is crossed by $O(\omega)$ cut edges.

##### Deep analysis on the intersection graphs of cycles.

We handle the third issue as follows. We choose $\Gamma$ in such a way that it
has the minimum number of edges among all possible solutions. Consider a piece
$A$ not containing a hole. Suppose that we have the set $E^{\prime}$ of
$O(\sqrt{k})$ cut edges of $\Gamma$ crossing the boundary of $A$. Due to the
bounded packedness property, we can ignore the cycles of $\Gamma$ fully
contained in a single cell of $\mathcal{M}$. Let $\Gamma^{\prime}$ be the set
of the remaining cycles of $\Gamma$. Let $\Pi$ be the set of path components
of the subgraph of $\Gamma^{\prime}$ induced by $V\cap A$. An endpoint of a
path $\pi$ of $\Pi$ is incident to a cut edge of $A$ along $\Gamma$. We extend
the endpoint of $\pi$ along the cut edge until it hits $\partial A$. Let
$\bar{\Pi}$ be the set of the resulting paths.

We aim to compute a small number of pairings of $\textsf{end}(\bar{\Pi})$ one
of which is the correct pairing of $\bar{\Pi}$. To do this, we consider the
intersection graph $\mathcal{G}$ of the paths of $\bar{\Pi}$: a vertex of
$\mathcal{G}$ corresponds to a path of $\bar{\Pi}$, and two vertices are
adjacent in $\mathcal{G}$ if and only if their paths cross in their drawings.
We show that the intersection graph $\mathcal{G}$ of $\bar{\Pi}$ is
$K_{z,z}$-free for a constant $z$. We call this property the _quasi-planar
property_. Note that the paths of $\bar{\Pi}$ may cross even if $\Gamma$ has
the bounded packedness property. See Figure 1.

Figure 1: (a) The drawings of two cycles of an optimal solution may cross. We
cannot replace them into triangles (gray color). (b) Two paths of $\bar{\Pi}$
are cross-ordered, and their drawings cross.

Then we relate the paring of $\textsf{end}(\bar{\Pi})$ to $\mathcal{G}$. We
say two paths of $\bar{\Pi}$, one ending at $a$ and $b$, and one ending at
$a^{\prime}$ and $b^{\prime}$, are _cross-ordered_ , if $a,a^{\prime},b$ and
$b^{\prime}$ appear along $\partial A$ in this order. For any two _cross-
ordered_ paths of $\bar{\Pi}$, their drawings cross since they are contained
in $A$. Given a pairing $\mathcal{P}$ of $\textsf{end}(\bar{\Pi})$, we define
the _circular arc crossing graph_ of $\mathcal{P}$ such that each vertex
corresponds to a pair of $\mathcal{P}$, and two vertices are adjacent if their
corresponding pairs are cross-ordered. By the previous observation, the
circular arc crossing graph is isomorphic to a subgraph of $\mathcal{G}$. Thus
it suffices to enumerate all pairings whose corresponding circular arc
crossing graphs are $K_{z,z}$-free. We show that the number of all such
pairings is $2^{O(\omega)}$.

In this way, we can enumerate $2^{O(\sqrt{k})}$ pairings of
$\textsf{end}(\bar{\Pi})$ one of which is the correct pairing of $\bar{\Pi}$
in the case that $\partial A$ is connected. We can handle the general case
where $\partial A$ has more than one curve in a similar manner although there
are some technical issues.

##  3 Preliminaries

For a connected subset $A$ of $\mathbb{R}^{2}$, let $\partial A$ denote the
boundary of $A$. The _closure_ of $A$, denoted by $\textsf{cl}(A)$, is defined
as $A\cup\partial A$. Also, the _interior_ of $A$, denoted by
$\textsf{int}(A)$, is defined as $\textsf{cl}(A)\setminus\partial A$. The
_diameter_ of $A$ is defined as the maximum Euclidean distance between two
points of $A$. A _curve_ is the image of a continuous function from an unit
interval into the plane. For any two points $a$ and $b$ in the plane, we call
a curve connecting $a$ and $b$ an _$a$ -$b$ curve_. A connected subset
$C^{\prime}$ of $C$ is a _subcurve_ of $C$. For a simple closed curve $C$,
$\mathbb{R}^{2}\setminus C$ consists of two disjoint regions by the boundary
curve theorem: an unbounded region and bounded region. We call the unbounded
region the exterior of $C$, and denote it by $C^{\textsf{ex}}$. Also, we call
the other region the interior of $C$, and denote it by $C^{\textsf{in}}$. If a
simple closed curve $C$ intersects a plane graph $G$ only at vertices of $G$,
we call $C$ a _noose_ of $G$. If it is clear from the context, we simply call
it a _noose_.

Let $G=(V,E)$ be a graph. For a subset $U$ of $V$, we let $G[U]$ be the
subgraph of $G$ induced by $U$. For convenience, we say the subgraph of $G$
induced by $V\setminus U$ as $G\setminus U$. We often use $V(G)$ and $E(G)$ to
denote the vertex set of $G$ and the edge set of $G$, respectively. By a
slight abuse of notation, we let $|G|$ be the number of vertices of $G$. A
_drawing_ of $G$ is a representation of $G$ in the plane such that the
vertices are drawn as points in the plane, and the edges are drawn as curves
connecting their endpoints. Here, the curves corresponding to two edges can
cross. A _drawing_ is called a _straight-line_ drawing if the edges are drawn
as line segments. We sometimes use a graph $G$ and its drawing interchangeably
if it is clear from the context. We deal with undirected graphs only, and the
_length_ of a path is defined as the number of edges in the path.

Throughout this paper, for a graph $G=(V,E)$ with vertex-weight
$c:V\rightarrow\mathbb{R}$, we let

$c_{\textsf{sos}}({G})=\sqrt{\sum_{v\in V}(c(v))^{2}},\quad
c_{\textsf{sum}}(G)=\sum_{v\in V}c(v),\quad c_{\textsf{max}}(G)=\max_{v\in
V}c(v).$

In this paper, we describe our algorithm in a more general way so that it
works for larger classes of geometric intersection graphs such as intersection
graphs of similarly-sized disks and squares. In particular, our algorithm
works on a graph drawn in the plane with a straight-line drawing satisfying
the _icf -property_ and having a _map_.

###  3.1 Geometric Tools: ICF-Property and Map Sparsifier

Let $G=(V,E)$ be a graph with its straight-line drawing. We say two edges
_cross_ if the drawing of two edges cross. We say $G$ has the _induced-
crossing-free_ property, the icf-property in short, if for any crossing edges
$xx^{\prime}$ and $yy^{\prime}$ of $G$, three of
$\\{x,x^{\prime},y^{\prime},y\\}$ form a cycle in $G$. As an example, a unit
disk graph $G$ admits the icf-property.

######  Observation 1.

For any crossing edges $xx^{\prime}$ and $yy^{\prime}$ of a unit disk graph,
three of $\\{x,x^{\prime},y^{\prime},y\\}$ form a cycle.

###### Proof.

For a point $a,b\in\mathbb{R}^{2}$, we denote the Euclidean distance between
$a$ and $b$ by $|ab|$. Without loss of generality, assume that
$|xx^{\prime}|\geq|yy^{\prime}|$. Consider the two disks $D$ and $D^{\prime}$
centered at $x$ and $x^{\prime}$, respectively, with radius $|xx^{\prime}|$.
Any line segment crossing $xx^{\prime}$ having their endpoints on the boundary
of $D\cap D^{\prime}$ has length at least $|xx^{\prime}|$. Therefore, either
$y$ or $y^{\prime}$ lies in $D\cap D^{\prime}$. Otherwise,
$|yy^{\prime}|>|xx^{\prime}|$, which makes a contradiction. Therefore,
$x,x^{\prime}$ and $y$ (or $y^{\prime}$) form a cycle in a unit disk graph. ∎

From now on, we always assume that $G$ admits the icf-property. A subset $M$
of $\mathbb{R}^{2}$ is _$r$ -fat_ if there are two disks $D\subset M\subset
D^{\prime}$ and the radius ratio of $D$ and $D^{\prime}$ is $r$. A family of
$r$-fat subsets is called a _similarly-size_ family if the ratio of the
maximum diameter and minimum diameter among subsets is bounded by a constant
$r^{\prime}$. A _map_ $\mathcal{M}$ of $G$ is a partition of a rectangle
containing $V(G)$ into a similarly-sized family of convex subsets (called
cells) each of complexity $O(1)$ satisfying the conditions (M1–M2): For each
cell $M$ of $\mathcal{M}$,

  * •

(M1) $V(G)\cap M$ forms a clique in $G$, and

  * •

(M2) each edge of $G$ intersects $O(1)$ cells.

We assume the _general position assumption_ that no vertex of $V$ is contained
on the boundary of a cell of $\mathcal{M}$, and no two edges of $E$ cross at a
point in $\partial M$. For two cells $M$ and $M^{\prime}$, the _distance_
between $M$ and $M^{\prime}$ is the length of the shortest path between them
in the dual graph of $\mathcal{M}$. We write the distance by
$d(M,M^{\prime})$. For an integer $\ell>0$, a cell $M$ is called an _$\ell$
-neighbor_ of a cell $M^{\prime}$ if $d(M,M^{\prime})\leq\ell$. Each cell has
$O_{\ell}(1)$ $\ell$-neighbors for any integer $\ell>0$ since the cells are
similarly-sized and fat. For a point $v$ in the plane, we use $M_{v}$ to
denote the cell of $\mathcal{M}$ containing $v$. Throughout this paper, we let
$\alpha$ be the maximum number of cells of $\mathcal{M}$ intersected by one
edge of $G$. Since an edge of $G$ has length at most one, $\alpha$ is a
constant.

######  Definition 2 (Clique-weight).

For a graph $G=(V,E)$ with the icf-property and a cell $M$ of $\mathcal{M}$,
the _clique-weight_ of $M$ is defined as $\log(|V\cap M|+1)$.

Suppose a map $\mathcal{M}$ is given. We define the _map sparsifier_ $H$ of
$G$ as follows. See Figure 2. Consider all $\alpha$-neighboring cells of the
cells containing vertices of $G$ of degree at least three. Let $H^{\prime}$ be
the plane graph consisting of all boundary edges of such cells. In addition to
them, we add the edges of $G$ whose both endpoints have degree at most two to
$H^{\prime}$. The vertices of $H^{\prime}$ are called the _base vertices_. It
is possible that more than one base vertices are contained in a single cell,
but the number of base vertices contained in a single cell is $O(1)$. Two
edges of $H^{\prime}$ can cross. In this case, we add such a crossing point as
a vertex of $H^{\prime}$ and split the two edges with respect to the new
vertex. These vertices are called the _cross vertices_. Let $H$ be the
resulting planar graph, and we call it a _map sparsifier_ of $G$ with respect
to $\mathcal{M}$. We can compute a map sparsifier $H$ and its drawing in
polynomial time.

Figure 2: (a) Illustration of $G$ and $\mathcal{M}$. (b) The base vertices are
marked with black boxes, and the cross vertices are marked with red boxes.

######  Lemma 3.

The number of vertices of $H$ is $O(|V(G)|)$. Among them, at most $O(\ell)$
vertices have degree at least three in $H$, where $\ell$ denotes the number of
vertices of $G$ of degree $\geq 3$.

###### Proof.

A vertex of $H$ is either a degree-2 vertex of $G$, a corner of a cell of
$\mathcal{M}$, or a cross vertex. The number of vertices of the first type is
at most $|V(G)|$, and the number of vertices of the second type is $O(\ell)$.
This is because such a vertex is a corner of an $O(1)$-neighboring cell of a
vertex of $G$ of degree at least three. Then we analyze the number of cross
vertices. No two edges from the boundaries of the cells of $\mathcal{P}$
cross. Also, note that no two edges of $G$ whose both endpoints have degree at
most two cross by the icf-property. Therefore, a cross vertex $v$ is a
crossing point between an edge $e$ of $G$ and the boundary of a cell $M$ of
$\mathcal{M}$. Notice that $M$ is an $O(1)$-neighboring cell of a vertex of
degree at least three of $G$, and thus the endpoints of $e$ are also contained
in $O(1)$-neighboring cells of a vertex of degree at least three. Thus there
are $O(\ell)$ edges of $G$ inducing cross vertices of $H$. Since each such
edge intersects $O(1)$ cells, the number of cross edges is $O(\ell)$.

To analyze the number of vertices of degree at least three, observe that a
vertex of the first type has degree two in $H$, and the number of vertices of
the second and third types is $O(\ell)$. Therefore, the lemma holds. ∎

###  3.2 Surface Decomposition and Surface Cut Decomposition.

In this subsection, we introduce the concepts of a _surface decomposition_ and
a _surface cut decomposition_ , which are variants of the branch decomposition
and carving decomposition with certain properties, respectively. A point set
$A$ is _regular closed_ if the closure of the interior of $A$ is $A$ itself.
In this paper, we say a regular closed and interior-connected region $A$ is an
_$s$ -piece_ if $\mathbb{R}^{2}\setminus A$ has $s$ connected components. If
$s=O(1)$, we simply say $A$ a _piece_. Note that a piece is a planar surface,
and this is why we call the following decompositions the _surface_
decomposition and _surface_ cut decomposition. In this case, we call $s$ the
_rank_ of $A$. The boundary of each component of $\mathbb{R}^{2}\setminus A$
is a closed curve. We call such a boundary component a _boundary curve_ of
$A$.777Because of computational issues, a boundary curve of a piece we
consider in this paper will be a polygonal curve of complexity $O(n)$.

######  Lemma 4.

For a piece $A$, the boundary of each connected component of
$\mathbb{R}^{2}\setminus A$ is a closed curve. Moreover, two boundary curves
intersect at most once at a single point.

###### Proof.

For the first statement, $\partial A$ divides the plane into $\textsf{int}(A)$
and the _holes_ of $A$. Here, a hole is a connected component of
$\mathbb{R}^{2}\setminus A$. Note that a hole is a non-empty connected open
set, and thus its boundary is a closed curve. Next, assume $\partial
F_{1}\cap\partial F_{2}$ consists of at least two connected components for two
holes $F_{1}$ and $F_{2}$ of $A$. Then $\partial F_{1}\cup\partial F_{2}$
divides the plane into at least four faces, two of them are contained in
$\textsf{int}(A)$. These two faces must be connected since $A$ is interior-
disjoint, which makes a contradiction. Now assume that $\partial
F_{1}\cap\partial F_{2}$ consists of a single connected component containing
at least two points. That is, $\partial F_{1}\cap\partial F_{2}$ is a curve.
Since $\partial F_{1}\cap\partial F_{2}$ is not contained in $F_{1}$ (and
$F_{2}$), it must be contained in $A$. On the other hand, it is not contained
in the interior of $A$, and thus it is not contained in the closure of $A$
since it is a curve. This contradicts that $A$ is regular-closed. Therefore,
two boundary curves intersect at most once at a single point. ∎

##### Surface decomposition.

A _surface decomposition_ of a plane graph $H$ with vertex weights
$c:V(H)\rightarrow\mathbb{R}^{+}$ is a pair $(T,\mathcal{A})$ where $T$ is a
rooted binary tree, and $\mathcal{A}$ is a mapping that maps a node $t$ of $T$
into a piece $A_{t}$ in the plane satisfying the conditions (A1–A3). For a
node $t$ and two children $t^{\prime},t^{\prime\prime}$ of $t$,

  * •

(A1) $\partial A_{t}$ intersects the planar drawing of $H$ only at its
vertices,

  * •

(A2) $A_{t^{\prime}},A_{t^{\prime\prime}}$ are interior-disjoint and
$A_{t^{\prime}}\cup A_{t^{\prime\prime}}=A_{t}$, and

  * •

(A3) $|V(H)\cap A_{t}|\leq 2$ if $t$ is a leaf node of $T$.

For an illustration, see Figure 3(a–b). The _weight_ of a node $t$ is defined
as the sum of weights of the vertices of $V(H)$ lying on $\partial A_{t}$. The
_weighted width_ of $(T,\mathcal{A})$ is defined as the maximum weight of the
nodes of $T$. We will prove the following theorem in Sections 4 and 5.
theoremannulus For a plane graph $H=(V,E)$ with vertex weight $c(\cdot)$ with
$1\leq c(v)\leq n^{O(1)}$ for all $v\in V$, one can compute a surface
decomposition of weighted width $O(\sqrt{\sum_{v\in V}(c(v))^{2}})$ in
$O(n\log n)$ time, where $n$ denotes the number of vertices of $H$.

##### Surface cut decomposition.

A key idea of our result lies in the introduction of a surface cut
decomposition. Let $G$ be an undirected graph drawn in the plane, which is not
necessarily planar. We recursively decompose the plane into pieces such that
the number of edges of $E$ crossing the boundary of each piece $A$ is small.
Once this is done, the number of all possible cases for the interaction
between the parts of $G$ contained in $\textsf{int}(A)$ and
$\mathbb{R}^{2}\setminus\textsf{int}(A)$ is small, and thus for each possible
case, we can break the problem into two subproblems, one for $\textsf{int}(A)$
and one for $\mathbb{R}^{2}\setminus\textsf{int}(A)$. A _surface cut
decomposition_ , sc-decomposition in short, of $G$ is defined as a pair
$(T,\mathcal{A})$ where $T$ is a rooted binary tree, and $\mathcal{A}$ is a
mapping that maps a node $t$ of $T$ into a piece $A_{t}$ in the plane
satisfying the conditions (C1–C4). Let $\mathcal{M}$ be a given map. For a
node $t$ of $T$ and two children $t^{\prime},t^{\prime\prime}$ and a cell $M$
of $\mathcal{M}$,

  * •

(C1) $V(G)\cap\partial A_{t}=\emptyset$,

  * •

(C2) $A_{t^{\prime}},A_{t^{\prime\prime}}$ are interior-disjoint,
$A_{t^{\prime}}\cup A_{t^{\prime\prime}}=A_{t}$,

  * •

(C3) $V(G)\cap A_{t}$ is contained in the union of at most two cells of
$\mathcal{M}$ for a leaf node $t$ of $T$,

  * •

(C4) there are $O(1)$ leaf nodes of $T$ containing points of $M\cap V(G)$ in
their pieces.

Notice that a main difference between the surface decomposition and the
surface cut decomposition is the condition (C1). For dynamic programming
algorithms, we will define subproblems for the subgraph $G_{t}$ of $G$ induced
by $V\cap A_{t}$. Thus it is sufficient to care about the edges incident to
the vertices in $G_{t}$. Let $\textsf{cut}({t})$ be the set of edges of $G$
with at least one endpoint in $A_{t}$ intersecting $\partial A_{t}$. Notice
that an edge in $\textsf{cut}({t})$ might have both endpoints in $A_{t}$. See
Figure 3(c).

The _clique-weighted width_ of a node $t$ (_with respect to_ $\mathcal{M}$) is
defined as the sum of the clique-weights of the cells of $\mathcal{M}$
containing the endpoints of the edges of $\textsf{cut}({t})$. The _clique-
weighted width_ of an sc-decomposition $(T,\mathcal{A})$ (_with respect to_
$\mathcal{M}$) is defined as the maximum clique-weight of the nodes of $T$. If
we can utilize two geometric tools from Section 3.1, we can compute an sc-
decomposition of small width with respect to $\mathcal{M}$. We will prove the
following theorem and corollary in Section 6.

theoremannuluscarving Let $G$ be a graph admits icf-property. Given a map
$\mathcal{M}$ of $G$, one can compute an sc-decomposition of clique-weighted
width $O(\sqrt{\ell})$ in polynomial time, where $\ell$ is the number of
vertices of degree at least three in $G$.

A unit disk graph admits the icf-property, and a grid that partitions the
plane into axis-parallel squares of diameter one is a map of a unit disk
graph.

Figure 3: (a) A planar surface with rank 2. (b) Two regions $A_{t^{\prime}}$
and $A_{t^{\prime\prime}}$ partition $A_{t}$. (c) The sold edges
($e_{1},e_{2},e_{3}$ and $e_{4}$) are cut edges, and $e_{5}$ is not a cut edge
of $A_{t}$.

corollarycarvingudg Let $G=(V,E)$ be a unit disk graph and $\ell$ be the
number of vertices of degree at least three in $G$. If the geometric
representation of $G$ is given, one can compute an sc-decomposition of clique-
weighted width $O(\sqrt{\ell})$ in polynomial time.

##  4 Weighted Cycle Separator of a Planar Graph

Let $H$ be a triangulated plane graph such that each vertex $v$ has _cycle-
weight_ $c(v)$ and _balance-weight_ $b(v)$ with $1\leq c(v)\leq|H|^{O(1)}$ and
$0\leq b(v)$. For a constant $0<\alpha<1$, a subset $S$ of $V(H)$ is called an
$\alpha$-_balanced separator_ of $H$ if the total balance-weight of each
connected component of $H\setminus S$ is at most $\alpha$ of the total
balance-weight of $H$. Moreover, we call $S$ a cycle separator if $S$ forms a
simple cycle in $H$. In this section, we show that $H$ has a $8/9$-balanced
cycle separator of weight $O\left(\sqrt{\sum_{v\in V(H)}(c(v))^{2}}\right)$.
This generalizes the results presented in [10] and in [21]. More specifically,
Djidjev [10] showed that $H$ has a $2/3$-balanced separator with the desired
cycle-weight, but the separator is not necessarily a cycle. On the other hand,
Har-Peled and Nayyeri [21] showed that $H$ has a $2/3$-balanced cycle
separator of the desired cycle-weight if the cycle-weight and balance-weight
of every vertex are equal to one.

###  4.1 Balanced Cycle Separator

We first compute a $2/3$-balanced cycle separator $S$, which might have a
large cycle-weight. To do this, we use the _level tree_ of $H$ introduced by
Lipton and Tarjan [29]. We choose the root vertex $r$ of $V(H)$ arbitrary. The
_cycle-weight_ of a simple path in $H$ is defined as the sum of the cycle-
weights of all vertices of the path. Then the _level_ of a vertex $p$ of $H$,
denoted by $\textsf{lv}(p)$, is defined as the minimum cycle-weight of an
$r$-$p$ path in $H$. The _level tree_ is defined as the minimum cycle-weight
path tree, that is, each $r$-$p$ path of the tree has minimum cycle-weights
among all $r$-$p$ paths of $H$. We denote the level tree by $\textsf{LT}(H)$.
A balanced cycle separator can be obtained from $\textsf{LT}(H)$ but this
separator might have a large cycle-weight.

######  Lemma 5 ([28]).

Given a triangulated planar graph $H$, we can find a root vertex $r$ of $H$
and an edge $(u,v)\in E(H)$ in $O(|V|)$ time such that

  * •

$\pi_{u}$ and $\pi_{v}$ are edge-disjoint,

  * •

the cycle $S=\pi_{u}\cup\pi_{v}\cup(u,v)$ is a $2/3$-balanced cycle separator
of $H$,

where $\pi_{u}$ is an $r$-$u$ path of the level tree $\textsf{LT}(H)$ of $H$
rooted at $r$.

In the rest of the section, $r,u,v$ and $S$ are the root, two vertices and the
cycle separator specified by Lemma 5, respectively. The maximum level of the
vertices in $S$ is either $\textsf{lv}(u)$ or $\textsf{lv}(v)$. Without loss
of generality, we assume that $\ell_{\textsf{max}}=\textsf{lv}(u)$ is the
maximum level. Also, the minimum level of the vertices in $S$ is the level of
$r$. We let $\ell_{\textsf{min}}=\textsf{lv}(r)=c(r)$. We use
$\textsf{parent}(w)$ to denote the parent node of $w$ in $\textsf{LT}(H)$.

###  4.2 Cycle Separators with Small Cycle-Weight

In this subsection, we construct a sequence of vertex-disjoint cycles each of
which crosses $S$ exactly twice and has small cycle-weight. Let
$c^{*}=\sqrt{\sum_{v\in V(H)}(c(v))^{2}}$ be the desired weight. Note that
$c(v)\leq c^{*}$ for any vertex $v\in H$. If the cycle-weight of $S$ is at
most $8c^{*}$, $S$ is a desired balanced cycle separator. Thus we assume that
the cycle-weight of $S$ is larger than $8c^{*}$. For a face $F$ of $H$, let
$\textsf{lv}(F)$ be the minimum level among the levels of the three vertices
incident to $F$. For a real number $\ell$ in range
$[\ell_{\textsf{min}},\ell_{\textsf{max}}-c^{*}]$, let $U_{\ell}$ be the union
of $\textsf{cl}(F)$ for all faces $F$ with $\textsf{lv}(F)<\ell$. Then
$U_{\ell}$ does not contain $u$ because the level of any face incident to $u$
is at least $\ell_{\textsf{max}}-c^{*}$. We consider the connected component
$F$ of $\mathbb{R}^{2}\setminus U_{\ell}$ containing $u$. Let $C_{\ell}$ be
the boundary curve of $F$. See Figure 4(a–b).

Figure 4: (a) Triangulated planar graph $H$ with the root node $r$. (b)
Illustrates $U_{\ell}$ by the blue region, and $C_{\ell}$ by the thick black
curve. (c) An $r$-$x$ path contained in $\textsf{int}(U_{\ell})$ encounters a
cut vertex $w$.

######  Lemma 6.

For a vertex $w$ in $C_{\ell}$,
$\textsf{lv}(\textsf{parent}(w))<\ell\leq\textsf{lv}(w)$.

###### Proof.

If $\textsf{lv}(w)<\ell$, the levels of all faces $F$ incident to $w$ are
lower than $\ell$. Then $F\subseteq U_{\ell}$ and
$w\in\textsf{int}(U_{\ell})$. This shows the second inequality. Let $F$ be a
face incident to $w$ contained in $U_{\ell}$. Then $F$ is adjacent to a vertex
$x$ with $\textsf{lv}(x)<\ell$, and $(w,x)$ is an edge of $H$. By the
definition of level tree, $\textsf{lv}(\textsf{parent}(w))\leq\textsf{lv}(x)$.
This shows the first inequality. ∎

######  Lemma 7.

The cycle $C_{\ell}$ is a simple cycle, and it intersects with $S$ at most
twice. Moreover, if $\ell+2c^{*}<\ell_{\textsf{max}}$, then $C_{\ell}$
intersects with $S$ exactly twice.

###### Proof.

Assume to the contrary that $C_{\ell}$ is not simple. By definition,
$C_{\ell}$ is the boundary of a connected component of
$\mathbb{R}_{\ell}\setminus U_{\ell}$. Therefore, the only possible case is
that $U_{\ell}$ has a cut vertex $w$. Then $F$ be a face of $H$ incident to
$w$ lying outside of the component of $\textsf{cl}(U_{\ell})\setminus\\{w\\}$
containing $r$. See Figure 4(c). By the definition of $U_{\ell}$, there is a
vertex $x$ incident to $F$ with $\textsf{lv}(x)<\ell$. Consider the $r$-$x$
path in the level tree. The level of a vertex in the path is lower than
$\ell$, and therefore, the path is contained in $\textsf{int}(U_{\ell})$.
Since this path must encounter $w$, and $\ell\leq\textsf{lv}(w)$, $w$ is not a
cut vertex of $C_{\ell}$.

Next we show that $C_{\ell}$ intersects $S$ at most twice. Note that
$C_{\ell}$ never contains $r$ by Lemma 6. If $|C_{\ell}\cap S|\geq 3$, we may
assume that $|C_{\ell}\cap\pi_{u}|\geq 2$. Let $x,y$ be two vertices of
$C_{\ell}\cap\pi_{u}$ with $\textsf{lv}(x)>\textsf{lv}(y)$. Then $y$ is an
ancestor of $x$ in the level tree. Since both $x$ and $y$ does not lie on
$\textsf{int}(U_{\ell})$, their cycle-weights are at least $\ell$. Then
$\ell\leq\textsf{lv}(y)\leq\textsf{lv}(\textsf{parent}(x))<\ell\leq\textsf{lv}(x)$
by Lemma 6, which leads to a contradiction. Finally, consider the case that
$\ell+2c^{*}<\ell_{\textsf{max}}$. The maximum level of vertices in $C_{\ell}$
is at most $\ell+c^{*}<\ell_{\textsf{max}}-c^{*}$ since $c(v)\leq c^{*}$ for
any vertex $v\in V(H)$. Observe that both $\textsf{lv}(v)$ and
$\textsf{lv}(u)$ are at least $\ell_{\textsf{max}}-c^{*}$. More precisely,
$\textsf{lv}(u)=\ell_{\textsf{max}}$ and
$\textsf{lv}(v)\geq\textsf{lv}(u)-c(v)\geq\ell_{\textsf{max}}-c^{*}$.
Therefore, both $\pi_{u}$ and $\pi_{v}$ intersect $C_{\ell}$ at least once. By
combining the previous argument, we conclude that they intersect $C_{\ell}$
exactly once. ∎

We compute a sequence $\mathcal{D}$ of cycles of small cycle-weight as
follows. We divide the interval
$[\ell_{\textsf{min}},\ell_{\textsf{max}}-c^{*}]$ into
$t=\lfloor\frac{\ell_{\textsf{max}}-\ell_{\textsf{min}}}{c^{*}}-1\rfloor$
intervals, $I_{1},\ldots,I_{t}$, such that all intervals but the last one,
have length exactly $c^{*}$. For every odd indices $j\leq t-2$, we pick the
number $\ell_{j}\in I_{j}$ that minimizes the cycle-weight of $C_{\ell_{j}}$.
In this way, we obtain a sequence $\mathcal{D}=\langle
C_{\ell_{1}},C_{\ell_{3}},C_{\ell_{5}}...,C_{\ell_{t^{\prime}}}\rangle$. To
see that $\mathcal{D}$ is not empty, we observe that the cycle-weight of $S$
is $\textsf{lv}(u)+\textsf{lv}(v)-c(r)\leq 2\cdot\textsf{lv}(u)$. Then we have
$8c^{*}\leq 2\cdot\textsf{lv}(u)=2\ell_{\textsf{max}}$, and
$\ell_{\textsf{min}}=c(r)\leq c^{*}$. Therefore, $3\leq t$, and $\mathcal{D}$
is not empty. Since we pick indices $j$ from $j\leq t-2$, we have
$\ell_{j}+2c^{*}<\ell_{\textsf{max}}$. We summary these facts into the
following:

######  Observation 8.

$\mathcal{D}$ is not empty, and each cycle of $\mathcal{D}$ intersects with
$S$ exactly twice.

We show that $\mathcal{D}$ consists of vertex-disjoint cycles with small
cycle-weight.

######  Lemma 9.

The cycles in $\mathcal{D}$ are vertex-disjoint.

###### Proof.

Let $C_{\ell_{j}}$ and $C_{\ell_{j+2}}$ be two consecutive cycles of
$\mathcal{D}$. By definition, $\ell_{j+2}-\ell_{j}$ is in range
$[c^{*},3c^{*}]$. For a vertex $v\in C_{\ell_{j}}$,
$\textsf{lv}(\textsf{parent}(v))<\ell_{j}$ by Lemma 6. In other words,
$\textsf{lv}(v)<\ell_{j}+c(v)$. Then $v$ is contained in
$\textsf{int}(U_{\ell_{j}+c(v)})$. Since $\ell_{j}+c(v)\leq\ell_{j+2}$, $v$ is
contained in the interior of $U_{\ell_{j+2}}$, and thus it does not lie on
$C_{\ell_{j+2}}$. ∎

######  Lemma 10.

Each cycle of $\mathcal{D}$ has weight at most $c^{*}$.

###### Proof.

We show the stronger statement that the sum of cycle-weights of all cycles in
$\mathcal{D}$ is at most $c^{*}$. Let $c(C_{\ell})$ be the cycle-weight of
$C_{\ell}$, which is the sum of the cycle-weights of all vertices of
$C_{\ell}$. For every index $j$ less than $t$, we have

$c(C_{\ell_{j}})\leq\frac{1}{c^{*}}\int_{\ell\in I_{j}}c(C_{\ell}),\text{ and
thus }\sum_{1\leq j\leq
t}{c(C_{\ell_{j}})}\leq\frac{1}{c^{*}}\int_{\ell\in[\ell_{\textsf{min}},\ell_{\textsf{max}}-c^{*}]}c(C_{\ell}).$

For a vertex $w\in C_{\ell}$, $\textsf{lv}(w)\geq\ell$ and
$\textsf{lv}(\textsf{parent}(w))<\ell$. Since
$\textsf{lv}(\textsf{parent}(w))+c(w)=\textsf{lv}(w)$,
$\textsf{lv}(w)\in[\ell,\ell+c(w)]$. Then each $w$ contributes at most
$(c(w))^{2}$ to the integral of $c(C_{\ell})$. Thus, the sum of all
$c(C_{\ell_{j}})$ for $j\leq t$ is at most $c^{*}$. ∎

We can compute $\mathcal{D}$ in linear time as follows. Starting from
$\ell_{\textsf{min}}$, imagine that we increase $\ell$ continuously. Then
$c(C_{\ell})$ is a step function which maps
$\ell\in[\ell_{\textsf{min}},\ell_{\textsf{max}}]$ to $c(C_{\ell})$. This
function has $|H|$ different values. Therefore, we can compute the weight of
$C_{\ell}$ for all $\ell$ in $O(|H|)$ time in total by sweeping the range
$[\ell_{\textsf{min}},\ell_{\textsf{max}}]$.

Figure 5: (a) A balanced cycle separator $S$ has cycle-weight larger than
$8c^{*}$. The gray region $R$ is $C_{2}^{r}\setminus C_{1}^{r}$ for two
consecutive cycles $C_{1},C_{2}$ of $\mathcal{D}$. (b) Two regions $R_{1}$ and
$R_{2}$, and the red paths $\pi=S\cap R$ partition $R$. (c) If
$b(\pi)<\frac{1}{9}b(H)$ and $b(R_{1})\geq b(R_{2})$, $S_{3}$ is a
$8/9$-balanced cycle separator.

###  4.3 Balanced Cycle Separator with Small Cycle-Weight

In this subsection, we compute a simple balanced cycle separator of small
_cycle-weight_ using $\mathcal{D}$ similar to the algorithm of Har-Peled and
Nayyeri [21]. For a subset $A$ of $\mathbb{R}^{2}$, we use $b(A)$ to denote
the total balance-weight of the vertices of $H$ contained in $A$. By a slight
abuse of notation, for a subgraph $H^{\prime}$ of $H$, we let $b(H^{\prime})$
be the total balance-weight of the vertices of $H^{\prime}$.

Suppose there is a vertex $w$ with $b(w)\geq b(H)/9$. Then we consider a face
$F$ incident to $w$. Three vertices incident to $F$ forms a desired separator
because the sum of cycle-weights of three vertices is at most $3c^{*}$. From
now on, we assume that all vertices $w$ have the balance-weights $b(w)$ with
$b(w)<b(H)/9$. We insert two cycles into $\mathcal{D}$: a trivial cycle
consisting of the root $r$ of $\textsf{LT}(H)$ in the front, and a trivial
cycle consisting of $u$ of $\textsf{LT}(H)$ in the last. For a cycle $C$ in
$\mathcal{D}$, no region of $\mathbb{R}^{2}\setminus C$ contains both $u$ and
$r$. Let $C^{u}$ and $C^{r}$ be two regions of $\mathbb{R}^{2}\setminus C$
contain $u$ and $r$, respectively. If such a region $C^{r}$ (and $C^{u}$) does
not exists, we set $C^{r}$ (and $C^{u}$) as the empty set.

If there is a cycle in $\mathcal{D}$ that is a $2/3$-balanced separator, we
are done due to the Lemma 10. Otherwise, we find two consecutive cycles
$C_{1}$ and $C_{2}$ in $\mathcal{D}$ such that $b(C_{1}^{r})<\frac{1}{3}b(H)$
and $b(C_{2}^{r})>\frac{2}{3}b(H)$. This is always possible because two
trivial cycles have balance weight at most $\frac{1}{9}b(H)$. Let $S$ be the
cycle specified in Lemma 5. We also specify some subsets and paths as follows.
Let $R=C_{2}^{r}\setminus C_{1}^{r}$, $R_{1}=R\cap S^{\textsf{in}}$,
$R_{2}=R\cap S^{\textsf{ex}}$, $R_{3}=R_{1}\cup C_{1}^{r}$, and
$R_{4}=R_{2}\cup C_{1}^{r}$. See Figure 5. Let $\pi=S\cap R$ be the subset of
the cycle-separator $S$. Since $C_{1}$ and $C_{2}$ are consecutive cycles in
$\mathcal{D}$, the total cycle-weights of the vertices of $\pi$ is at most
$4c^{*}$. The boundary $\partial R_{i}$ consists of a single cycle, namely
$S_{i}$. Then the total cycle-weights of the vertices in $S_{i}$ is at most
$10c^{*}=O(c^{*})$ due to Lemma 10.

We claim that one of $S_{i}$’s is a $8/9$-balanced cycle separator of $H$.
Since $S$ is a $2/3$-balanced separator, $b(R_{1})$, $b(R_{2})$ is at most
$\frac{2}{3}b(H)$. For the first case that $b(R_{i})\geq\frac{1}{3}b(H)$ for
$i\in\\{1,2\\}$, $S_{i}$ is a $2/3$-balanced cycle separator. For the second
case that total balance-weights of vertices in $\pi$ is at least
$\frac{1}{9}b(H)$, $S_{1}$ is a $8/9$-balanced cycle separator because all
vertices of $\pi$ are contained in $S_{1}$. The remaining case is that
$b(R_{1}),b(R_{2})<\frac{1}{3}b(H)$ and $b(\pi)<\frac{1}{9}b(H)$. Since
$\\{R_{1},\pi,R_{2}\\}$ forms a partition of $R$, we have

$b(R_{1})+b(R_{2})=b(R)\setminus
b(\pi)\geq\frac{1}{3}b(H)-\frac{1}{9}b(H)=\frac{2}{9}b(H).$

Then we can pick $i\in\\{1,2\\}$ so that $b(R_{i})\geq\frac{1}{9}b(H)$. Then

$\frac{1}{9}b(H)\leq
b(R_{i})<b(R_{i+2})=b(R_{i})+b(C_{1}^{r})<\frac{2}{3}b(H).$

Therefore, $S_{i+2}$ is a desired separator.

######  Lemma 11.

For a triangulated plane graph $H$ with cycle-weight $c(\cdot)$ and balance-
weight $b(\cdot)$ satisfying $1\leq c(v)\leq|H|^{O(1)}$ and $0\leq b(v)$, we
can compute a $(8/9)$-balanced cycle separator of weight
$10\cdot\sqrt{\sum_{v\in V(H)}(c(v))^{2}}$ in $O(|H|)$ time.

##  5 Surface Decomposition of Small Weighed Width

In this section, we show that a plane graph $H$ with cycle-weights
$c:V(H)\rightarrow\mathbb{R}$ with $1\leq c(v)\leq|H|^{O(1)}$ admits a surface
decomposition of weighted width
$O(c_{\textsf{sos}}({H})+c_{\textsf{max}}(H)^{4})$. For most of applications,
the first term in the weighted width dominates the second term. Recall that a
surface decomposition of $H$ is a recursive decomposition of $\mathbb{R}^{2}$
into pieces such that all pieces in the lowest level have at most two vertices
of $G$, and the boundary of no piece is crossed by an edge of $H$. We
represent it as a pair $(T,\mathcal{A})$ where $T$ is a rooted binary tree,
and $\mathcal{A}$ is a mapping that maps a node $t$ of $T$ into a piece
$A_{t}$. The _weight_ of a node $t$ is defined as the sum of weights of the
vertices in $V(H)\cap\partial A_{t}$. The _weighted width_ of
$(T,\mathcal{A})$ is defined as the maximum weight of the nodes of $T$.

We first give a sketch of our algorithm. Initially, we have the tree
consisting of a single node $t$ associated with $A_{t}=\mathbb{R}^{2}$ and
$H_{t}=H$. At each iteration, for a leaf node $t$, we compute a balanced
simple cycle separator $S_{t}$ using Lemma 11 by assigning balance-weights to
the vertices of $H_{t}$ properly. Let $\gamma_{t}$ be a Jordan curve
intersecting $H_{t}$ only at vertices of $S_{t}$. Then $A_{t}$ is partitioned
into connected components by $\gamma_{t}$. We add a child $t^{\prime}$ of $t$
each corresponding to each connected component. That is, we let
$A_{t^{\prime}}$ be the closure of a connected component of
$A_{t}-\gamma_{t}$, and $H_{t^{\prime}}$ be the subgraph of $H_{t}$ induced by
$A_{t^{\prime}}\cap V(H)$. We do this until $H_{t}$ has at most
$\max\\{(c_{\textsf{max}}(H))^{3},10^{24}\\}$ vertices. When we reach a node
$t$ such that $H_{t}$ has at most
$\max\\{(c_{\textsf{max}}(H))^{3},10^{24}\\}$ vertices, we can compute the
descendants of $t$ in a straightforward way such that the weight of the
resulting surface decomposition increases by
$|V(H_{t})|{c_{\textsf{max}}(H_{t})}\leq O({(c_{\textsf{max}}(H_{t}))^{4}})$.

There are three issues: First, $H$ is not necessarily triangulated, so we
cannot directly apply Lemma 11. Second, although a single balanced cycle
separator of Lemma 11 has complexity $c_{\textsf{sos}}({H_{t}})$, $H_{t}$
might have $\Theta(d\cdot c_{\textsf{sos}}({H_{t}}))$ vertices lying on the
boundary of $A_{t}$, and $A_{t}$ might have rank $d$ in the worst case for a
node $t$ constructed in the $d$th recursion step for $d=\omega(1)$. For the
former case, the weighted width of the surface decomposition computed by this
approach can exceed the desired value, and for the latter case, $A_{t}$
violates the conditions for being a piece. Third, the number of components of
$A_{t}-\gamma_{t}$ can be more than two. In this case, the previous approach
creates more than two children, which violates the conditions for the surface
decomposition.

The first issue can be handled by triangulating $H$ and assigning weights
carefully to the new vertices. The second issue can be handled by assigning
balance-weights so that, in each recursion step, the complexity of $S_{t}$
decreases by a constant factor, or the rank of $A_{t}$ decreases by a constant
factor. Then the third issue can be handled by partitioning the components
into exactly two groups, and then adding two children for the two groups. We
introduce the tools for dealing with the first two issues in Section 5.1 and
show how to handle all the issues to compute a surface decomposition of
desired weighted width in Section 5.2.

###  5.1 Vertex and Hole Separators for a Piece

Let $H_{t}$ be the subgraph of $H$ induced by $A_{t}\cap V(H)$ with
$|V(H_{t})|\geq\max\\{(c_{\textsf{max}}(H_{t}))^{3},10^{24}\\}$. In this
subsection, we introduce two types of separators of $H_{t}$ called a _vertex
separator_ and a _hole separator_. A _vertex separator_ $\gamma_{\textsf{v}}$
is a noose of $H_{t}$ such that the total cycle-weight of the vertices
contained in the _closure_ of each connected component of
$\textsf{int}(A_{t})-\gamma_{\textsf{v}}$ is at most $9/10$ of the total
cycle-weight of $H_{t}$. A _hole separator_ $\gamma_{\textsf{h}}$ is a noose
of $H_{t}$ such that the rank of the closure of each connected component of
$\textsf{int}(A_{t})-\gamma_{\textsf{h}}$ is at most $9/10$ of the rank of
$A_{t}$. This is well-defined due to the following lemma. We can compute them
by setting balanced-weights $b(\cdot)$ of the vertices of $H_{t}$ carefully
and then using the balanced cycle separator described in Section 4.

######  Lemma 12.

For a closed curve $\gamma$ intersecting a piece $A$, the closure of each
connected component of $\textsf{int}(A)-\gamma$ is also a piece with rank at
most one plus the rank of $A$. Moreover, the union of the closures of the
connected components of $\textsf{int}(A)-\gamma$ is $A$ itself.

###### Proof.

For the first claim, let $F$ be a connected component of
$\textsf{int}(A)-\gamma$. Since $F$ is an open set, $\textsf{cl}(F)$ is
interior-connected. Also, since $F$ is a connected open point set in the
plane, $\textsf{int}(\textsf{cl}(F))=F$, and thus $\textsf{cl}(F)$ is regular
closed. Finally, the rank of $\textsf{cl}(F)$ is at most one plus the rank of
$A$. To see this, we call a connected component of $\mathbb{R}^{2}\setminus A$
a _hole_ of $A$. The rank of $A$ is the number of holes of $A$ by definition.
A hole of $A$ is contained in a hole of $F$. Also, one of the regions cut by
$\gamma$, say $X$, is contained in a hole of $F$. On the other hand, each hole
of $F$ intersects either a hole of $A$ or $X$. Therefore, $\textsf{cl}(F)$ is
a piece, and its rank is at most one plus the rank of $A$.

For the second claim, let $F_{1},\ldots,F_{\ell}$ be the connected components
of $\textsf{int}(A)-\gamma$. Clearly,
$\textsf{cl}(F_{1})\cup\ldots\cup\textsf{cl}(F_{\ell})\subseteq A$ because
$F_{1},\ldots,F_{\ell}\subseteq A$ and $A$ is closed. For the other direction,
let $p$ be a point of $A$. If $p$ lies on $\gamma$, there is an index $i$ such
that $F_{i}$ is incident to $\gamma$ at $p$, and thus $p$ is contained in
$\textsf{cl}(F_{i})$. If $p$ is contained in $\textsf{int}(A)-\gamma$, it is
contained in $F_{1}\cup\ldots\cup F_{\ell}$, and thus it is contained in
$\textsf{cl}(F_{1})\cup\ldots\cup\textsf{cl}(F_{\ell})$. If $p$ is contained
in $\partial A-\gamma$, there is a small disk centered at $p$ intersecting
$\textsf{int}(A)-\gamma$ at a point, say $q$. Then there is an index $i$ such
that $F_{i}$ contains $q$, and moreover, $\textsf{cl}(F_{i})$ contains $p$.
For any case, $p$ is contained in
$\textsf{cl}(F_{1})\cup\ldots\cup\textsf{cl}(F_{\ell})$, and thus the second
claim also holds. ∎

Figure 6: (a) Illustrates the construction of $H_{\textsf{tr}}$. Auxiliary
vertices are denoted by blue points. (b) Illustrates a balanced cycle
separator (red cycle). (c) The balanced cycle separator subdivides the piece
into two smaller pieces.

We first triangulate $H_{t}$ by adding an auxiliary vertex $v^{\prime}$ in the
interior of each face of $H_{t}$, and connecting it with each vertex incident
to the face by an edge.888Here, an edge is not necessarily drawn as a single
segment. It is not difficult to see that we can triangulate each face $F$ of
$H_{t}$ by drawing the edges as polygonal curves of total complexity
polynomial in the complexity of $F$. Let $H_{\textsf{tr}}$ be the
triangulation of $H_{t}$. Since the auxiliary vertices do not have cycle-
weights yet, we set the cycle-weight $c(v^{\prime})$ as one. Note that
$c_{\textsf{sum}}(H_{\textsf{tr}})\leq 3c_{\textsf{sum}}(H_{\textsf{t}})$ and
$c_{\textsf{sos}}({H_{\textsf{tr}}})\leq\sqrt{3}c_{\textsf{sos}}({H_{\textsf{t}}})$,
because the number of faces of $H$ is at most $2|V(H)|$ due to Euler’s
formula.

##### Vertex separator.

To obtain a vertex separator, we set $b(v)$ to $c(v)$ for every vertex $v$ of
$H_{\textsf{tr}}$ which comes from $H_{t}$, and we set $b(v^{\prime})$ to zero
for every auxiliary vertex $v^{\prime}$ of $H_{\textsf{tr}}$. We compute a
cycle separator $S$ of cycle-weight $10\cdot
c_{\textsf{sos}}({H_{\textsf{tr}}})\leq 10\sqrt{3}\cdot
c_{\textsf{sos}}({H_{t}})$ of $H_{\textsf{tr}}$ using Lemma 11. Let
$S_{\textsf{v}}$ be the sequence of vertices of $S$ excluding the auxiliary
vertices. Then $S_{\textsf{v}}$ is a balanced separator of $H_{t}$ by
construction. Moreover, we can draw a noose $\gamma_{\textsf{v}}$ of $H_{t}$
intersecting all vertices of $S_{\textsf{v}}$. See Figure 6(c).

Notice that $\gamma_{\textsf{v}}$ partitions $A_{t}$ into at least two
regions. Let $H^{\prime}$ be the subgraph of $H_{t}$ induced by the vertices
in the _closure_ of a connected component of
$\textsf{int}(A_{t})-\gamma_{\textsf{v}}$. By Lemma 11, the sum of $b(v)$ for
all vertices in $H^{\prime}$ not lying on $\gamma_{\textsf{v}}$ is at most
$(8/9)\cdot c_{\textsf{sum}}(H_{t})$ as the sum of $b(v)$ for all vertices
$v\in H_{\textsf{tr}}$ is exactly $c_{\textsf{sum}}(H_{t})$ by the choice of
$b(\cdot)$. However, the vertices of $H^{\prime}$ lying on
$\gamma_{\textsf{v}}$ also have cycle-weight, but they are not considered in
Lemma 11. But the total cycle-weight of such vertices is sufficiently small.
Specifically, the cycle-weight of $\gamma_{\textsf{v}}$ is at most
$10\sqrt{3}c_{\textsf{sos}}({H_{t}})\leq
10\sqrt{3}\cdot\sqrt{c_{\textsf{max}}(H_{t})^{2}\cdot|H_{t}|}=10\sqrt{3}|H_{t}|^{5/6}$
by the assumption. Moreover, we have $|H_{t}|^{5/6}\leq
10^{-4}\cdot|H_{t}|\leq 10^{-4}\cdot(c_{\textsf{sum}}(H_{t}))$ by the
assumption that $c(\cdot)\geq 1$ and $|H_{t}|\geq 10^{24}$. Therefore, the
total cycle-weight of $H^{\prime}$ is at most $(9/10)\cdot
c_{\textsf{sum}}(H_{t})$, and thus $\gamma_{\textsf{v}}$ is a vertex separator
of $H_{t}$.

##### Hole separator.

To obtain a hole separator, we set $b(v)=0$ for every vertex $v$ of
$H_{\textsf{tr}}$ which comes from $H_{t}$. A face of $H_{t}$ is either
contained in $A_{t}$, or contains a connected component of
$\mathbb{R}^{2}-A_{t}$. We set $b(v^{\prime})=0$ for a vertex $v^{\prime}$
corresponding to a face of $H_{t}$ of the former type, and set
$b(v^{\prime})=1$ for a vertex $v^{\prime}$ corresponding to a face of $H_{t}$
of the latter type. Since the number of faces of the latter type is exactly
the rank of $A_{t}$, the total balance-weight of $H_{\textsf{tr}}$ is equal to
the rank of $A_{t}$. Then we compute a balanced cycle separator of weight
$O(c_{\textsf{sos}}({H_{\textsf{tr}}}))$ of $H_{\textsf{tr}}$. As we did for a
vertex separator, we can obtain a balanced separator $S_{\textsf{h}}$ of
$H_{t}$ and a noose $\gamma_{\textsf{h}}$ intersecting the vertices of
$S_{\textsf{h}}$. By construction, the rank of the closure of each connected
region in $\textsf{int}(A_{t})-\gamma_{\textsf{h}}$ is at most $8/9$ of the
rank of $A_{t}$ plus one, and thus $\gamma_{\textsf{h}}$ is a hole separator.

######  Lemma 13.

Let $H$ be a planar graph with cycle-weight $c$ drawn in a piece with $|H|\geq
10^{24}$ and $1\leq c(v)\leq{|H|}^{1/3}$ for all vertices $v\in V(H)$. Then we
can compute a vertex separator and a hole separator of weight
$O(\sqrt{\sum_{v\in V(H)}(c(v))^{2}})$ in $O(|H|)$ time.

##### Remark.

In our application of vertex and hole separators in Section 6, there might be
_forbidden polygonal curves_. A forbidden polygonal curve is a polygonal curve
which is not a part of the drawing of $H$, but intersects $H$ only at a single
vertex of $H$. It is not difficult to see that we can construct a vertex and
hole separator not intersecting any forbidden polygonal curves (except for
their intersection with $V(H)$) without increasing the weight of the
separators.

###  5.2 Recursive Construction

In this subsection, we give an $O(|H|\log|H|)$-time algorithm that computes a
surface decomposition $(T,\mathcal{A})$ of $H$ of weighted width
$O(c_{\textsf{sos}}({H})+(c_{\textsf{max}}(H))^{4})$. As mentioned before, the
algorithm starts from the tree $T$ of a single node $t$ with
$A_{t}=\mathbb{R}^{2}$ and $H_{t}=H$. For each leaf node $t$, we subdivide
$A_{t}$ further if $A_{t}$ contains more than one edge of $H$. If $H_{t}$ has
more than $\max\\{(c_{\text{max}}(H))^{4},10^{24}\\}$ vertices, we do the
following. If the rank of $A_{t}$ exceeds some constant, say $100$, we compute
a hole separator $\gamma$ of $H_{t}$. Otherwise, we compute a vertex separator
$\gamma$ of $H_{t}$. We denote the set of the closures of the connected
components of $\textsf{int}(A_{t})-\gamma$ by $\mathcal{A}_{\gamma}$. See
Figure 7(a). Each region of $\mathcal{A}_{\gamma}$ is a piece as shown in
Lemma 12, but the size of $\mathcal{A}_{\gamma}$ can be more than two. One
might want to add $|\mathcal{A}_{\gamma}|$ children of $t$ and assign each
piece of $\mathcal{A}_{\gamma}$ to each child. However, each internal node of
$T$ for a surface decomposition $(T,\mathcal{A})$ should have exactly two
children by definition. Thus instead of creating $|\mathcal{A}_{\gamma}|$
children of $t$, we construct a binary tree rooted at $t$ whose leaf edges
correspond to the pieces of $\mathcal{A}_{\gamma}$. Here, since a piece must
be regular closed and interior-connected, we have to construct such a binary
tree carefully.

For this purpose, consider the adjacency graph of $\mathcal{A}_{\gamma}$ where
the vertices represents the pieces of $\mathcal{A}_{\gamma}$ and two vertices
are connected by an edge if their respective pieces are adjacent. See Figure
7(b). Every connected graph has a vertex whose removal does not disconnect the
graph: choose a leaf node of a DFS tree of the graph. We compute a DFS tree of
the adjacency graph and choose a leaf node of the tree. Let $A$ be the piece
corresponding to the chosen leaf node. Then $A$ and the union $A^{\prime}$ of
the pieces of $\mathcal{A}_{\gamma}-\\{A\\}$ are also pieces. We create two
children of $t$, say $t_{1}$ and $t_{2}$, and then let $A_{t_{1}}=A$ and
$A_{t_{2}}=A^{\prime}$, respectively. Then we update the DFS tree by removing
the node corresponding to $A$, and choose a leaf node again. We add two
children of $t_{2}$ and assign the pieces accordingly. We do this repeatedly
until we have a binary tree of $t$ whose leaf nodes have the pieces of
$\mathcal{A}_{\gamma}$. After computing the binary tree, we let
$H_{t^{\prime}}=H_{t}[V(H_{t})\cap A_{t^{\prime}}]$ for each node $t^{\prime}$
of the binary tree.

If the number of vertices of $H_{t}$ is at most
$\max\\{(c_{\textsf{max}}(H))^{3},10^{24}\\}$, we can compute the descendants
of $t$ in a straightforward way so that the weight of the surface
decomposition increases by $(c_{\textsf{max}}(H))^{4}+O(1)$, and maintain the
rank of the piece as a constant. In particular, we compute an arbitrary noose
that divides the piece into two pieces such that the number of vertices of
$V(H_{t})$ decreases by at least one. Whenever the rank of the piece exceeds a
certain constant, we compute a hole separator that reduces the rank of the
piece by a constant fraction, and then compute the descendants as we did for
the case that $H_{t}$ has more than
$\max\\{(c_{\textsf{max}}(H))^{3},10^{24}\\}$ vertices. By repeating this
until all pieces in the leaf nodes have exactly one edge of $H$, we can obtain
$(T,\mathcal{A})$ satisfying the conditions (A1–A3) for being a surface
decomposition of $H$. Thus in the following, we show that the weighted width
of $(T,\mathcal{A})$ is $O(c_{\textsf{sos}}({H})+(c_{\textsf{max}}(H))^{4})$,
and the surface decomposition can be computed in $O(|H|\log|H|)$ time.

Figure 7: (a) The boundary of the red piece $A_{t}$ intersects $H$ only at the
vertices. The red dotted curve denotes the separator $S$. (b) First we
separate $A_{t_{1}}$ and $(A_{t_{2}}\cup A_{t_{3}})$, and then again separate
$A_{t_{2}}$ and $A_{t_{3}}$. The boundaries of pieces again intersect $H$ only
at the vertices.

######  Lemma 14.

We can compute $(T,\mathcal{A})$ in $O(|H|\log|H|)$ time if
$c_{\textsf{max}}(H)\leq|H|^{O(1)}$.

###### Proof.

Consider the recursion tree of our recursive algorithm. For each recursion
step for handling a node $t$, we first compute a separator of $H_{t}$ in
$O(|H_{t}|)$ time. Then the separator splits $A_{t}$ into smaller pieces, and
we compute a DFS tree of the adjacency graph of the smaller pieces in
$O(|H_{t}|)$ time. For all recursive calls in the same recursion level, the
total complexity of $H_{t}$’s is $O(|H|)$. Therefore, the recursive calls in
one recursion level take $O(|H|)$ time.

Then we claim that the recursion depth is $O(\log|H|)$, which leads to the
total time complexity of $O(|H|\log|H|)$. Consider a longest path in the
recursion tree. For each recursive call in this path, we compute either a
vertex separator or a hole separator: If the rank of $A_{t}$ is larger than
100, we compute a hole separator, and otherwise, we compute a vertex
separator. If we compute a vertex separator at some level, the total cycle-
weights of $H_{t^{\prime}}$ in the next recursive call (for a node
$t^{\prime}$ of $T$) in this path decreases by a constant factor. Note that
once we use a hole separator at some level, the rank of $A_{t^{\prime}}$
decreases to at most $\frac{8}{9}\cdot 100+1\leq 90$, and thus no two
consecutive calls in the path use both hole separators. That is, the total
cycle-weight of $H_{t}$ decreases by a constant factor for every second
recursive call in the path. Therefore, the height of the recursion tree is
$O(\log c_{\textsf{max}}(H))=O(\log|H|)$. ∎

######  Lemma 15.

$(T,\mathcal{A})$ has weighted width $O(\sqrt{\sum_{v\in V(H)}(c(v))^{2}})$.

###### Proof.

Recall that the weight of a node $t$ of $T$ is the sum of the cycle-weights of
$\textsf{bd}({t})$, where $\textsf{bd}({t})$ is the set of vertices of $H_{t}$
contained in $\partial A_{t}$. We again consider the recursion tree of our
recursive algorithm. By construction, $\partial A_{t}$ is contained in the
union of the hole and vertex separators constructed for the ancestors of the
recursion tree of the recursive call that constructs $t$. As shown in the
second paragraph of the proof of Lemma 14, the total-cycle weight of $H_{t}$
decreases by a constant fraction for every second recursive call in a path in
the recursion tree. That is, the cycle-weight of $H_{t}$ is (almost)
geometrically decreasing along the path. Therefore, the total weight of the
hole and vertex separators constructed for the ancestors is bounded by the
weight of the hole or vertex separator constructed for the root of the
recursion tree, which is $O(\sqrt{\sum_{v\in V(H)}(c(v))^{2}})$. ∎

Theorem 3.2 summarizes this section. *

##  6 Surface Cut Decomposition of a Graph with ICF-Property

Let $G=(V,E)$ be a graph given with its straight-line drawing in the plane
that admits the icf-property. In this section, we present a polynomial-time
algorithm that computes an sc-decomposition of clique-weighted width
$O(\sqrt{\ell})$ with respect to $\mathcal{M}$ assuming that a map
$\mathcal{M}$ of $G$ is given, where $\ell$ is the number of vertices of
degree at least three in $G$. Let $H$ be a map sparsifier of $G$ with respect
to $\mathcal{M}$.

A key idea is to use a surface decomposition $(T,{\mathcal{A}})$ of $H$. For
each piece $A_{t}$ of ${\mathcal{A}}$, the boundary curves of $A_{t}$
intersect $H$ only at vertices of $H$. We slightly perturb the boundary curves
locally so that no piece contains a vertex of $G$ on its boundary. Then we can
show that the resulting pair, say $(T,\bar{\mathcal{A}})$, is an sc-
decomposition of $G$. By defining the weights of the vertices of $H$
carefully, we can show that the clique-weighted width of the sc-decomposition
of $G$ is at most the weight of $(T,{\mathcal{A}})$. However, the sum of the
squared weights of the vertices of ${H}$ can be $\Theta(n)$ in the worst case,
and thus the weight of $(T,{\mathcal{A}})$ is $O(\sqrt{n})$. To get an sc-
decomposition of $H$ of weight $O(\sqrt{\ell})$, we consider the minor $H_{3}$
of $H$ obtained by contracting each maximal path consisting of degree-1 and
degree-2 vertices and then by removing all degree-1 vertices in the resulting
graph. Then we apply the algorithm in Section 5 to $H_{3}$ to obtain a surface
decomposition of $H_{3}$ of weight $O(\sqrt{\ell})$. Then using it, we
reconstruct a surface decomposition of $H$ of weight $O(\sqrt{\ell})$ as
mentioned earlier.

Although this basic idea is simple, there are several technical issues to
implement the idea and prove the correctness of our algorithm. In Section 6.1,
we define the weight of the vertices of $H$ and construct the minor $H_{3}$ of
$H$. We analyze the sum of the squared weights of the vertices of $H_{3}$, and
this gives an upper bound on the surface decomposition of $H_{3}$ constructed
from Section 5. In Section 6.2, we construct a surface decomposition
$(T,{\mathcal{A}})$ of $H$ using the surface decomposition of $H_{3}$, and
analyze its width. In Section 6.3, we modify $(T,{\mathcal{A}})$ to construct
an sc-decomposition $(T,\bar{\mathcal{A}})$ of $G$ by perturbing the boundary
curves of the pieces of $\mathcal{A}$.

###  6.1 Step 1: Construction of $H_{3}$

We first define the weight of the vertices of $H$ so that the clique-weighted
width of the sc-decomposition of $G$ constructed from a surface decomposition
$(T,{\mathcal{A}})$ of $H$ is at most the weight of $(T,{\mathcal{A}})$. For
each cell $M$ of $\mathcal{M}$, we define the weight $c_{H}(v)$ of a vertex
$v$ contained in $M$ as the sum of the clique-weights of all
$\alpha$-neighboring cells of $M$ in $\mathcal{M}$. That is,
$c_{H}(v)=1+\sum\log(1+|V(G)\cap M^{\prime}|)$ where in the summation, we take
all $\alpha$-neighboring cells $M^{\prime}$ of $M$ in $\mathcal{M}$. Recall
that a cell $M^{\prime}$ is an $r^{\prime}$-neighboring cell of $M$ if a
shortest path between $M$ and $M^{\prime}$ has length at most $r^{\prime}$ in
the dual graph of $\mathcal{M}$. By the definition of a map, $M$ has
$O_{r^{\prime}}(1)$ $r^{\prime}$-neighboring cells in $\mathcal{M}$.

To compute $H_{3}$ from $H$, we compute all maximal paths of $H$ whose
internal vertices have degree exactly two. Among them, we remove all paths one
of whose endpoints has degree one in $H$ (excluding the other endpoint having
degree larger than two). For the other paths, we contract them into single
edges (remove all internal vertices and connect the two endpoints by an edge.)
The resulting graph is denoted by $H_{3}$. Note that $H_{3}$ might have a
vertex of degree less than three, but such a vertex has degree at least three
in $H$. To apply the notion of the surface decomposition, we draw $H_{3}$ in
the plane as in the drawing of $H$: the drawing of $H_{3}$ is a subdrawing of
the drawing of $H$. Some points in the drawing considered as vertices in $H$
are not considered as vertices of $H_{3}$, and some polygonal curve in the
drawing of $H$ is removed in $H_{3}$ if its endpoint has degree one in $H$. We
compute a surface decomposition $(T,{\mathcal{A}})$ of $H_{3}$ using Theorem
3.2. The decomposition has width $O(\sqrt{\ell})$ by Lemma 6.1.

lemmasumcost We have $c_{\textsf{max}}(H_{3})\leq
c_{\textsf{max}}(H)=O(\log\ell)$ and
$c_{\textsf{sos}}({H_{3}})=O(\sqrt{\ell})$.

###### Proof.

Let $v$ be a vertex of $H$ contained in a cell $M_{v}$ of $\mathcal{M}$. Its
weight $c_{H}(v)$ is the total clique-weight of $O(1)$-neighboring cells of
$M_{v}$ in $\mathcal{M}$. The number of such cells is $O(1)$ due to the
definition of the map. For the first statement, since $V(H_{3})$ is a subset
of $V(H)$, the inequality holds immediately. For an $O(1)$-neighboring cell
$M$ of $M_{v}$, if $|M\cap V(G)|\leq 3$, it contributes $O(1)$ to $c_{H}(v)$.
If $|M\cap V(G)|>3$, all vertices of $G$ contained in $M$ have degree at least
three in $G$. Therefore, such a cell contributes $\log(1+|V(G)\cap
M|)=O(\log\ell)$ to $c_{H}(v)$. Therefore, $c_{H}(v)=O(\log\ell)$, and thus
$c_{\textsf{max}}(H)=O(\log\ell)$.

For the second statement, observe the number of vertices of $H_{3}$ is
$O(\ell)$ by Lemma 3 since all vertices of $H_{3}$ have degree at least three
in $H$. Also, we have $c(v)^{2}=(1+\sum\log(1+|V(G)\cap
M|))^{2}\leq(1+\sum(\log(1+|V(G)\cap M|))^{2})\cdot O(1)$ by the Cauchy-
Schwarz inequality. Therefore, each cell $M$ contributes $O(\log(1+|V(G)\cap
M|)^{2})$ to $c(v)^{2}$. Each cell is an $O(1)$-neighboring cell of $O(1)$
cells, and each cell contains $O(1)$ vertices of $H$ (and thus $H_{3}$). Thus
$M$ contributes to the weights of $O(1)$ vertices of $H_{3}$.

Consider the cells in $\mathcal{M}$ containing at most three vertices of $G$,
say _light cells_. Each light cell contributes $O(1)$ to $c(v)^{2}$ since
$\log(1+|V(G)\cap M|)\leq\log 4=2$. Thus, for each vertex $v$ of $H_{3}$, the
portion of $c(v)^{2}$ induced by the light cells is $O(1)$, and the portion of
the sum of $c(v)^{2}$ induced by light cells is $O(\ell)$ over all vertices of
$H_{3}$ in total. Now consider the cells in $\mathcal{M}$ containing more than
three vertices of $G$, say _heavy cells_. Since $(\log z+1)^{2}\leq 2z$ for
every natural number $z$, a heavy cell $M$ contributes at most $2|V(G)\cap M|$
to a vertex of $H_{3}$ contained in an $O(1)$-neighboring cell of $M$. Notice
that the sum of $2|V(G)\cap M|$ over all heavy cells $M$ is $O(\ell)$ since
the number of vertices of $H_{3}$ is $O(\ell)$. Therefore, the heavy cells
contribute $O(\ell)$ to the sum of $c(v)^{2}$ over all vertices $v$ of $H_{3}$
in total. This implies that the sum of $c(v)^{2}$ over all vertices $v$ of
$H_{3}$ is $O(\ell)$, and $c_{\textsf{sos}}({H_{3}})$, which is the square of
the sum of $c(v)^{2}$, is at most $O(\sqrt{\ell})$. ∎

By construction of the drawing of $H_{3}$, some polygonal curves of the
drawing of $H$ do not appear in the drawing of $H_{3}$. Thus the boundary of a
piece of ${\mathcal{A}}$ might cross an edge of $H$. We can avoid this case by
constructing a surface decomposition of $H_{3}$ more carefully. A polygonal
curve of $H$ not appearing in $H_{3}$ is attached at a single vertex of
$H_{3}$. Whenever we construct a hole and vertex separator during the
construction of a surface decomposition of $H_{3}$, we set those polygonal
curves as forbidden regions. We can construct a hole and vertex separator not
intersecting these forbidden regions as mentioned in the remark at the end of
Section 5.1.

###  6.2 Step 2: Constructing a Surface Decomposition of $H$ Using $H_{3}$

Given a surface decomposition ($T$, ${\mathcal{A}}$) of $H_{3}$ intersecting
the drawing of $H$ only at its vertices, we construct a surface decomposition
of $H$. We simply call a maximal path of $H$ whose internal vertices have
degree two a _maximal chain_ of $H$. If both endpoints of a maximal chain lie
on the boundary of $A_{t}$ for a node $t$, it is called a _traversing chain_
of $A_{t}$. Otherwise, exactly one endpoint lies on the boundary of $A_{t}$.
In this case, it is called an _attached chain_ of $A_{t}$. See Figure 8(a). A
piece of a leaf node of $T$ might contain maximal chains of $H$. Recall that
by the definition of a surface decomposition, each leaf node must have a piece
containing at most two vertices of $H$. To handle this issue, we subdivide
such pieces further. Once this is done, the resulting pair becomes a surface
decomposition of $H$.

Let $t$ be a leaf node of $T$ such that $A_{t}$ contains a maximal chain.
Here, $A_{t}$ contains at most one traversing chain, but it might contain more
than one attached chains. This is because the endpoints of a traversing chain
appear in $V(H_{3})\cap A_{t}$. We handle each maximal chain one by one
starting from the attached chains (if they exist). To handle a maximal chain
$\pi$, we cut $A_{t}$ into two pieces along a closed polygonal curve $C$ whose
interior is contained in $A_{t}$ as follows. If there is a maximal chain in
$A_{t}$ other than $\pi$, we separate $\pi$ from all other maximal chains.
Note that $\pi$ is an attached chain by definition. In this case, we choose
$C$ such that it intersects $\pi$ only at the endpoint $p$ of $\pi$ lying on
the boundary of $A_{t}$, and it touches $\partial A_{t}$ along an
$\epsilon$-neighborhood of $p$ in $\partial A_{t}$ for a sufficiently small
constant $\epsilon>0$ so that the rank of the piece does not increases. See
Figure 8(b). If $\pi$ is a unique maximal chain in $A_{t}$, we separate one
endpoint of $\pi$ from all other edges of $\pi$. We choose $C$ such that $C$
intersects $\pi$ only at the first vertex of $\pi$ and the second last vertex
of $\pi$, and it touches $\partial A_{t}$ along an $\epsilon$-neighborhood of
the first vertex of $\pi$ in $\partial A_{t}$ for a sufficiently small
constant $\epsilon>0$. Here, $\pi$ is oriented from an arbitrary endpoint
lying on $\partial A_{t}$ to the other one. In this case, the rank of the
piece increases by at most one. See Figure 8(c). We add two children of $t$,
and assign the two pieces to those new nodes. Then we repeatedly subdivide the
pieces further for the new nodes until all leaf noes have pieces containing
exactly one edge of $H$. Then all pieces contains at most two vertices of $H$.

Since $c_{\textsf{max}}(H)=O(\log\ell)$ by Lemma 6.1, the new nodes
constructed from a node $t$ of $T$ have weight at most $O(\log\ell)$ plus the
weight of $t$, which is $O(\sqrt{\ell})$. This is because the closed polygonal
curve $C$ constructed for non-unique maximal chains does not intersect any
vertex of $H$ which were contained in the interior of $A_{t}$. In the case of
a unique maximal chain, it intersects exactly one new vertex of $H$ which were
contained in the interior of $A_{t}$. Since a single vertex has weight
$O(\log\ell)$, this does not increase the weight of the surface decomposition
asymptotically. By the argument in this subsection, we can conclude that
$(T,{\mathcal{A}})$ is a surface decomposition of $H$ of $O(\sqrt{\ell})$
weighted width.

Figure 8: (a) The piece $A_{t}$ contains a traversing chain and an attached
chain. (b) We first handle the attached chain. The new closed curve forms a
part of the outer boundary curve of $A_{t^{\prime}}$. (c) Then we handle the
traversing chain. We compute a curve separating an edge of the traversing
chain from the other edges. Since $A_{t^{\prime\prime}}$ contains exactly one
edge of $H$, we do not subdivide $A_{t^{\prime\prime}}$ further.

lemmacontracted $(T,{\mathcal{A}})$ is a surface decomposition of $H$ and has
weighted width $O(\sqrt{\ell})$.

###  6.3 Step 3: sc-Decomposition of $G$ from a Decomposition of $H$

Then we compute an sc-decomposition $(T,\bar{\mathcal{A}})$ of $G$ from the
surface decomposition $(T,{\mathcal{A}})$ of $H$. The pieces of
${\mathcal{A}}$ are constructed with respect to the vertices of $H$. We
perturb the boundaries of the pieces of ${\mathcal{A}}$ slightly so that no
piece contains a vertex of $G$ on its boundary.

####  6.3.1 Constructing an sc-Decomposition of $G$ Using Perturbation

For perturbation, observe that the pieces of all leaf nodes of $T$ is a
partition of $\mathbb{R}^{2}$ by (A2). Thus if we perturb such pieces only,
then the pieces of all other nodes of $T$ can be updated accordingly. Let
$\mathcal{A}_{L}$ be the set of the pieces of the leaf nodes of $T$. During
the perturbation, we do not move the intersection points between $\partial
A_{t}$ and the boundaries of the cells of $\mathcal{M}$, and thus we can
handle the cells of $\mathcal{M}$ one by one separately.

For a cell $M$ of $\mathcal{M}$, let $\mathcal{S}_{M}$ be the subdivision of
$M$ with respect to the pieces of $\mathcal{A}_{L}$. Without changing its
combinatorial structure, we modify $\mathcal{S}_{M}$ such that no vertex of
$G$ lies on the boundary of the edges of the subdivision. Since each cell of
$M$ has $O(1)$ edges, we can do this without increasing the complexity of the
subdivision. By construction, each region of the resulting set
$\mathcal{A}_{L}$ is a piece, and the combinatorial structure of the
subdivision of $\mathbb{R}^{2}$ induced by the pieces of $\mathcal{A}_{L}$
remains the same. Let $\bar{\mathcal{A}}$ be the set of pieces we obtained
from the perturbation.

######  Lemma 16.

$(T,\bar{\mathcal{A}})$ is an sc-decomposition of $G$.

###### Proof.

By the general position assumption, no vertex of $G$ lies on the boundary of a
cell of $\mathcal{M}$. Therefore, by construction, no vertex of $G$ lies on
the boundary of a piece of $\bar{\mathcal{A}}$, and thus
$V(G)\cap\partial\bar{A}_{t}=\emptyset$ (Condition (C1)). Also,
$\bar{A}_{t^{\prime}},\bar{A}_{t^{\prime\prime}}$ are interior-disjoint, and
$\bar{A}_{t^{\prime}}\cup\bar{A}_{t^{\prime\prime}}=\bar{A}_{t}$ for all node
$t$ and its children $t^{\prime},t^{\prime\prime}$ (Condition (C2)). This is
because the combinatorial structures of the pieces of ${\mathcal{A}}$ do not
change during the perturbation. For a leaf node $t$ of $T$, $A_{t}$ contains
at most two vertices of $H$ by (A3). For an $O(1)$-neighboring cell $M$ of the
cell containing a vertex of $G$ of degree at least three, its boundary edges
are contained in the drawing of $H$. Thus $M$ is intersected by $\bar{A}_{t}$
only when $A_{t}$ contains a vertex of $H$ lying on the boundary of $M$. Thus
$A_{t}$ intersects at most two such cells. For the other cells, they contain
at most two vertices of $G$. Thus $\bar{A}_{t}\cap V(G)$ are contained in at
most two cells of $\mathcal{M}$, and thus the condition (C3) also holds. For
the condition (C4), observe that a cell of $\mathcal{M}$ containing exactly
one point of $V(G)$ satisfies (C4) immediately. On the other hand, for a cell
$M$ containing more than one point of $V(G)$, the boundary of $M$ appears on
the drawing of $H$, and thus a piece containing a vertex of $V(G)\cap M$
contains a vertex of $H$ on its boundary. Since the leaf pieces are interior-
disjoint, there are $O(1)$ leaf nodes containing vertices of $V(G)\cap M$ in
their pieces. Therefore, (C4) is also satisfied. ∎

####  6.3.2 Analysis of the Clique-Weighted Width

We show that the clique-weighted width of $(T,\bar{\mathcal{A}})$ is
$O(\sqrt{\ell})$ using the fact that $(T,\mathcal{A})$ has weighted width
$O(\sqrt{\ell})$. In particular, we show that for each node $t$ of $T$, the
clique-weight of the cells of $\mathcal{M}$ containing the endpoints of the
edges of $\textsf{cut}({t})$ is $O(\sqrt{\ell})$. Let $A$ be a piece of a node
of $T$, and let $\bar{A}$ be the piece obtained from $A$ by the perturbation.

Let $t$ be a node of $T$. Let $\textsf{bd}({t})$ denote the set of vertices of
$V(H)\cap\partial A_{t}$. The weight of $t$ in the surface decomposition of
$H$ is defined as the total weight of $\textsf{bd}({t})$. Also, the weight
$c_{H}(v)$ of $v$ in $H$ is defined as the total clique-weight of the cells of
$\mathcal{M}_{\textsf{nb}}(v)$, where $\mathcal{M}_{\textsf{nb}}(v)$ denotes
the set of all $\alpha$-neighboring cells of $M_{v}$. Therefore, it suffices
to show that the endpoints of $\textsf{cut}({t})$ are contained in the cells
of the union of $\mathcal{M}_{\textsf{nb}}(v)$ for all vertices
$v\in\textsf{bd}({t})$.

Let $e=ab$ be an edge of $\textsf{cut}({t})$, and let $M$ be a cell containing
a point of $e\cap\partial\bar{A}_{t}$. Consider the case that either $M_{a}$
or $M_{b}$ contains a vertex of degree at least three. Here, $M_{a}$ and
$M_{b}$ are the cells of $\mathcal{M}$ contain $a$ and $b$, respectively.
Notice that $M$ is an $\alpha$-neighboring cell of a vertex of $G$ of degree
at least three, and thus $\partial M$ appears on the drawing of $H$ by the
construction of $H$. Therefore, $\partial A_{t}$ intersects $\partial M$ only
at vertices of $H$, say $v$. Note that $v\in\textsf{bd}(t)$, and $a$ and $b$
are contained in cells of $\mathcal{M}_{\textsf{nb}}(v)$.

Now consider the case that $M_{a}$ and $M_{b}$ contain vertices of degree two
only. Thus $a$ and $b$ are degree-2 vertices of $G$. Consider a maximal chain
$\pi$ of degree-2 vertices of $G$ containing $ab$. It is a part of the drawing
of $H$, and thus $\partial A_{t}$ intersects $\pi$ only at vertices of $\pi$.
Therefore, $ab$ is intersected by $\partial A_{t}$ only when $a$ or $b$ lies
on $\partial A_{t}$. Without loss of generality, assume that $a$ lies on
$\partial A_{t}$. This means that $a\in\textsf{bd}({t})$, and both $a$ and $b$
are contained in cells of $\mathcal{M}_{\textsf{nb}}(a)$ in this case.

*

*

##### Remark.

The icf-property is crucial to get the bound on the width of the surface
decomposition. In particular, for a graph $G$ which does not admit this
property, we cannot bound the number of vertices of $H_{3}$. Nevertheless, in
this case, we can compute an sc-decomposition of weighted width
$O(\sqrt{\ell+\ell^{\prime}})$ once we have a map of $G$, where $\ell$ and
$\ell^{\prime}$ denotes the number of vertices of degree at least three in $G$
and $H$, respectively.

##  7 Properties of Vertex-Disjoint Cycles

For a graph $G$ drawn in the plane with a map that satisfies the icf-property,
we define three properties of a set of $k$ vertex-disjoint cycles in $G$:
quasi-planar property, bounded packedness property, and sparse property. We
will see in Section 9, if $G$ has $k$ vertex-disjoint cycles satisfying these
three properties, we can compute a set of $k$ vertex-disjoint cycles in $G$ in
$2^{O(\sqrt{k})}n^{O(1)}$ time. Let $\mathcal{M}$ be a map, and $H$ be a map
sparsifier of $G$ with respect to $\mathcal{M}$. Throughout this section,
$\alpha$ is a fixed constant which is the maximum number of cells of
$\mathcal{M}$ intersected by one edge of $G$.

##### Bounded packedness property.

A set $\Gamma$ of vertex-disjoint cycles of $G$ is _$c$ -packed_ if at most
$c$ vertices contained in a cell of $\mathcal{M}$ lie on the cycles of
$\Gamma^{\prime}$, and every cycle of $\Gamma\setminus\Gamma^{\prime}$ is a
triangle, where $\Gamma^{\prime}$ is the set of cycles of $\Gamma$ visiting at
least two vertices from different cells of $\mathcal{M}$.

lemmapacked Let $G$ be a graph drawn in the plane having a map $\mathcal{M}$.
If $G$ has a set of $k$ vertex-disjoint cycles, then it has a set of $k$
vertex-disjoint cycles which is $O(1)$-packed.

###### Proof.

Among all sets of $k$ vertex-disjoint cycles of $G$, we choose the one
$\Gamma$ that minimizes the number of cycles of $\Gamma$ visiting at least two
vertices from different cells. Let $\Gamma^{\prime}$ be the set of cycles of
$\Gamma$ visiting at least vertices from different cells. Let $M$ be a cell of
$\mathcal{M}$, and $Q$ be the set of vertices of $V\cap M$ lying on the cycles
of $\Gamma^{\prime}$. In the following, we show that $|Q|\leq\beta^{2}\times
3$, where $\beta$ is the maximum number of $\alpha$-neighboring cells of a
cell of $\mathcal{M}$.

For this purpose, assume $|Q|>\beta^{2}\times 3$. For each vertex $v$ in $Q$,
let $x(v)$ and $y(v)$ be the neighbors of $v$ along the cycle of
$\Gamma^{\prime}$ containing $v$. Consider the (at most $\beta$) cells of
$\mathcal{M}$ which are $\alpha$-neighboring cells of $M_{v}$. All neighbors
of the vertices of $Q$ are contained in the union of these cells. Among all
pairs of such cells, there is a pair $(M_{1},M_{2})$ such that the number of
vertices $v$ of $Q$ with $x(v)\in M_{1}$ and $y(v)\in M_{2}$ is at least
$|Q|/\beta^{2}\geq 3$. See Figure 9(a–b). Let $v_{1},v_{2}$ and $v_{3}$ be
such vertices. Then we can replace the cycles containing at least one of
$v_{1},v_{2}$ and $v_{3}$ with three triangles: one consisting of
$x(v_{1}),x(v_{2})$ and $x(v_{3})$, one consisting of $v_{1},v_{2}$ and
$v_{3}$, and one consisting of $y(v_{1}),y(v_{2})$ and $y(v_{3})$. This is
because the vertices of $G$ contained in a single cell form a clique, and the
cycles of $\Gamma$ are pairwise vertex-disjoint. This contradicts the choice
of $\Gamma$. ∎

Figure 9: The $\alpha$-neighboring cells around $M$. If there are three
vertices $v_{1},v_{2}$ and $v_{3}$ in $M$ such that the neighboring vertices
of them on $\Gamma^{\prime}$ are contained in $M_{1}$ and $M_{2}$, the three
cycles containing $v_{1},v_{2}$ and $v_{3}$, respectively, can be replaced
with the three triangles.

##### Quasi-planar property.

A set $\Gamma$ of vertex-disjoint cycles of $G$ is _quasi-planar_ if each
cycle of $\Gamma$ is not self-crossing, and for any set $\Pi$ of subpaths of
the non-triangle cycles of $\Gamma$, the intersection graph of $\Pi$ is
$K_{z,z}$-free for a constant $z$ depending only on the maximum number of
paths of $\Pi$ containing a common edge. Here, the intersection graph is
defined as the graph where a vertex corresponds to a non-triangle cycle of
$\Gamma$, and two vertices are connected by an edge if and only if their
corresponding cycles cross in their drawing. For two paths of $\Pi$ having a
common edge $e$, their intersection at a point in $e$ is not counted as
crossing. In this case, note that two paths of $\Pi$ come from the same cycle
of $\Gamma$.

Figure 10: (a) The intersection graph of
$\eta_{1},\ldots,\eta_{z},\pi_{1},\ldots,\pi_{z}$ contains $K_{z,z}$ as a
subgraph, and none of two paths share a common edge. (b) We can pick four
indices such that the the distance between two cells containing two crossing
points is at least $2\alpha$. We can replace (at most) four cycles containing
$\pi_{i},\pi_{i^{\prime}},\eta_{j}$ and $\eta_{j^{\prime}}$ with four
triangles by the icf-property.

######  Lemma 17.

Let $G$ be a graph drawn in the plane having a map $\mathcal{M}$ and admitting
the icf-property. If $G$ has a set of $k$ vertex-disjoint cycles, then it has
a set of $k$ quasi-planar and $O(1)$-packed vertex-disjoint cycles.

###### Proof.

Let $\Gamma$ be a set of $k$ vertex-disjoint cycles which has the minimum
number of edges in total among all $O(1)$-packed vertex-disjoint cycles.
First, due to the icf-property, no cycle of $\Gamma$ has a self-crossing. Let
$\Pi$ be the set of subpaths of non-triangle cycles of $\Gamma$ such that two
subpaths of $\Pi$ may share some common edges, and let $\mathcal{I}$ be the
intersection graph of the drawing of $\Pi$. Also, let $s$ be the the maximum
number of paths of $\Pi$ containing a common edge.

If $\mathcal{I}$ is not $K_{z,z}$-free, there are $z/s$ paths
$\pi_{1},\ldots\pi_{z}$ and another $z/s$ paths $\eta_{1},\ldots,\eta_{z}$ of
$\Pi$ such that $\pi_{i}$ crosses $\eta_{j}$ in their drawings for every index
pair $(i,j)$ with $1\leq i,j\leq z$. Let $a(i,j)$ be a crossing point between
$\pi_{i}$ and $\eta_{j}$. We denote the cell of $\mathcal{M}$ containing
$a(i,j)$ by $M_{i,j}$. Let $\beta$, $\kappa$ be the maximum numbers of
$\alpha$-neighboring cells and $2\alpha$-neighboring cells of a cell of
$\mathcal{M}$, respectively. Then $\beta,\kappa=O(1)$. Since each edge of $G$
intersects at most $\alpha$ cells, at most $b:=c^{2}\beta^{2}$ crossing points
are contained in one cell $M$ of $\mathcal{M}$. Here, $c$ is a constant
specified in Lemma 7 such that $G$ admits a $c$-packed solution. We claim that
if $z/s>2b^{2}\kappa^{2}$, there are four indices
$i,j,i^{\prime},j^{\prime}<z$ such that $d(M_{i,j},M_{i^{\prime},j})$,
$d(M_{i,j^{\prime}},M_{i^{\prime},j^{\prime}})$,
$d(M_{i,j},M_{i,j^{\prime}})$, and
$d(M_{i^{\prime},j},M_{i^{\prime},j^{\prime}})$ are greater than $2\alpha$,
where $d(M,M^{\prime})$ is the length of the shortest path between $M$ and
$M^{\prime}$ in the dual graph of $\mathcal{M}$. If the claim holds, we can
replace the cycles containing $\pi_{i},\pi_{i^{\prime}},\eta_{j}$ and
$\eta_{j^{\prime}}$ into four vertex-disjoint triangles by applying icf-
property on the crossing points $a(i,j),a(i^{\prime},j),a(i,j^{\prime})$ and
$a(i^{\prime},j^{\prime})$. The four triangles are vertex-disjoint because the
distance between any two cells containing two crossing points are greater than
$2\alpha$, while each edge intersects at most $\alpha$ cells. Moreover, this
replacement does not violate the $c$-packed property, but it violates the
choice of $\Gamma$. Thus the lemma holds.

Then we show that we can always find four such indices. Since
$z/s>2b^{2}\kappa^{2}$, we can pick $2b\kappa$ indices $j_{1},\ldots
j_{2b\kappa}$ such that the distance between any two of $M_{1,j_{1}},\ldots
M_{1,j_{2b\kappa}}$ is greater than $2\alpha$. Then there are at most
$2b^{2}\kappa^{2}$ indices $i$ such that $d(M_{1,j_{m}},M_{i,j_{m}})$ is at
most $2\alpha$ for some $m\leq 2b\kappa$. In other words, we can pick an index
$i$ such that $d(M_{1,j_{m}},M_{i,j_{m}})$ is greater than $2\alpha$ for all
$m\leq 2b\kappa$. Among $2b\kappa$ intersection points $a(i,j_{m})$’s, we can
pick two points $a(i,j)$ and $a(i^{\prime},j^{\prime})$ such that
$d(M_{i,j},M_{i^{\prime},j^{\prime}})>2\alpha$. See also Figure 10. This
completes the proof. ∎

##### Sparse property.

A graph $G$ with the icf-property that has a map becomes sparse after applying
the cleaning step that removes all vertices not contained in any cycle of $G$.
The cleaning step works by recursively removing a vertex of degree at most one
from $G$. Note that the resulting graph is also a graph with the icf-property.
From now on, we assume that every vertex of $G$ has degree at least two.

lemmanumdegree-apd Let $G$ be a graph with the icf-property. For a constant
$c$, assume that $G$ has more than $ck$ vertices of degree at least three
after the cleaning step. Then $(G,k)$ is a yes-instance, and moreover, we can
find a set of $k$ vertex-disjoint cycles in polynomial time.

###### Proof.

We first remove $O(k)$ vertices to make the graph planar. If two edges $xy$
and $zw$ of $G$ cross, three of four vertices, say $x,y$ and $z$, form a
triangle by the icf-property. Then we remove $x,y,z$ and all edges incident to
$x,y,z$ from $G$. If we can do this $k$ times, $G$ has $k$ vertex-disjoint
cycles. Thus we assume that we can apply the removal less than $k$ times. In
this way, we remove $O(k)$ vertices of $G$, and then we have a planar induced
subgraph $G_{1}$ of $G$. Note that $G_{1}$ itself also admits the icf-
property. We first show that the number of vertices of $G_{1}$ adjacent to the
removed vertices is $O(k)$. Observe that no five vertices of $G_{1}$ are
contained in the same cell of $\mathcal{M}$. Otherwise, $G_{1}$ contains
$K_{5}$ as a subgraph, and thus it is not planar. For a removed vertex $v$,
its neighbors in $G$ are contained in $\beta=O(1)$ cells of $\mathcal{M}$.
Therefore, there are $O(1)$ vertices of $G_{1}$ adjacent to $v$ in $G$, and
thus the number of vertices of $G_{1}$ adjacent to removed vertices is $O(k)$.

Now it is sufficient to show that the number of vertices of $G_{1}$ of degree
at least three is $O(k)$. For the purpose of analysis, we iteratively remove
degree-1 vertices from $G_{1}$. Let $G_{2}$ be the resulting graph. In this
way, a vertex of degree at least three in $G_{1}$ can be removed, and the
degree of a vertex can decrease due to the removed vertices. We claim that the
number of such vertices is $O(k)$ in total. To see this, consider the subgraph
of $G_{1}$ induced by the vertices removed during the construction of $G_{2}$.
They form a rooted forest such that the root of each tree is adjacent to a
vertex of $G_{2}$, and no leaf node is adjacent to a vertex of $G_{2}$. The
number of vertices of the forest of degree at least three is linear in the
number of leaf nodes of the forest. Since $G$ has no vertex of degree one due
to the cleaning step, all leaf nodes of the forest are adjacent to
$V(G)\setminus V(G_{1})$. Therefore, only $O(k)$ vertices of degree at least
three in $G$ are removed during the construction of $G_{2}$. Also, the degree
of a vertex decreases only when it is adjacent in $G$ to a root node of the
forest. Since the number of root nodes of the forest is $O(k)$, and a root
node of the forest is adjacent to only one vertex of $G_{2}$, there are $O(k)$
vertices of $G_{2}$ whose degrees decrease during the construction of $G_{2}$.

Therefore, it is sufficient to show that vertices of $G_{2}$ of degree at
least three is at most $10k$. Let $H$ be the dual graph of $G_{2}$. Since $H$
is also a planar graph, it is 5-colorable. Then there is a set of $|F_{2}|/5$
vertices with the same color, and it is an independent set of $H$, where
$F_{2}$ denotes the number of faces of $G_{2}$. Note that a vertex of $H$
corresponds to a face of $G_{2}$. Two vertices of $H$ are connected by an edge
if and only if their corresponding faces share an edge. Therefore, the faces
in $H$ corresponding to the vertices of $I$ form $|I|$ vertex-disjoint cycles
in $G_{2}$. Therefore, if $|F_{2}|$ exceeds $5k$, $(G,k)$ is yes-instance. In
this case, since we can find a 5-coloring of a planar graph in polynomial
time, we can compute $k$ vertex-disjoint cycles in polynomial time. Now
consider the case that $(G,k)$ is no-instance. Let $V_{2},E_{2}$ and $F_{2}$
be the vertex set, edge set, and face set of $G_{2}$, respectively. Let $\ell$
be the number of vertices of $G_{2}$ of degree at least three. We have three
formulas:

$\displaystyle 2(|V_{2}|-\ell)+3\ell\leq\sum_{v\in
V_{2}}\textsf{deg}(v)=2|E_{2}|$ $\displaystyle|V_{2}|-|E_{2}|+|F_{2}|=2$
$\displaystyle|F_{2}|\leq 5k$

This implies that $|V_{2}|\leq 10k$, and thus the lemma holds. ∎

##  8 Generalization of Catalan Bounds to Crossing Circular Arcs

It is well-known that, for a fixed set $P$ of $n$ points on a circle, the
number of different sets of pairwise non-crossing circular arcs having their
endpoints on $P$ is the $n$-th Catalan number, which is $2^{O(n)}$. Here, two
circular arcs are _non-crossing_ if they are disjoint or one circular arc
contains the other circular arc. This fact is one of main tools used in the
ETH-tight algorithm for the planar cycle packing problem: Given a noose
$\gamma$ of a planar graph $G$ visiting $m$ vertices of $G$, the parts of the
cycles of $\Gamma$ contained in the interior of $\gamma$ corresponds to a set
of pairwise non-crossing circular arcs having their endpoints on fixed $m$
points, where $\Gamma$ denotes a set of vertex-disjoint cycles of $G$ crossing
$\gamma$. This holds since no two vertex-disjoint cycles cross in planar
graphs. Although two vertex-disjoint cycles in a graph $G$ admitting the icf-
property can cross in their drawing, there exists a set of $k$ vertex-disjoint
cycles of $G$ with the quasi-planar property due to Lemma 17. To make use of
this property, we generalize the Catalan bound on non-crossing circular arcs
to circular arcs which can cross.

The _circular arc crossing graph_ , CAC graph in short, is a variation of the
circular arc graph. For a fixed set $P$ of points on a unit circle, consider a
set $\mathcal{C}$ of circular arcs on the unit circle connecting two points of
$P$ such that no arcs share their endpoints. The CAC graph of $\mathcal{C}$ is
defined as the graph whose vertex corresponds to a circular arc of
$\mathcal{C}$, and two vertices are connected by an edge if and only if their
corresponding circular arcs are crossing. Here, we say two arcs on the unit
circle are _crossing_ if they are intersect and none of them contains the
other arc. Note that the CAC graph $G_{\textsf{cac}}$ of $\mathcal{C}$ depends
only on the pairing $\mathcal{P}$ of the endpoints of the arcs of
$\mathcal{C}$. If we do not want to specify circular arcs, we simply say
$G_{\textsf{cac}}$ is the CAC graph of $\mathcal{P}$. With a slight abuse of
term, we say a set $\mathcal{C}$ of circular arcs (or its pairing) is
$K_{z,z}$-free if its CAC graph is $K_{z,z}$-free. Note that a set of pairwise
non-crossing circular arcs is $K_{1,1}$-free since its CAC graph is edgeless.

lemmacirculararc The number of $K_{z,z}$-free sets of circular arcs over a
fixed set $P$ of points is $2^{O_{z}(|P|)}$.

###### Proof.

For the convenience, we let $P=\\{1,2,\ldots,2m\\}$ be the cyclic sequence of
the elements of $\mathbb{Z}_{2m}$. For a $K_{z,z}$-free set $\mathcal{C}$ of
circular arcs, an arc of $\mathcal{C}$ with counterclockwise endpoint $a$ and
clockwise endpoint $b$ for $\mathbb{Z}_{2m}$ is denoted by $[a,b]$. We
decompose the arcs of $\mathcal{C}$ into several _layers_ as follows. In each
iteration, we choose all arcs of $\mathcal{C}$ not contained in any other arcs
of $\mathcal{C}$, and remove them from $\mathcal{C}$. The _level_ of $\gamma$
is defined as the index of the iteration when $\gamma$ is removed.

Figure 11: All arcs of level less than $i-z$ with endpoints in $\gamma_{i}$
(colored red) intersect $\gamma_{i},\gamma_{i-1},\ldots,\gamma_{i-z+1}$.

######  Claim 18.

An arc of level $i$ contains at most $z$ endpoints of the arcs of level less
than $i-z$.

###### Proof.

Assume to the contrary that an level-$i$ arc $\gamma_{i}$ of $\mathcal{C}$
contains more than $z$ endpoints of arcs of $\mathcal{C}$ of level less than
$i-z$. For each index $k$ with $i-z<k\leq i$, there is an level-$k$ arc
$\gamma_{k}$ containing $\gamma_{i}$. This arc $\gamma_{k}$ forbids
$\gamma_{i}$ from being assigned level $k$. But $\gamma_{k}$ does not contain
an arc $\gamma$ of level less than $i-z$ as $\gamma_{k}$ forbids $\gamma$ from
being assigned level lower than $k$. That is, $\gamma$ crosses $\gamma_{k}$ if
$\gamma_{i}$ contains an endpoint of $\gamma$. See Figure 11. Therefore,
$\\{\gamma_{i},\gamma_{i-1},\ldots\gamma_{i-z+1}\\}$ and the $z$ arcs of
$\mathcal{C}$ of level less than $i-z$ crossing $\gamma_{i}$ induces $K_{z,z}$
subgraph of the CAC graph of $\mathcal{C}$. This contradicts that the CAC
graph of $\mathcal{C}$ is $K_{z,z}$-free. ∎

Note that the maximum level among all arcs of $\mathcal{C}$ is at most $m$
since the endpoints of the arcs of $\mathcal{C}$ are distinct. For each
integer $i\leq m$, we denote the set of endpoints of all circular arcs of
level at most $i$ by $P_{i}$. Then we have $P_{1}\subset
P_{2}\subset\ldots\subset P_{m}=P$. We let $P_{i}=\emptyset$ for $i\leq 0$ for
convenience. For a subset $P^{\prime}$ of $P$, we define a _partial order_
$\chi_{P^{\prime}}:P^{\prime}\rightarrow[1,|P^{\prime}|]$ such that
$\chi_{P^{\prime}}(a)=b$ if $a$ is the $b$-th endpoint of $P^{\prime}$
(starting from 1). We simply write $\chi_{i,j}=\chi_{P_{j}\setminus P_{i-1}}$
for every $i\leq j$. Given a partial order $\chi_{i,j}$, consider the mapping
that maps each circular arc $[a,b]$ into $[\chi_{i,j}(a),\chi_{i,j}(b)]$,
where $a,b\in P_{j}\setminus P_{i-1}$. We define the _quotient_ $Q_{i,j}$ by
the set of circular arcs $[\chi_{i,j}(a),\chi_{i,j}(b)]$ on the ground set
$[1,2,\ldots|P_{j}\setminus P_{i-1}|]$. The CAC graph of $Q_{i,j}$ is
isomorphic to the subgraph of the CAC graph of $\mathcal{C}$, and therefore it
is $K_{z,z}$-free.

Then we analyze the number of $K_{z,z}$-free sets of circular arcs over $|P|$.
First, the number of different tuples $(|P_{1}|,|P_{2}|,\ldots|P_{m}|)$ is
$2^{O(m)}$ by simple combinatorics. Hence, we assume that the tuple
$(|P_{1}|,|P_{2}|,\ldots|P_{m}|)$ is fixed. We claim that the number of
different quotients $Q_{1,i}$ under a fixed $Q_{1,i-1}$ is single exponential
in $|P_{i}\setminus P_{i-z-1}|$ for every index $i$. First we show that the
number of different $Q_{i,i}$ is $2^{O_{z}(|P_{i}\setminus P_{i-1}|)}$.
Observe that no arc of $Q_{i,i}$ contains the other arc of $Q_{i,i}$ by
construction. For a circular arc $[a,b]$ in $Q_{i,i}$, at least
$\frac{b-a}{2}$ circular arcs of $Q_{i,i}$ contain $a$, and these arcs induce
a clique of size $\frac{b-a}{2}$ in the CAC graph of $Q_{i,j}$. Since this
graph is $K_{2z}$-free, $b-a\leq 4z$. Consequently, for each $a$, there are
$4z$ different candidates for the other endpoint $b$ of $[a,b]$. Thus, the
number of different $Q_{i,i}$ is $2^{O_{z}(|P_{i}\setminus P_{i-1}|)}$.

Next we bound the number of different $Q_{i-z,i}$. Note that the partial order
$\chi_{i-z,i-1}$ is fixed since $Q_{1,i-1}$ is fixed. Hence, the number of
different $\chi_{i-z,i}$ is equal to the number of ways to determine the
position of $P_{i}\setminus P_{i-1}$ on $\chi_{i-z,i}$ times the number of
different quotient $Q_{i,i}$. The former one equals to the number of different
subsets of size $|P_{i}\setminus P_{i-1}|$ from $\\{1,2,\ldots|P_{i}\setminus
P_{i-z}|\\}$, which is $2^{O(|P_{i}\setminus P_{i-z}|)}$. Thus, the number of
different $Q_{i-z,i}$ is $2^{O_{z}(|P_{i}\setminus P_{i-z}|)}$. Finally we
compute the number of different $Q_{1,i}$. We compute the number of different
range $\chi_{1,i}(P_{i-z})$ using Claim 18. This is equal to the number of
solutions of the following equation:

$n(1)+n(2)+\ldots+n(|P_{i}\setminus P_{i-z}|)=|P_{i-z}|,\text{ }\forall
j,n(j)\in\mathbb{Z}_{\geq 0}.$

Here, $n(j)$ represents the number of endpoints of $P_{i-z}$ located between
the $(j-1)$-th and $j$-th endpoints of $P_{i}\setminus P_{i-z}$. We use the
notation $a_{j}$ to denote the $j$-th endpoint of $P_{i}\setminus P_{i-z}$.
Since $Q_{1,i-1}$ is fixed, $n(j)$ is uniquely determined if both $a_{j}$ and
$a_{j-1}$ are contained in $P_{i-1}$. Therefore, we enough to compute $n(j)$
for all $j$ with $a_{j}\notin P_{i-1}$ or $a_{j-1}\notin P_{i-1}$. Suppose
$a_{j}\notin P_{i-1}$, and consider the arc of level $i$ whose one endpoint is
$a_{j}$. Then either this arc contains $[a_{j-1},a_{j}]$, or there is an arc
of level $i-1$ contains $[a_{j-1},a_{j}]$. For both cases, at most $O(1)$
points of $P_{i-z-1}$ are contained in $[a_{j-1},a_{j}]$ due to Claim 18. In
addition, there are at most $2|P_{i}\setminus P_{i-1}|$ $n(j)$’s which are not
uniquely determined. Overall, the number of different $\chi_{1,i}(P_{i-z})$ is
equal to the number of solutions of the following equation:

$n^{\prime}(1)+n^{\prime}(2)+\ldots+n^{\prime}(2|P_{i}\setminus
P_{i-1}|)=|P_{i}\setminus P_{i-z-1}|+O(1)\cdot|P_{i}\setminus P_{i-1}|,\text{
}\forall j,n^{\prime}(j)\in\mathbb{Z}_{\geq 0}.$

This is $2^{O(|P_{i}\setminus P_{i-1}|)+O(|P_{i}\setminus
P_{i-z-1}|)}=2^{O(|P_{i}\setminus P_{i-z-1}|)}.$ Overall, the number of
different $Q_{1,i}$ is at most the number of different $\chi_{1,i}(P_{i-z})$
times the number of different $Q_{i-z,i}$, which is $2^{O_{z}(|P_{i}\setminus
P_{i-z-1}|)}$. This confirms the claim. Finally, the number of different
$K_{z,z}$-free sets of circular arcs is

$\exp(\sum_{i}O_{z}(|P_{i}\setminus
P_{i-z-1}|))=\exp(O_{z}(|P_{m}|))=\exp(O_{z}(|P|)).$

This completes the proof. ∎

Moreover, we can compute all $K_{z,z}$-free sets of circular arcs over a fixed
set $P$ in $2^{O_{z}(|P|)}$ time. lemmacirculararc-algo Given a set $P$ of
points on a unit circle, we can compute all $K_{z,z}$-free sets of circular
arcs over $P$ in $2^{O_{z}(|P|)}$ time.

###### Proof.

Let $|P|=2m$. Since the number of different tuples
$(|P_{1}|,|P_{2}|,\ldots,|P_{m}|)$ is $2^{O(m)}$, it is sufficient to compute
all $K_{z,z}$-free sets of circular arcs under a fixed tuple
$(|P_{1}|,|P_{2}|,\ldots,|P_{m}|)$. Lemma 8 implicitly says that the number of
different quotients $Q_{i,j}$ is $\exp(\sum_{k\in[i,j]}|P_{k}|)$. We show that
given all different quotients $Q_{1,i-1}$, we can compute all different
quotients $Q_{1,i}$ in $\exp(O(\sum_{j\leq i}|P_{j}|)\cdot|P|^{2}$ time.
First, we enumerate all different quotients $Q_{i,i}$ in $2^{O(|P_{i}|)}$ time
by exhaustively considering all cases that the range of $Q_{i,i}$ consists of
the circular arcs of length at most $4z$. The number of different pairs
$(Q_{1,i-1},Q_{i,i})$ at this moment is $\exp(\sum_{j\leq i}|P_{j}|)$. For
each different pair, we consider $\exp(\sum_{j\leq i}|P_{j}|)$ possible sets
of $\chi_{1,i}(P_{i})$. Each triple $(Q_{1,i-1},Q_{i,i},\chi_{1,i}(P_{i}))$
induces a unique quotient $Q_{1,i}$. Then we check whether the CAC graph
w.r.t. the resulting quotient $Q_{1,i}$ is $K_{z,z}$-free or not, in
$O(|P|^{2})$ time for each triple. In summary, we can compute all different
quotients $Q_{1,i}$ in $\exp(O(\sum_{j\leq i}|P_{j}|))|P|^{2}$ time. Then we
can compute all different quotients $Q_{1,m}$ in $\exp(O(\sum_{j\leq
m}|P_{j}|))|P|^{3}=2^{O(|P|)}$ time. ∎

##  9 Algorithm for Cycle Packing

In this section, given a graph $G=(V,E)$ drawn in the plane along with a map
$\mathcal{M}$ and an sc-decomposition $(T,\mathcal{A})$ of clique-weighted
width $\omega$, we present a $2^{O(\omega)}n^{O(1)}$-time dynamic programming
algorithm that computes a maximum number of vertex-disjoint cycles of $G$.

Throughout this section, let $\Gamma$ be a maximum-sized set of vertex-
disjoint cycles which is quasi-planar and $O(1)$-packed. Let
$\mathcal{M}_{\textsf{f}}$ be the finer subdivision of $\mathcal{M}$ formed by
subdividing each cell of $\mathcal{M}$ into _finer cells_ along $\partial A$
for all pieces $A$ corresponding to the leaf nodes of $T$. We call a cycle of
$\Gamma$ an _intra-cell_ cycle if its vertices are contained in a single finer
cell of $\mathcal{M}_{\textsf{f}}$, and an _inter-cell_ cycle, otherwise.
Notice that an intra-cell cycle is a triangle since $\Gamma$ is $O(1)$-packed.
To make the description easier, we sometimes consider a set of vertex-disjoint
cycles and paths of $G$ as a _graph_ consisting of disjoint paths (path
components) and cycles (cycle components) if it is clear from the context. For
a set $\Gamma^{\prime}$ of paths and cycles of $G$, we let
$\textsf{end}(\Gamma^{\prime})$ be the set of end vertices of the _paths_ of
$\Gamma^{\prime}$, and $V(\Gamma^{\prime})$ be the set of all vertices of
_paths and cycles_ of $\Gamma^{\prime}$.

###  9.1 Standard DP Algorithm for Cycle Packing

In this subsection, we present a $2^{O(\omega\log\omega)}$-time algorithm for
the cycle packing problem using a dynamic programming on $(T,\mathcal{A})$ in
a standard manner. For a node $t$ of $T$, recall that $\textsf{cut}({t})$ is
the set of edges of $E$ with at least one endpoints in $A_{t}$ that intersect
the boundary of $A_{t}$. Also, recall that $G_{t}$ is the subgraph of $G$
induced by $V\cap A_{t}$. Let $\mathcal{M}_{t}$ be the set of finer cells of
$\mathcal{M}_{\textsf{f}}$ having vertices of $V(\textsf{cut}({t}))\cap
A_{t}$. The clique-weight of the finer cells in $\mathcal{M}_{t}$ is
$O(\omega)$ as for each cell $M$ of $\mathcal{M}$, $V(G)\cap M$ is decomposed
into $O(1)$ subsets $V(G)\cap M_{\textsf{f}}$ for finer cells $M_{\textsf{f}}$
of $\mathcal{M}_{\textsf{f}}$ by (C4).

##### Subproblems.

To encode the interaction between $\Gamma$ and $\textsf{cut}({t})$, we focus
on the parts of $\Gamma$ consisting of edges of $\textsf{cut}({t})$. Let
$\Lambda$ be the subgraph of $\Gamma$ induced by $\textsf{cut}({t})$, and
$\Delta$ be the set of intra-cell cycles of $\Gamma$ contained in a cell of
$\mathcal{M}_{t}$. See Figure 12. Then $V(\Lambda)\cap V(\Delta)=\emptyset$,
since an edge of $\Lambda$ is a part of an inter-cell cycle of $\Gamma$.

The interaction between $\Gamma$ and $\textsf{cut}({t})$ can be characterized
as $(\Lambda,V(\Delta),\mathcal{P})$ where $\Lambda$ and $V(\Delta)$ are
defined earlier, and $\mathcal{P}$ is the pairing of the vertices of
$\textsf{end}(\Lambda)$ contained in $A_{t}$ such that the vertices in the
same pair belong to the same component of the subgraph of $\Gamma$ induced by
$V\cap A_{t}$. We call $(\Lambda,V(\Delta),\mathcal{P})$ the $t$-_signature_
of $\Gamma$. Consider two sets $\Gamma$ and $\Gamma^{\prime}$ of vertex-
disjoint cycles of $G$ having the same signature. Imagine that we replace the
parts of the cycles of $\Gamma$ contained in $G_{t}$ with the parts of the
cycles of $\Gamma^{\prime}$ contained in $G_{t}$. The resulting set forms
vertex-disjoint cycles of $G$. Therefore, it suffices to find a maximum number
of vertex-disjoint cycles and paths contained in $G_{t}$ that matches the
given signature. A formal proof will be given in Lemma 19.

Figure 12: The $t$-signature $(\Lambda,V(\Delta),\mathcal{P})$ consists of the
vertex-disjoint cycles and paths induced by $\textsf{cut}({t})$ (black lines),
the vertices contained in $\mathcal{M}_{t}$ forming intra-cell cycles of
$\Delta$ (black vertices), and the connectivity information of the endpoints
of the paths of $\Lambda$ (dotted red line).

Since we are not given $\Gamma$ in advance, we try all possible tuples which
can be the signatures of $\Gamma$, and find an optimal solution for each of
such signatures. We define the subproblem for each _valid_ tuple
$(\widetilde{\Lambda},\widetilde{V},\widetilde{\mathcal{P}})$. We say a tuple
$(\widetilde{\Lambda},\widetilde{V},\widetilde{\mathcal{P}})$ is _valid_ if
for every finer cell $M$ of $\mathcal{M}_{t}$

  * •

$\widetilde{\Lambda}$ induces vertex-disjoint paths and cycles consisting of
edges of $\textsf{cut}({t})$,

  * •

$\widetilde{V}$ is a subset of $\\{v\in M^{\prime}\mid
M^{\prime}\in\mathcal{M}_{t}\\}$ with $\widetilde{V}\cap
V(\widetilde{\Lambda})=\emptyset$ and $|M\cap(V\setminus\widetilde{V})|=O(1)$,
and

  * •

$\widetilde{\mathcal{P}}$ is a pairing of all vertices of
$\textsf{end}(\widetilde{\Lambda})$ contained in $A_{t}$.

Notice that the $t$-signature of $\Gamma$ is also a valid tuple. For each
valid tuple $Q$ for a node $t$, the value $S[Q]$ is defined as the maximum
number of vertex-disjoint cycles of $\Gamma^{\prime}$ contained in $G_{t}$
over all sets $\Gamma^{\prime}$ of vertex-disjoint cycles and paths of
$G[E(G_{t})\cup\textsf{cut}({t})]$ whose $t$-signature is $Q$.999The signature
is defined for a set of disjoint cycles of $G$, but it can be extended to a
set of disjoint paths and cycles of $G[E(G_{t})\cup\textsf{cut}({t})]$ in a
straightforward manner. If such a set does not exist, we let $S[Q]=-\infty$.

lemmanumtuple The number of valid tuples is $2^{O(\omega\log\omega)}$.

###### Proof.

First, we analyze the number of choices of $\widetilde{\Lambda}$. Observe that
every finer cell of $\mathcal{M}_{t}$ contains $O(1)$ vertices of
$\widetilde{\Lambda}$ due the second validity condition. Since the clique-
weight of $V(\textsf{cut}({t}))$ is $O(\omega)$ by the definition of the
clique-weight of an sc-decomposition, the number of different sets of
$V(\widetilde{\Lambda})$ satisfying the validity conditions is

$\prod_{M\in\mathcal{M}_{t}}|M\cap
V(\textsf{cut}({t}))|^{O(1)}=\exp\biggl{(}O\biggl{(}\sum_{M\in\mathcal{M}_{t}}\log(|M\cap
V(\textsf{cut}({t}))|+1)\biggr{)}\biggr{)}=2^{O(\omega)}.$

Since each vertex of $\widetilde{\Lambda}$ has degree at most two in
$\widetilde{\Lambda}$, the number of different edge sets of
$\widetilde{\Lambda}$ is $2^{O(\omega)}$. Second, the number of different
$\widetilde{V}$ is $2^{O(\omega)}$ because all but $O(1)$ vertices in $M$ are
contained in $\widetilde{V}$ for each finer cell $M\in\mathcal{M}_{t}$, and
the clique-weight of the finer cells of $\mathcal{M}_{t}$ is $O(\omega)$. Thus
similarly to the first case, we can show that the number of different choices
of $\widetilde{V}$ is $2^{O(\omega)}$. Finally, observe that the number of
vertices of $\textsf{end}(\widetilde{\Lambda})$ contained in $A_{t}$ is
$O(\omega)$ since the number of cells of $\mathcal{M}_{t}$ containing vertices
of $\widetilde{\Lambda}$ is $O(\omega)$. Then the number of different pairings
$\mathcal{P}$ is $2^{O(\omega\log\omega)}$. ∎

Figure 13: (a) For the two tuples $Q_{1},Q_{2}$ harmonic with $Q$, the edge
set of $\widetilde{\Lambda}_{u}$ consists of the black lines of
$\widetilde{\Lambda}_{1}\cup\widetilde{\Lambda}_{2}$ and dotted curves of
$\widetilde{\mathcal{P}}_{1}\cup\widetilde{\mathcal{P}}_{2}$. (b)
$\widetilde{\Lambda}_{u}$ consists of one cycle and two paths, which are
stored as the information of $c(Q_{1},Q_{2})$ and $\widetilde{\mathcal{P}}$,
respectively.

##### Relation of the subproblems.

For a valid tuple
$Q=(\widetilde{\Lambda},\widetilde{V},\widetilde{\mathcal{P}})$ for a node
$t$, we say two valid tuples
$Q_{1}=(\widetilde{\Lambda}_{1},\widetilde{V}_{1},\widetilde{\mathcal{P}}_{1})$
and
$Q_{2}=(\widetilde{\Lambda}_{2},\widetilde{V}_{2},\widetilde{\mathcal{P}}_{2})$
for the two children $t_{1}$ and $t_{2}$ of $t$, respectively, are _harmonic_
with $Q$ if the following four conditions hold. Let
$\widetilde{\Lambda}_{\textsf{u}}$ be the graph obtained by taking the union
of $\widetilde{\Lambda}_{1}$ and $\widetilde{\Lambda}_{2}$ and then by adding
the edges $uv$ for all subsets
$\\{u,v\\}\in(\widetilde{\mathcal{P}}_{1}\cup\widetilde{\mathcal{P}}_{2})$.
See Figure 13. Then the following are the four conditions for tuples
$(Q_{1},Q_{2})$ harmonic with $Q$.

  * •

$M\cap\widetilde{V}=M\cap\widetilde{V}_{i}$ for every finer cell $M$ of
$\mathcal{M}_{t_{i}}\cap\mathcal{M}_{t}$ for $i=1,2$,

  * •

$E(\widetilde{\Lambda}_{1})\cap\textsf{cut}({t_{2}})=E(\widetilde{\Lambda}_{2})\cap\textsf{cut}({t_{1}})$
and
$E(\widetilde{\Lambda}_{i})\cap\textsf{cut}({t})=E(\widetilde{\Lambda})\cap\textsf{cut}({t_{i}})$
for $i=1,2$,

  * •

$\widetilde{\Lambda}_{\textsf{u}}$ consists of vertex-disjoint paths and
cycles, and

  * •

$\widetilde{\mathcal{P}}$ is the pairing consisting of the endpoint pairs of
paths of $\widetilde{\Lambda}_{\textsf{u}}$.

Notice that for fixed two tuples $Q_{1}$ and $Q_{2}$ harmonic with $Q$, the
graph $\widetilde{\Lambda}_{\textsf{u}}$ is fixed. Let $c(Q_{1},Q_{2})$ be the
number of cycles in $\widetilde{\Lambda}_{\textsf{u}}$.

######  Lemma 19.

For a valid tuple
$Q=(\widetilde{\Lambda},\widetilde{V},\widetilde{\mathcal{P}})$, we have

$S[Q]=\max\\{S[Q_{1}]+S[Q_{2}]+c(Q_{1},Q_{2})\\}$

where in the maximum we consider harmonic tuples $(Q_{1},Q_{2})$ with $Q$.

###### Proof.

The value $S[Q]$ is defined as the maximum number of vertex-disjoint cycles of
$\Gamma^{\prime}$ contained in $G_{t}$ among all sets $\Gamma^{\prime}$ of
vertex-disjoint cycles and paths in $G[E(G_{t})\cup\textsf{cut}({t})]$ whose
$t$-signature is $Q$. We first show that
$S[Q]\leq\max\\{S[Q_{1}]+S[Q_{2}]+c(Q_{1},Q_{2})\\}$. Among all sets of
vertex-disjoint paths and cycles we can attain for $S[Q]$, we choose the one
$\Gamma^{\prime}$ which is $O(1)$-packed and quasi-planar.101010The argument
of Section 7 implies that if there is a set of vertex-disjoint paths and
cycles whose $t$-signature is $Q$, then there is a set of vertex-disjoint
paths and cycles whose $t$-signature is $Q$ and which is $O(1)$-packed and
quasi-planar. Let $t_{1}$ and $t_{2}$ be the two children of $t$. Let
$Q_{i}=(\Lambda_{i},V(\Delta_{i}),\mathcal{P}_{i})$ be the $t_{i}$-signature
of $\Gamma^{\prime}$ for $i=1,2$. Since the signatures of $O(1)$-packed and
quasi-planar sets of vertex-disjoint cycles/paths are all valid, $Q_{1}$ and
$Q_{2}$ are also valid. Also, it is not difficult to see that $Q_{1}$ and
$Q_{2}$ are harmonic with $Q$.

We analyze $S[Q]$ with respect to $S[Q_{1}]$, $S[Q_{2}]$, and
$c(Q_{1},Q_{2})$. Recall that the number of cycles of $\Gamma^{\prime}$
contained in $G_{t}$ is $S[Q]$. The cycles of $\Gamma^{\prime}$ contained in
$G_{t}$ can be partitioned into three cases: it is contained in $G_{{t}_{1}}$,
or contained in $G_{{t}_{2}}$, or intersects both. The number of cycles of the
first case is at most $S[Q_{1}]$, and the number of cycles of the second case
is at most $S[Q_{2}]$. A cycle $\Gamma^{\prime}$ of the third case is an
inter-cell cycle. Imagine that we remove
$\textsf{cut}({t_{1}})\cup\textsf{cut}({t_{2}})$ from $\Gamma^{\prime}$. Then
we have a number of paths connecting two vertices of
$\textsf{end}(\textsf{cut}({t_{1}})\cup\textsf{cut}({t_{2}}))$ each of which
is contained in $G_{i}$ for $i=1,2$. Therefore, each path corresponds to a
pair of $\mathcal{P}_{i}$, and thus a cycle of the third case corresponds to a
cycle of $\Lambda_{\textsf{u}}$. The number of cycles of the third case is at
most $c(Q_{1},Q_{2})$, and thus the inequality holds.

Now consider the other direction:
$S[Q]\geq\max\\{S[Q_{1}]+S[Q_{2}]+c(Q_{1},Q_{2})\\}$. For this, let
$(Q_{1},Q_{2})$ be a pair of tuples harmonic with $Q$. Let
$\Gamma^{\prime}_{1}$ and $\Gamma^{\prime}_{2}$ be the sets of paths and
cycles we attain for $S[Q_{1}]$ and $S[Q_{2}]$, respectively, which are quasi-
planar and $O(1)$-packed. Also, let
$Q_{i}=(\Lambda_{i},V_{i},\mathcal{P}_{i})$. Let $\Gamma^{\prime}$ be the
union of $\Gamma_{1}^{\prime}$ and $\Gamma_{2}^{\prime}$. Since
$(Q_{1},Q_{2})$ is a tuple harmonic with $Q$, the subgraph of the union of
$\Gamma^{\prime}$ induced by $E[G_{t_{i}}]\cup\textsf{cut}({t_{i}})$ is
exactly $\Gamma_{i}^{\prime}$. Also, it is a set of disjoint paths and cycles
whose signature is $Q$. Therefore, $\Gamma^{\prime}$ is considered in the
computation of $S[Q]$, and thus the number of cycles of $\Gamma^{\prime}$
contained in $G_{t}$ is at most $S[Q]$.

Thus it is sufficient to analyze the number of cycles of $\Gamma^{\prime}$
with respect to $S[Q_{1}]$, $S[Q_{2}]$, and $c(Q_{1},Q_{2})$. Let
$\Lambda_{\textsf{u}}$ of the union of $\Lambda_{1},\Lambda_{2}$ and the edges
$uv$ with $\\{u,v\\}\in\mathcal{P}_{1}\cup\mathcal{P}_{2}$. We replace each
edge $uv$ of $\Lambda_{\textsf{u}}$ with $\\{u,v\\}\in\mathcal{P}_{i}$ with
the path in $\Gamma_{i}^{\prime}$ between $u$ and $v$. It is not difficult to
see that the resulting set $\Lambda_{\textsf{u}}$ is the union of
$\Gamma^{\prime}_{1}$ and $\Gamma^{\prime}_{2}$ excluding the cycles contained
in $G_{t_{i}}$ for $i=1,2$. The number of cycles contained in $G_{t_{i}}$ is
$S[Q_{i}]$ for $i=1,2$. A cycle intersecting both $G_{t_{1}}$ and $G_{t_{2}}$
contains a cut edge of $\textsf{cut}({t_{1}})\cap\textsf{cut}({t_{2}})$, and
it is a cycle of $\Lambda_{\textsf{u}}$, and thus the number of such cycles is
$c(Q_{1},Q_{2})$. Therefore, the inequality holds. ∎

Then we can compute $S[Q]$ for all valid tuples $Q$ in
$2^{O(\omega\log\omega)}n^{O(1)}$ time in total, and thus we can solve Cycle
Packing in $2^{O(\omega\log\omega)}n^{O(1)}$ time. Here, the bound on
$2^{O(\omega\log\omega)}$ comes from the number of different pairings
$\mathcal{P}$, and thus in the following section, we focus on decreasing the
number of different pairings $\mathcal{P}$ using the $O(1)$-packed property
and quasi-planar property of $\Gamma$.

###  9.2 Analysis of Crossing Patterns

In this subsection, we introduce a key idea of our improvement on the standard
DP algorithm. To do this, we analyze the crossing pattern of inter-cell cycles
of $\Gamma$ more carefully. The subgraph of $\Gamma$ induced by $V\cap A_{t}$
consists of paths and cycles, and each path has both endpoints in
$V(\textsf{cut}({t}))$. Let $\Pi$ be the set of path components of the
subgraph of $\Gamma$ induced by $V\cap A_{t}$. Notice that a path of $\Pi$ is
part of an inter-cell cycle of $\Gamma$ since intra-cell cycles contain no
edge of $V(\textsf{cut}({t}))$. For a path $\pi$ of $\Pi$, the path obtained
from $\pi$ by adding the two cut edges incident to $\pi$ at the end of $\pi$
is denoted by $\stackon[-4.2pt]{\pi}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$. Notice that it is
possible that $\stackon[-4.2pt]{\pi}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$ is a cycle.

In the following, we define the ordering of paths $\pi$ of $\Pi$ with respect
to a crossing point between
$\stackon[-4.2pt]{\pi}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$ and $\partial A_{t}$.
For this purpose, let $\bar{\pi}$ be the path (polygonal curve) obtained from
$\stackon[-4.2pt]{\pi}{\,\smash{\stackon[-1.95pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}$ by removing parts of
its end edges maximally such that the endpoints of $\bar{\pi}$ lie on
$\partial A_{t}$. We call $\bar{\pi}$ the _anchored path_ of $\pi$. Let
$\bar{\Pi}$ be the set of the anchored paths of the paths of $\Pi$. A path of
$\bar{\Pi}$ is fully contained in $A_{t}$ by the definition of
$\textsf{cut}({t})$.

##### Simple case: $\partial A_{t}$ is a single curve.

Given a fixed set $P$ of $O(\omega)$ vertices on $\partial A_{t}$ (which is
indeed $\textsf{end}(\bar{\Pi})$), our goal is to compute a small number of
pairings of $P$ one of which is a correct pairing of $\bar{\Pi}$. We first
focus on the simple case that all points of $\textsf{end}(\bar{\Pi})$ lie on a
single boundary curve $C$ of $A_{t}$. We can compute $2^{O(\omega)}$ pairings
one of which is a correct pairing as follows. For a path $\bar{\pi}$ of
$\bar{\Pi}$, we represent it as the pair of its end vertices on $C$. Then the
circular arc crossing graph of all pairs of $\bar{\Pi}$ is isomorphic to a
subgraph of the intersection graph of $\Pi$, and thus it is $K_{z,z}$-free by
the quasi-planar property. That is, for any two paths $\bar{\pi}$ and
$\bar{\pi}^{\prime}$ of $\bar{\Pi}$, one ending at $a$ and $b$, and one ending
at $a^{\prime}$ and $b^{\prime}$, if $a,a^{\prime},b$ and $b^{\prime}$ appear
along $C$ in this order, the two paths must cross as they cannot cross
$\partial A_{t}$. Using this, we simply enumerate all pairings of $P$ whose
corresponding circular arc graphs are $K_{z,z}$-free by Lemma 8. The number of
such pairings is $2^{O(|P|)}=2^{O(\omega)}$, and we can compute them in
$2^{O(\omega)}$ time.

##### General case: $\partial A_{t}$ has more than one curves.

Now we consider the general case where two endpoints of $\bar{\pi}$ are
contained in different boundary curves of $\partial A_{t}$. In particular, let
$(C,C^{\prime})$ be a pair of boundary curves of $A_{t}$. To handle the paths
$\bar{\pi}_{x,y}$ of $\bar{\Pi}$ with $x\in C$ and $y\in C^{\prime}$, we
connect $C$ and $C^{\prime}$ with an arbitrary curve
$\lambda=\lambda(C,C^{\prime})$. This curve intersects $C$ and $C^{\prime}$
only at its endpoints and does not contain any endpoints of the paths of
$\bar{\Pi}$. Subsequently, we obtain the closed curve consisting of
$C,C^{\prime}$ and $\lambda$ such that $\lambda$ appears in the closed curve
twice. Since none of the endpoints of a path in $\bar{\Pi}$ lie on $\lambda$,
we can orderly arrange the endpoints of paths in $\bar{\Pi}$ such that each
path has one endpoint on $C$ and the other on $C^{\prime}$. This arrangement
follows along the described closed curve, which consists of $\lambda$, $C$,
and $C^{\prime}$.

We will show that for two paths $\bar{\pi}_{x,y}$ and
$\bar{\pi}_{x^{\prime},y^{\prime}}$ with $x,x^{\prime}\in C$ and
$y,y^{\prime}\in C^{\prime}$, if they are cross-ordered, and their _crossing
numbers_ are the same in modulo 2, then $\bar{\pi}_{x,y}$ and
$\bar{\pi}_{x^{\prime},y^{\prime}}$ cross. Here, the crossing number of a path
$\bar{\pi}_{x,y}$ with $x\in C$ and $y\in C^{\prime}$ is defined as the number
of times that $\bar{\pi}_{x,y}$ crosses $\lambda(C,C^{\prime})$. Note that