# Parameterized Algorithm for the Planar Disjoint Paths Problem: Exponential
in $k^{2}$, and Linear in $n$111This work was supported by the National
Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT)
(No.2020R1C1C1012742).

Kyungjin Cho222Pohang University of Science and Technology, Korea. Email:
<EMAIL_ADDRESS>Eunjin Oh333Pohang University of Science and
Technology, Korea. Email<EMAIL_ADDRESS>Seunghyeok Oh444Pohang
University of Science and Technology, Korea. Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the Planar Disjoint Paths problem: Given an undirected
planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs
$(s_{i},t_{i})_{i=1}^{k}$ of vertices, the goal is to find a set $\mathcal{P}$
of $k$ pairwise vertex-disjoint paths connecting $s_{i}$ and $t_{i}$ for all
indices $i\in\\{1,\ldots,k\\}$. We present a $2^{O(k^{2})}n$-time algorithm
for the Planar Disjoint Paths problem. This improves the two previously best-
known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics
1995] and $2^{O(k^{2})}n^{6}$-time algorithm [STOC 2020].

##  1 Introduction

In this paper, we study the Disjoint Paths problem on planar graphs: Given an
undirected graph $G$ with $n$ vertices and a set $T$ of $k$ pairs
$(s_{i},t_{i})_{i=1}^{k}$ of vertices, the goal is to find a set $\mathcal{P}$
of $k$ pairwise vertex-disjoint paths connecting $s_{i}$ and $t_{i}$ for all
indices $i\in\\{1,\ldots,k\\}$. This problem has been studied extensively due
to its numerous applications such as VLSI layout and circuit routing [13].
However, this problem is NP-complete even for grid graphs [6]. This motivates
the study of this problem from the viewpoint of parameterized algorithms and
approximation algorithms. For approximation algorithms, we wish to connect as
many terminal pairs as possible using vertex-disjoint paths in polynomial
time. The best known approximation algorithm has approximation ratio
$O(\sqrt{n})$ [19]. In the case that the input graph is restricted to be
planar, the best known approximation ratio is $O(n^{9/19}\log^{O(1)}n)$ [5].
On the other hand, under reasonable complexity-theoretic assumptions, no
polynomial-time algorithm has approximation factor better than
$2^{\Omega(\sqrt{\log n})}$ [7].

The Disjoint Paths problem has been also studied extensively from the
viewpoint of parameterized algorithms. Here, the goal is to design an
algorithm which runs in $f(k)\cdot n^{O(1)}$ time for a function $f$, where
$k$ is the number of terminal pairs. The seminal work of Roberson and Seymour
[24] showed that this problem can be solved in $f(k)\cdot n^{3}$ time for a
computable function $f$. Although this algorithm is powerful, the original
proof of Roberson and Seymour requires the full power of the Graph Minor
Thoery. For this reason, Kawarabayashi and Wollan [18] presented a simpler
proof of correctness of the algorithm in [24]. Later, this algorithm was
improved by Kawarabayashi et al. [16] to run in $h(k)\cdot n^{2}$ time for a
computable function $h$. However, the dependence on $k$ is still huge both in
[16, 24]. Moreover, the explicit bound on the dependence on $k$ is not known.

For this reason, the Disjoint Paths problem has been studied extensively for
planar graphs [1, 9, 21, 23, 25]. In this case, we call the problem the Planar
Disjoint Paths problem. Note that there are two components of the running
times of parameterized algorithms: the dependency on the parameter $k$ and the
dependency on the input size $n$. Reed [23] focused on the dependence on the
input size, and gave a $2^{2^{O(k)}}n$-time algorithm for the Planar Disjoint
Paths problem. On the other hand, Lokshtanov et al. [21] focused on the
dependence on the parameter $k$, and gave a $2^{O(k^{2})}n^{6}$-time algorithm
for this problem.555The two papers [23] and [21] do not give explicit bounds
on the dependent on $k$ and dependent on $n$, respectively. But it is not
difficult to see that these algorithms run in $2^{2^{\Theta(k)}}n$-time and
$2^{\Theta(k^{2})}n^{6}$-time, respectively. A natural question posed here is
to achieve both best dependency on $k$ and the best dependency on $n$
simultaneously.

As mentioned in [22], this direction of research is indeed as old as the field
of parameterized algorithms. The result of Bodlaender [3] on on the problem
for computing a treewidth of a graph belongs to this class of results. Also,
the $f(k)\cdot n^{3}$-time and $h(k)\cdot n^{2}$-time algorithms for the
Disjoint Paths problem by Roberson and Seymour [24] and by Kawarabayashi et
al. [16], respectively, belong to this class of results. There are more recent
results in this direction, for instance, Odd Cycle Transversal [14, 17],
Subgraph Isomorphism [11], Planarization [15], and Treewidth [20].

In this paper, we present an algorithm for the Planar Disjoint Paths problem
which runs in $2^{O(k^{2})}n$ time. This improves both the
$2^{2^{O(k)}}n$-time algorithm by Reed [23] and the $2^{O(k^{2})}n^{6}$-time
algorithm by Lokshtanov et al. [21]. Our contribution in this paper can be
summarized as follows.

######  Theorem 1.

The Planar Disjoint Paths problem can be solved in $2^{O(k^{2})}n$ time.

##  2 Preliminaries

An instance of the Planar Disjoint Paths problem is a tuple $(G,T,k)$ where
$G$ is a plane graph, $T$ is a set $\\{(s_{1},t_{1}),\ldots,(s_{k},t_{k})\\}$
of $k$ vertex pairs. Here, the embedding of $G$ is fixed. We let $\bar{T}$ be
the set of all vertices in the pairs of $T$, and we call such vertices the
_terminals_.

A _walk_ $\omega$ is a sequence of edges which joins a sequence of vertices.
If all vertices and all edges of $\omega$ are distinct, we call $\omega$ a
_path_. A _$T$ -linkage_ is an ordered family $\langle
P_{1},\ldots,P_{k}\rangle$ of $k$ _vertex-disjoint_ paths in $G$ such that
$P_{i}$ connects $s_{i}$ and $t_{i}$ for $i\in\\{1,\ldots,k\\}$. We say two
paths $P$ and $P^{\prime}$ are _crossing_ if there are four edges
$e,f,e^{\prime},f^{\prime}$ of $G$ sharing a common endpoint such that $e,f$
are consecutive edges of $P$, $e^{\prime},f^{\prime}$ are consecutive edges of
$P^{\prime}$, and $e,f,e^{\prime}$ and $f^{\prime}$ lie in clockwise order
around their common endpoint. A _weak $T$-linkage_ $\mathcal{W}$ is an ordered
family $\langle P_{1},\ldots,P_{k}\rangle$ of $k$ pairwise _non-crossing_
walks in $G$ such that $P_{i}$ connects $s_{i}$ and $t_{i}$ for
$i\in\\{1,\ldots,k\\}$. If all edges of the walks of a weak $T$-linkage
$\mathcal{W}$ are distinct, we say $\mathcal{W}$ is _edge-disjoint_. We
sometimes call a $T$-linkage and a weak $T$-linkage for a set $T$ of terminal
pairs simply a _linkage_ and a _weak linkage_ , respectively, when we do not
need to specify $T$.

We use standard notions and terms for graphs as used in [4]. For instance, for
a graph $G$, we let $V(G)$ be the vertex set of $G$, and $E(G)$ be the edge
set of $G$. Also, throughout this paper, we use $[n]$ to denote the set
$\\{1,2,\ldots,n\\}$.

######  Definition 2.

A _tree decomposition_ of an undirected graph $G=(V,E)$ is defined as a pair
$(T,\beta)$, where $T$ is a tree and $\beta$ is a mapping from nodes of $T$ to
subsets of $V$ (called bags) satisfying the following properties. Let
$\mathcal{B}:=\\{\beta(t):t\in V(T)\\}$ be the set of bags of $T$.

  * •

For any vertex $u\in V$, there is at least one bag in $\mathcal{B}$ which
contains $u$.

  * •

For any edge $(u,v)\in E$, there is at least one bag in $\mathcal{B}$ which
contains both $u$ and $v$.

  * •

For any vertex $u\in V$, the nodes of $T$ containing $u$ in their bags are
connected in $T$.

The width of a tree decomposition is defined as the size of its largest bag
minus one, and the treewidth of $G$ is the minimum width of a tree
decomposition of $G$.

###  2.1 Radial Distance and Radial Curves

The _radial distance_ in $G$ between two faces $f_{1}$ and $f_{2}$ of $G$ is
defined as the minimum length of a sequence of faces starting from $f_{1}$ to
$f_{2}$, such that every two consecutive faces of this sequence share a common
vertex. Similarly, the radial distance between two vertices $u$ and $v$,
denoted by $\textsf{rdist}(u,v)$, is defined as the minimum radial distance
between two faces $F_{u}$ and $F_{v}$ incident to $u$ and $v$, respectively.
Note that there is a curve connecting $u$ and $v$ which meets $G$ only at
$\textsf{rdist}(u,v)$ vertices (excluding $u$ and $v$) and does not intersect
any edges of $G$. We call such a curve a _radial curve_ connecting $u$ and
$v$. See Figure 1(a). For two subsets $X$ and $Y$ of $V$, we define their
radial distance as the Hausdorff distance:
$\textsf{rdist}(X,Y)=\max\\{\max_{x\in X}\min_{y\in
Y}\textsf{rdist}(x,y),\max_{y\in Y}\min_{x\in X}\textsf{rdist}(x,y)\\}$. For
two subgraphs $P$ and $P^{\prime}$ of $G$, we define their radial distance as
$\textsf{rdist}(V(P),V(P^{\prime}))$.

An _innermost_ face $F^{*}$ of $G$ is defined as a face farthest from the
outer face with respect to the radial distance. We can compute $F^{*}$ in
linear time using a variant of the breadth-first search on $G$. Also, we call
a simple closed curve a _noose_ if it intersects $G$ only at vertices of $G$,
and does not intersect any edge of $G$. The complexity of a noose is defined
as the number of vertices of $G$ intersected by the noose. A similar notion we
use in this paper is a _face-edge path_ in $G$: an alternating sequence of
faces and edges such that every face is incident (in $G$) to the edges
neighboring in the sequence, and the two end elements of the sequence are
faces.

The _radial completion_ of $G$, denoted by $G^{\textsf{rad}}$, is a subgraph
of $G$ constructed as follows. We add one vertex for each face $F$ of $G$, and
connect this vertex and all vertices lying on $F$. Note that every face of
$G^{\textsf{rad}}$ is a triangle. See Figure 1(b). One can consider a radial
curve of length $N$ as a path in $G^{\textsf{rad}}$ of length $\Theta(N)$. We
use the radial completion to define the discrete homotopy in the following
subsection.

###  2.2 Homology and Flow Function

Schrijver [25] used the language of flows and homology to deal with linkages
and weak-linkages. As the algorithm of [25] works with directed graphs, we
consider $G$ as a directed graph by replacing each edge of $G$ with two
directed edges of $G$ with opposite directions. Also, we consider a walk of a
$T$-linkage of $G$ as oriented from $s_{i}$ to $t_{i}$. Let
$\Sigma=\\{1,2,\ldots,k\\}$ be an alphabet consisting of $k$ symbols, and let
$\Sigma^{-1}=\\{1^{-1},2^{-1},\ldots,k^{-1}\\}$. The group $\Sigma^{*}$
generated by $\Sigma$ consists of all strings $b_{1}b_{2}\ldots b_{t}$ with
$t\geq 0$ such that $b_{1},\ldots,b_{t}\in\Sigma\cup\Sigma^{-1}$ and
$b_{i}\neq{b_{i+1}^{-1}}$ for all indices $i\in[t)$. Then the product $x\cdot
y$ of two strings $x$ and $y$ in $\Sigma^{*}$ is defined as the string
obtained from the concatenation $xy$ by deleting iteratively all occurrences
of $s^{-1}s$ and $ss^{-1}$ for $s\in\Sigma$. The empty string is denoted by
$\epsilon$. Note that $xx^{-1}=x^{-1}x=\epsilon$ for any string
$x\in\Sigma^{*}$.

##### Flow Function and Linkages.

A flow function $\phi:E(G)\rightarrow\Sigma^{*}$ is defined as follows. For a
vertex $v$, let $e_{1},\dots,e_{\ell}$ be its incident edges in $G$ sorted in
the clockwise direction. Then $h(v)$ be the product of
$\phi(e_{r})^{\mu(e_{r})}$’s for all $r=1,2,\ldots,\ell$, where the sign
$\mu(e_{r})$ is positive if $e_{r}$ is an outgoing edge from $v$, and
negative, otherwise.666Note that $h(v)$ depends on the choice of $e_{1}$. To
avoid the ambiguity, we choose $e_{1}$ so that $|h(v)|$ is minimized. A
function $\phi$ is called a _flow function_ if $h(s_{i})=i$ for all $i\in[k]$,
$h(t_{i})=i^{-1}$ for all $i\in[k]$, and $h(v)=\epsilon$ for $v\notin\bar{T}$.
This is an algebraic interpretation of the standard flow-conservation
constraint.

An edge-disjoint weak $T$-linkage $\mathcal{W}$ can be considered as a _flow
function_ $\phi:E\to\Sigma^{*}$. Let $W_{i}$ be the path of $\mathcal{W}$
connecting $s_{i}$ and $t_{i}$ for $i\in[k]$. For each edge $e\in E(G)$, let
$\phi(e)=i$ if it is used in the path connecting $s_{i}$ to $t_{i}$, and let
$\phi(e)=\epsilon$ if it is not used by any path of $\mathcal{W}$. We say
$\phi$ is the flow function _representing_ $\mathcal{W}$. But it is possible
that a flow function $\phi$ represents more than two weak $T$-linkages of $G$.
For illustration, refer to Figure 2 of [21]. Schrijver [25] showed that a flow
function $\phi$ represents a $T$-linkage of $G$ if and only if
$\phi(\pi)\in\Sigma\cup\Sigma^{-1}$ for every face-edge path consisting of
faces and edges sharing a common vertex. Here, a face-edge path in $G$ is an
alternating sequence of faces and edges such that every face is incident (in
$G$) to the edges neighboring in the sequence.

##### Homology.

For a directed edge $e$ of $G$, we let $L_{e}$ denote the face lying to the
left of $e$, and let $R_{e}$ denote the face lying to the right of $e$. We say
two flow functions $\phi$ and $\psi$ are _homologous_ if there exists a
_homology_ function $f:\mathcal{F}\to\Sigma^{*}$, where $\mathcal{F}$ denotes
the set of all faces of $G$, such that

  * •

$f(F^{*})=\epsilon$, and

  * •

$(f(L_{e}))^{-1}\cdot\phi(e)\cdot f(R_{e})=\psi(e)$ for every directed edge
$e$.

###  2.3  Discrete Homotopy and Linkages

Instead of working with homology, Lokshtanov et al. [21] introduced a notion
of _discrete homotopy_ , which is a variant of the standard homotopy. When we
deal with discrete homotopy, we always work with the radial completion
$G^{\textsf{rad}}$ of $G$. Two weak linkages $\mathcal{W}$ and
$\mathcal{W}^{\prime}$ are _homotopic_ to each other if one can obtained from
the other weak linkage by a sequence of _face operations_. There are three
types of face operations: Face Move, Face Pull, and Face Push. Since our
argument uses Face Move and Face Pull only, we give the definitions of Face
Move and Face Pull only. The definition of Face Push can be found in [21,
Definition 5.3]. Each operation is applied to a face $F$ of $G^{\textsf{rad}}$
and a walk $W$ of $\mathcal{W}$. Let $\partial F$ be the cycle consisting of
the three edges incident to $F$. For illustration, see Figure 1(c–d).

Figure 1: (a) The red curve is a part of a radial curve. (b) The edges colored
red and the points marked with boxes are added to construct
$G^{\textsf{rad}}$. (c) The face move operation is applied to $(F,P)$. (d) the
face pull operation is applied to $(F,Q)$.

  * •

Face Move. The move operation is applicable to $(F,W)$ only when there is a
subpath $P$ of $\partial F$ of length at most two such that $P$ is a subwalk
of $W$, and no edge of $E(\partial F)\setminus E(P)$ belongs to any walk of
$\mathcal{W}$. In this case, we replace $P$ in $W$ by the unique subpath of
$\partial F$ between the endpoints of $P$ that is edge-disjoint from $P$.

  * •

Face Pull. The pull operation is applicable to $(F,W)$ only when $\partial F$
is a subwalk $Q$ of $W$. In this case, we replace $Q$ in $W$ by a single
occurrences of the first vertex in $Q$.

The following lemma connects the concept of discretely homotopy and the
concept of homology.

######  Lemma 3 ([21, Lemma 5.2]).

Let $\mathcal{W}$ and $\mathcal{W}^{\prime}$ be two weak linkages discretely
homotopic to each other. Then the flow function representing $\mathcal{W}$ is
homologous to the flow function representing $\mathcal{W}^{\prime}$.

##  3 Overview

In this section, we present an overview of our algorithm. To do this, we first
give a sketch of [21] in Section 3.1, and we then give a sketch of our
algorithm in Section 3.2. The two algorithms in [21] and [25] (and ours)
consist of the following two steps. Here, $h_{1},h_{2}$ and $h_{3}$ are
functions on $n$ and $k$.

  1. 1.

Enumerate $h_{1}$ weak $T$-linkages of $G$ one of which is homotopic to a
$T$-linkage of $G$ in $h_{2}$ time.

  2. 2.

Assuming that we have a _correct_ weak $T$-linkage $\mathcal{W}$, we compute a
$T$-linkage of $G$ in $h_{3}$ time.777In fact, we apply this algorithm for all
weak $T$-linkages we have computed (since we do not know which one is a
correct weak $T$-linkage), and we can obtain a $T$-linkage of $G$ when we
apply this algorithm to a correct weak $T$-linkage.

In the case of [25], the bounds of $h_{1},h_{2}$ and $h_{3}$ are
$n^{O(\sqrt{k})}$, $n^{O(\sqrt{k})}$, and $O(n^{6})$, respectively.888But this
algorithm also works for directed graphs. To deal with the second step, the
algorithm of [21] uses the algorithm in [25], and thus they have the same
bound on $h_{3}$. But using clever ideas, they significantly improves the
bounds of $h_{1}$ and $h_{2}$ to $2^{O({k^{2}})}$ and
$2^{O({k^{2}})}n+2^{O(k)}n^{2}$, respectively.

We also use the same high level structure. But we improve the bounds of
$h_{1},h_{2}$ and $h_{3}$ to $2^{O(k^{2})}$, $2^{O(k^{2})}n$, and $2^{O(k)}n$,
respectively. Therefore, the total running time of our algorithm is
$2^{O(k^{2})}n$.

###  3.1 Sketch of [21] and Obstacles in Designing a $2^{O(k^{2})}n$-time
Algorithm

We first give a brief sketch of the $2^{O(k^{2})}n^{6}$-time algorithm for the
Planar Disjoint Paths problem as we also use several tools used in [21]. At
the end of this subsection, we give three obstacles in improving this
algorithm to run in $2^{O(k^{2})}n$ time. Then we briefly show how we overcome
each of the obstacles in this paper.

####  3.1.1 Enumerating Homology Classes

The first step is to enumerate $2^{O(k^{2})}$ homology classes. Before doing
that, they remove several _irrelevant_ vertices from $G$ as a preprocessing
step. Given an instance $(G,T,k)$ of Planar Disjoint Paths, this algorithm
first removes several _irrelevant_ vertices from $G$ so that the answer of
$(G,T,k)$ remains the same, and the treewidth of $G$ decreases to $2^{O(k)}$.
Indeed, it is a common ingredient of all previous algorithms for Planar
Disjoint Paths, which is called the _irrelevant vertex technique_. More
specifically, a vertex $v$ of $G$ is said to be _irrelevant_ for $(G,T,k)$ if
$(G,T,k)$ is a YES-instance if and only if $(G-v,T,k)$ is a YES-instance,
where $G-v$ is the graph obtained from $G$ by removing $v$ and its incident
edges. Roberson and Seymour [24] showed that a planar graph having treewidth
$g(k)$ has an irrelevant vertex for a specific function $g(k)$. For this, they
showed that a planar graph with treewidth $O(w)$ has a $w\times w$ grid as a
minor. If $w\geq g(k)$ for a specific function $g(k)$, there is a grid minor
of $G$ of size $g(k)\times g(k)$ such that the innermost vertex of the grid
minor is irrelevant. Later, the bound of $g(k)$ was improved to
$O(k^{1.5}2^{k})$ by Adler et al. [1]. Therefore, by repeatedly removing
irrelevant vertices from $G$, we can obtain an equivalent instance
$(G^{\prime},T,k)$ where the treewidth of $G^{\prime}$ is $O(g(k))$. A single
irrelevant vertex can be found in linear time, and thus a naive implementation
of this technique yields a quadratic-time algorithm.

Figure 2: After pushing the paths to the tree in (a), we can obtain the the
walks in (b).

Now we assume that $G$ has treewidth $2^{O(k)}$. Using this, Lokshtanov et al.
[21] enumerated $2^{O(k^{2})}$ weak $T$-linkages one of which is discretely
homotopic to a $T$-linkage of $G$. To do this, they used a Steiner tree $R$ of
$\bar{T}$ in $G$, which they call the _backbone tree_ , having a certain
property. The backbone tree has $O(k)$ non-degree-2 vertices and $O(k)$
maximal paths consisting of degree-2 vertices only. A maximal degree-2 path is
said to be _long_ if its length is at least $2^{10k}$, and it is said to be
_short_ , otherwise. Then the total complexity of the short maximal degree-2
paths is $2^{O(k)}$. They showed that for every long maximal degree-2 path
$\pi$ of $R$, there are two nooses $S_{v}$ and $S_{u}$ of complexity
$2^{O(k)}$ such that $\textsf{rdist}(u,u^{\prime})$ and
$\textsf{rdist}(v,v^{\prime})$ is $2^{O(k)}$ for the vertices $v^{\prime}$ and
$u^{\prime}$ of $S_{v}$ and $S_{u}$, respectively, intersected by $\pi$, where
$u$ and $v$ are the endpoints of $\pi$. This property holds due to the
treewidth of $G$ is $2^{O(k)}$. In the following, we call the subpath of $\pi$
lying between $u$ and $u^{\prime}$ (and between $v$ and $v^{\prime}$) the
_prefixes_ of $\pi$. The subpath of $\pi$ excluding its prefixes is called the
_middle subpath_ of $\pi$.

If $(G,T,k)$ is a YES-instance of Planar Disjoint Paths, there exists a
$T$-linkage $\mathcal{P}$ of $G$ which can be pushed onto the edges of $R$ so
that the resulting walks on $R$ traverse each edge of $R$ $2^{O(k)}$ times.
See Figure 2. More specifically, Lokshtanov et al. [21] gave a canonical way
to push the paths of $\mathcal{P}$ onto the edges of $R$. Then $\mathcal{P}$
becomes a weak $T$-linkage of $G$ whose edges lie on the backbone tree $R$.
For this purpose, they cut each path of $\mathcal{P}$ into several _segments_
at the vertices intersected by the short maximal degree-2 paths and by the
prefixes of the long maximal degree-2 paths. The number of segments is
$2^{O(k)}$, and each segment $s$ forms a walk $\omega_{s}$ on $R$ when it is
pushed onto $R$. Each edge of $R$ appears exactly once on $\omega_{s}$ unless
$s$ intersects the middle path of a long maximal degree-2 path. Also, by a
clever choice of $\mathcal{P}$, they showed that $\omega_{s}$ also traverses a
single edge $2^{O(k)}$ times even in the case that $s$ intersects the middle
path of a long maximal degree-2 path.

This shows that, if $(G,T,k)$ is a YES-instance of Planar Disjoint Paths,
there is a weak $T$-linkage $\mathcal{W}$ of $G$ homotopic to a $T$-linkage of
$G$ such that the edges of the walks of $\mathcal{W}$ lie on $R$, and each
walk of $\mathcal{W}$ traverses a single edge $2^{O(k)}$ times in total. Using
this, they enumerate all weak $T$-linkages on $R$ such that each weak
$T$-linkage traverses a single edge $2^{O(k)}$ times. The number of all such
weak $T$-linkages is $2^{O(k^{2})}$.

In summary, they first compute a Steiner tree $R$ with a certain property in
$2^{O(k)}n^{2}$ time, and then enumerate all weak $T$-linkages on $R$ in
$2^{O(k^{2})}n$ time.

####  3.1.2 Finding a Solution Using a Given Weak Linkage

For each weak $T$-linkage computed from the previous stage, they apply the
algorithm by Schrijver [25]. Given a weak $T$-linkage $\mathcal{W}$ of $G$,
Schrijver [25] presented an $O(n^{6})$-time algorithm for computing a
$T$-linkage $\mathcal{P}$ of $G$ such that $\psi_{\mathcal{W}}$ is homologous
to $\psi_{\mathcal{P}}$, where $\phi_{\mathcal{W}}$ and $\phi_{\mathcal{P}}$
are flow functions representing $\mathcal{W}$ and $\mathcal{P}$, respectively.
Due to Lemma 3, this algorithm always returns a $T$-linkage
$\mathcal{P}^{\prime}$ of $G$ if there is a $T$-linkage $\mathcal{P}$
discretely homotopic to a given weak $T$-linkage $\mathcal{W}$.

Although Lokshtanov et al. [21] used this algorithm as a black box, we are
required to open up this black box to analyze the dependence on $n$ in the
running time of [21]. The goal here is to compute a flow function $\psi$
homologous to a given flow function $\phi$ such that $\psi$ represents a
$T$-_linkage_ of $G$. To control the number of edges with
$\psi(\cdot)\neq\epsilon$ incident to a common vertex, Schrijver [25]
introduced a more general problem setting: the _homology feasibility problem_.

In the homology feasiblity problem, we are given a flow function $\phi$, and a
candidate function $\Gamma:{\Pi}\to 2^{\Sigma^{*}}$, where $\Pi$ is a set of
face-edge paths. For a flow function $\psi$ and a face-edge path $\pi$, we let
$\psi(\pi)$ denote the product of $\psi(e)^{\mu(e)}$’s for all edges $e$ in
$\pi$, where the sign $\mu(e)$ is positive if $L_{e}$ is the face lying
previous to $e$ in $\pi$, and negative, otherwise. Then the goal is to compute
a flow function $\psi$ homologous to a given flow function $\phi$ such that
$\psi(\pi)\in\Gamma(\pi)$. In this case, the homology function $f$ for $\phi$
and $\psi$ is called a _feasible homology function_. Schrijver showed that a
flow function $\psi$ with $\psi(\pi)\in\Gamma(\pi)$ for all $\pi\in\Pi$
corresponds to a $T$-linkage if (i) $\Pi$ is the set of all face-edge paths
each consisting of faces and edges sharing a common vertex, and (ii)
$\Gamma(\pi)=\Sigma\cup\Sigma^{-1}$ for all $\pi\in\Pi$. Therefore, it
suffices to present an algorithm for the homology feasibility problem.

To solve the homology feasibility problem with $\Gamma$, the algorithm of [25]
first computes several _initial_ functions $f$’s, computes a specific function
$\bar{f}$ for each initial function $f$, and then takes the _join_ of
$\bar{f}$’s. Schrijver showed how to choose such initial functions $f$’s so
that the join of $\bar{f}$’s is a feasible homology function. Given an initial
function $f$, Schrijver showed how to compute $\bar{f}$ in $O(n\eta|\Pi|)$
time, where $\eta$ denotes the maximum length of $\bar{f}$ for all initial
functions $f$. Moreover, the initial functions can be computed in time
quadratic in the number $\chi$ of face-edge paths $\pi$ of $\Pi$ with
$\phi(\pi)\notin\Gamma(\pi)$, and the number of initial functions is linear in
$\chi$. Therefore, the total running time is
$O(\chi^{2}+n\cdot\eta\cdot\chi\cdot|\Pi|)$.

In the case of the weak $T$-linkages obtained from [21], $|\Pi|$ and $\chi$
are $\Theta(n^{2})$ since the number of vertices of $R$ is $O(n)$ and the
degree (in $G$) of each vertex of $R$ is $\Theta(n)$ in the worst case. Also,
$\eta$ is $\Theta(n)$ in the worst case since the maximum radial distance
between the outer face of $G$ and the vertices of $R$ is $\Theta(n)$ in the
worst case. Therefore, the total running time of [21] is $2^{O(k^{2})}n^{6}$.

####  3.1.3 Obstacles in Designing a $2^{O(k^{2})}n$-time Algorithm and Our
Methods

There are three places where a super-linear dependence on $n$ appears: the
application of the irrelevant vertex technique takes $2^{O(k)}n^{2}$ time, the
computation of the backbone tree takes $O(n^{2})$ time, and the algorithm of
[25] takes $O(n^{6})$ time. Although a fine-grained analysis of the algorithm
of [25] gives the bound of $O(\chi^{2}+n\cdot\eta\cdot\chi\cdot|\Pi|)$, the
values of $\chi,\eta$ and $|\Pi|$ are too large in the case of the weak
$T$-linkages $\mathcal{W}$ constructed from [21]. This is because the number
of edges of $R$ is $\Theta(n)$, and the maximum radial distance from the outer
face to the vertices of $R$ is $\Theta(n)$ in the worst case.

One possible direction for obtaining a faster algorithm for the Planar
Disjoint Paths problem is to construct weak $T$-linkages with respect to some
other backbone structure of complexity of $2^{O(k)}$ instead of constructing
them with respect to the backbone tree. Then (after modifying $G$ slightly),
we can show that this decreases $\chi$ to $2^{O(k)}$, and thus this leads to
an algorithm running in $2^{O(k^{2})}n^{5}$ time. This was our starting point.

##### New Backbone Structures.

We first construct a backbone structure (a subgraph of $G^{\textsf{rad}}$) of
complexity of $2^{O(k)}$ in $2^{O(k)}n$ time, and then show that all paths of
$\mathcal{P}$ can be pushed onto the backbone structure (and several
precomputed paths) for a $T$-linkage $\mathcal{P}$. In this paper, we call
this backbone structure the _frames_ and _skeleton forests_ , which will be
defined later. In this way, each edge on the backbone structure is traversed
by the resulting walks $2^{O(k)}$ times in total. Also, each edge on the
precomputed paths is traversed by the resulting walks at most once in total.
This allows us to only consider the weak $T$-linkages using each edge of the
backbone structure $2^{O(k)}$ times and each edge of the precomputed paths
exactly once. There are $2^{O(k^{2})}$ such weak $T$-linkages $\mathcal{W}$,
and we can enumerate each of them in $2^{O(k)}n$ time. By slightly modifying
$G$ with respect to a given weak $T$-linkage, we can make each vertex of the
backbone structure have degree $2^{O(k)}$ (without changing the answer of the
instance). Then the number $\chi$ of face-edge paths $\pi$ of $\Pi$ with
$\phi(\pi)\notin\Gamma(\pi)$ decreases to $2^{O(k)}$. In this way, we can
overcome the second obstacle: we can construct the backbone structure in
$2^{O(k)}n$ time (although we define the backbone structure in a different
way.) Also, we can partially overcome the third obstacle: now the algorithm of
[25] takes $O(n^{5})$ time in our case.

##### Maintaining a Data Structure.

There remain obstacles to be handled to obtain a $2^{O(k^{2})}n$ time
algorithm. First, due to properties of the backbone structure we defined, we
can show that the length of $\bar{f}(F)$ of all initial functions $f$
constructed from [25] is $2^{O(k)}$. But even in our case, $|\Pi|$ can be
$2^{\Theta(k)}n$ as the total number of edges of the walks of $\mathcal{W}$
can be $2^{\Theta(k)}n$. We resolve this issue by designing a suitable data
structure and implementing the algorithm of [25] using this data structure. In
this way, we can fully overcome the third obstacle: Given a _correct_ weak
$T$-linkage of $G$ defined with respect to the backbone structure (frames and
skeleton forests), we can compute a $T$-linkage of $G$ in $2^{O(k)}n$ time.

##### Irrelevant Vertex Technique.

The remaining obstacle is to remove irrelevant vertices so that $G$ has
treewidth $2^{O(k)}$ in $2^{O(k)}n$ time in total. We overcome this obstacle
by removing irrelevant vertices while subdividing $G$ into several pieces.
This idea was already used in [23], but this work focused on designing
$2^{O(k^{2})}n$ time algorithm for the Planar Disjoint Paths problem. We apply
the algorithm [23] first, and then we are given $2^{O(k)}$ pieces (subgraphs
of $G$) enclosed by a closed curve such that no terminal is contained in the
_interior_ of each piece. Then we remove all vertices in each piece whose
radial distance is at least $2^{ck}$ from the boundary vertices of the piece
for a specific constant $c$ in time linear in the complexity of the piece. We
show that all such vertices are irrelevant for $(G,T,k)$, and the resulting
graph has treewidth $2^{O(k)}$.

###  3.2 Our Methods

In this subsection, we give a more detailed sketch of our algorithm. We first
apply the irrelevant technique in $2^{O(k)}n$ time so that the resulting graph
$G$ has treewidth $2^{O(k)}$. This algorithm is described in Section 4. In the
following, we assume that the treewidth of $G$ is $2^{O(k)}$. A key idea of
our algorithm is summarized in the following lemma. The definitions of frames,
forests and reference paths will be given in Section 3.2.1 and Section 5.
Section 5, Section 6 and Section 7 are devoted to prove the following lemma.

######  Lemma 4.

We can enumerate $2^{O(k^{2})}$ weak linkages $\mathcal{W}$ in $2^{O(k^{2})}n$
time one of which is discretely homotopic to a $T$-linkage of $G$ such that

  * •

the edges of the walks of $\mathcal{W}$ lie on the _frames_ , _skeleton
forests_ , and _reference paths_ ,

  * •

each edge of the frames and skeleton forests is traversed by the walks of
$\mathcal{W}$ $2^{O(k)}$ times, and

  * •

each edge of the the reference paths is traversed by the walks of
$\mathcal{W}$ at most once.

####  3.2.1 Frames, Skeleton Forests, and Reference Paths

To prove Lemma 4, we first define the _frames_ and _skeleton forests_ in
Section 5. A frame is a noose of complexity $2^{O(k)}$, and we construct
$O(k)$ _concentric_ frames. They subdivide $G$ into $O(k)$ _framed rings_ each
of which is a subgraph of $G$ lying between two consecutive frames. A framed
ring containing a terminal and a framed ring not containing a terminal appear
alternatively. For illustration, see Figure 10.

##### Framed Ring Containing a Terminal.

For a framed ring containing a terminal, the radial distance between its two
boundary frames is $2^{O(k)}$. This allows us to encode the interaction
between $\mathcal{P}$ and a framed ring $\textsf{Ring}^{\textsf{o}}$
containing a terminal in a compact way. To do this, we cut
$\textsf{Ring}^{\textsf{o}}$ along the radial curves from each terminal to the
outer boundary of $\textsf{Ring}^{\textsf{o}}$ so that the terminals lie on
the boundary of the resulting subgraph. This approach is also used in [12] for
computing shortest non-crossing walks in a planar graph. For illustration, see
Figure 14. The union of the radial curves forms a forest, and we call it the
_skeleton forest_ of $\textsf{Ring}^{\textsf{o}}$. In Section 6, we push the
parts of the paths of $\mathcal{P}$ contained in $\textsf{Ring}^{\textsf{o}}$
onto the skeleton forest to obtain the _canonical $T$-linkage_. Then as in
[12, 21], we can encode the interaction between the canonical weak $T$-linkage
and $\textsf{Ring}^{\textsf{o}}$ using $O(k\cdot k_{i})$ bits, where $k_{i}$
denotes the number of terminals contained in $\textsf{Ring}^{\textsf{o}}$.

##### Framed Ring Containing No Terminal.

On the other hand, for a framed ring $\textsf{Ring}^{\textsf{x}}$ not
containing a terminal, the radial distance between its two boundary frames can
be as large as $\Theta(n)$. However, in this case, the number of maximal
subpaths $\pi$ of the paths of $\mathcal{P}$ contained in
$\textsf{Ring}^{\textsf{x}}$ is $2^{O(k)}$. For a maximum-cardinality set
$\mathcal{Q}$ of disjoint paths in $\textsf{Ring}^{\textsf{x}}$ between the
two boundary frames, the absolute value of the _winding number_ between $\pi$
and a path of $\mathcal{Q}$ is $2^{O(k)}$.999More precisely, there is a
$T$-linkage, which we call the _base_ $T$-linkage, satisfying this property.
Using this observation, we precompute a maximum-cardinality set $\mathcal{Q}$
of disjoint paths between the two boundary frames. We call the paths of
$\mathcal{Q}$ the _reference paths_. Then in Section 6, we push the parts of
the paths of $\mathcal{P}$ contained in $\textsf{Ring}^{\textsf{x}}$ onto the
frames and the paths of $\mathcal{Q}$.101010In fact, the story is more
complicated here. It is not easy to apply the two techniques simultaneously
(the technique for bounding the winding number between $\pi$ and a path of
$\mathcal{Q}$, and the technique for pushing the paths onto the frames and
paths of $\mathcal{Q}$). To handle this issue, we define subframes, which are
cycles lying close to the frames, and then define $\mathcal{Q}$ as a maxmimum-
cardinality set of paths connecting two subframes. We show that the resulting
walks use each edge of the frames $2^{O(k)}$ times, and use each edge of the
paths of $\mathcal{Q}$ at most once. Then we can encode the interaction
between the canonical weak $T$-linkage and $\textsf{Ring}^{\textsf{x}}$ using
$O(k)$ bits.

In summary, only $O(k^{2})$ bits are required to encode the interaction
between the framed rings and the canonical weak $T$-linkage. Therefore, we can
enumerate $2^{O(k^{2})}$ weak linkages one of which is the canonical weak
$T$-linkage as described in Section 7. Note that the canonical $T$-linkage
satisfies the properties stated in Lemma 4. Using these properties, we can
show that given the canonical weak $T$-linkage, we can compute a $T$-linkage
of $G$ in $O(n)$ time in Section 8.

####  3.2.2 Finding a Solution Using a Given Weak Linkage

Given a weak $T$-linkage $\mathcal{W}$ of $G$ satisfying the properties stated
in Lemma 4, we first compute the flow function $\phi$ representing
$\mathcal{W}$. Then we let $\Pi$ be the set of all face-edge paths each
consisting of faces and edges sharing a common vertex, and let
$\Gamma:\Pi\to\Sigma^{*}$ be the function with
$\Gamma(\pi)=\Sigma\cup\Sigma^{-1}$ for all $\pi\in\Pi$. By applying the
algorithm in [25], we can compute a flow function $\psi$ homologous to $\phi$
with $\psi(\pi)\in\Gamma(\pi)$. By the argument of [25], $\psi$ represents a
unique $T$-linkage $\mathcal{P}$ of $G$, and thus we can obtain $\mathcal{P}$
from $\psi$ in linear time.

As mentioned in Section 3.1.2, we can show that the running time of the
algorithm in [25] is $O(\chi^{2}+n\cdot\eta\cdot\chi\cdot|\Pi|)$. Here, $\chi$
is the number of face-edge paths $\pi$ of $\Pi$ with
$\phi(\pi)\notin\Gamma(\pi)$, and $\eta$ is the maximum length of $\bar{f}$
for all _initial_ functions $f$.111111The definition of the initial functions
is given in Section 8.1. The value of $\chi$ is
$2^{O(k)}\cdot\textsf{MaxDeg}$, where MaxDeg denotes the maximum degree in $G$
of the vertices on the frames and skeleton forests. At this point, MaxDeg can
be as large as $\Theta(n)$.

##### Modification of $G$ to $G_{\textsf{mod}}$.

To handle this issue, we modify $G$ slightly so that MaxDeg decreases to
$2^{O(k)}$ in Section 8.2. We say an edge $e$ is _linkage-edge_ if a walk of
$\mathcal{W}$ uses $e$. For a vertex $v$ of $G$, let $d_{W}(v)$ be the number
of linkage-edges incident to $v$. Also, let $d_{G}(v)$ be the degree of $v$ on
$G$. We say an edge $e$ lies _between $e_{1}$ and $e_{2}$_ if $e$, $e_{1}$,
and $e_{2}$ are incident to a common vertex $v$, and $e$ lies from $e_{1}$ to
$e_{2}$ in clockwise direction around $v$. Two linkage-edges $e$ and
$e^{\prime}$ incident to $v$ form a _wedge at $v$_ if there is no other
linkage-edge between $e$ and $e^{\prime}$. Furthermore, the wedge contains all
edges between $e$ and $e^{\prime}$, and all wedges at $v$ are pairwise
interior-disjoint. See Figure 16. Clearly, there are at most $d_{W}(v)$ wedges
at a vertex $v$. We say a wedge at $v$ is _empty_ if no edge of $G$ incident
to $v$ is contained in the wedge.

For each non-empty wedge at a vertex $v$ in the frames and skeleton forests,
we insert a new vertex $v^{\prime}$ to $G$, and add the edge between $v$ and
$v^{\prime}$. Then we remove the edges in the wedge, and reconnect them to
$v^{\prime}$ instead of $v$. Note that, the edges incident to a new vertex
$v^{\prime}$ are not linkage-edges. We do this for all non-empty wedges and
all vertices in the frames and skeleton forests. This takes $O(n)$ time in
total since the total degree of all vertices in the frames and skeleton
forests is $O(n)$. Clearly, there is a one-to-one correspondence between two
linkages (and weak linkage) on $G$ and on $G_{\textsf{mod}}$. Due to the
modification, the running time of [25] is improved to $2^{O(k)}\cdot
n\cdot\eta\cdot|\Pi|$.

##### Further Improvement.

We improve further the running time of [25] to $2^{O(k)}\cdot
n\cdot\eta\cdot|\Pi|$ in Section 8.3. First, using a suitable data structure,
we improve the running time to $2^{O(k)}n\cdot\eta$. More specifically, the
algorithm of [25] computes $2^{O(k)}$ initial functions $f$, and then computes
a function $\bar{f}$, which is called a _smallest pre-feasible function_ , for
each initial function $f$. The procedure for computing $\bar{f}$ consists of
$O(n\eta)$ iterations, and in each iteration, we update the value of $f(F)$
for a specific face $F$. Here, each iteration takes $O(|\Pi|)$ time because we
are required to find a face-edge path $\pi\in\Pi$ with
$f(F)^{-1}\cdot\phi(\pi)\cdot\phi(F^{\prime})\notin\Gamma(\pi)$ and
$f(F)\neq\epsilon$, where $F$ and $F^{\prime}$ are the end faces of $\pi$.
Then we update the value of $f(F)$ or $f(F^{\prime})$ accordingly. Instead of
considering all face-edge paths in $\Pi$, we can find such a face-edge path
$\pi$ in amortized constant time by maintaining a suitable data structure.
This improves the running time to $2^{O(k)}n\cdot\eta$.

Finally, we show that $\eta=2^{O(k)}$ by introducing $O(k)$ new constraints to
$\Pi$, one per frame. Before doing that, we first observe that for any weak
$T$-linkage $\mathcal{W}$ represented by $f$, there is a weak $T$-linkage
represented by $f^{\prime}$ discretely homotopic to $\mathcal{W}$, where
$f^{\prime}$ is a function obtained from $f$ during the process of computing
$\bar{f}$. This is simply because each iteration of the process is indeed a
face operation. Moreover, due to the new constraints, the part of
$\mathcal{W}$ contained in a framed ring Ring is discretely homotopic to the
part of $\mathcal{W}^{\prime}$ contained in ring Ring. Using this property, we
show that $\eta$ is $2^{O(k)}$ in the proof of Lemma 33.

In summary, we first apply the irrelevant technique to $G$ in $2^{O(k)}n$ time
so that $G$ has treewidth of $2^{O(k)}$ in Section 4. We construct the frames,
skeleton forests, and reference paths in $2^{O(k)}n$ time in Section 5 and
Section 6. Using them, we enumerate $2^{O(k^{2})}$ weak $T$-linkages
satisfying the properties stated in Lemma 4 in $2^{O(k^{2})}n$ time. Then for
each weak $T$-linkage, we apply the algorithm of [25] after modifying $G$
slightly in $2^{O(k)}n$ time in total as described in Section 8. In this way,
we can solve the Planar Disjoint Paths problem in $2^{O(k^{2})}n$ time.

##  4 Irrelevant Vertex Technique

In this section, we remove sufficiently many irrelevant vertices from $G$ to
reduce the treewidth of $G$ to $2^{O(k)}$. Using this algorithm as a
preprocessing step, we may assume that $G$ has treewidth $2^{O(k)}$ in the
following sections. A _$c$ -punctured plane_ $\boxdot$ is the region obtained
by removing $c$ open holes from the plane. The boundary of $\boxdot$ is the
union of the boundaries of the open holes of $\boxdot$ and a vertex of $G$
lying on the boundary of $\boxdot$ is called a boundary vertex. Let $G$ be a
plane graph, and $T$ be a set of terminal pairs. We consider a point where
each terminal lies as a (trivial) hole. In this way, we can obtain a
$2k$-punctured plane $\boxdot$ such that the terminals of $T$ lie on the
boundary of $\boxdot$.

We say vertex-disjoint cycles $C_{1},\ldots,C_{\ell}$ of $G$ are _concentric_
if $C_{i}$ is contained in the interior of $C_{i+1}$ for all $i\in[\ell-1]$. A
cycle $C$ _separates_ a vertex $u$ and a vertex set $W$ if $u$ is contained in
the interior (or exterior) of $C$, and $W$ is contained in the exterior (or
interior) of $C$. Furthermore, a vertex $v$ is said to be $\ell$-_isolated_ if
there are $\ell$ concentric cycles each separating $v$ and $\bar{T}$.

######  Lemma 5 (Lemmas 1 and 10 in [1]).

There exists a function $g(k)\in O(k^{1.5}2^{k})$ which every $g(k)$-isolated
vertex in $G$ is irrelevant for the instance $(G,T,k)$ of Planar Disjoint
Paths.

In the following, let $g(k)$ be the function in $O(k^{1.5}2^{k})$. Our
strategy is to decompose $G$ into $2^{O(k)}$ _nice_ subgraphs $H$ each
embedded on a 1-punctured plane after removing several $g(k)$-isolated
vertices from $G$. A subgraph $H$ of $G$ embedded on a $c$-punctured plane is
said to be _nice_ if any cycle $C$ of $H$ separating a vertex $v$ of $H$ and
the boundary vertices of $H$ also separates $v$ and $\bar{T}$ in $G$. Then a
vertex in $H$ separated from the boundary vertices of $H$ by $g(k)$ concentric
cycles is $g(k)$-isolated in $G$. Thus we are allowed to delete such vertices
from $H$.

Figure 3: (a) The white areas are open holes, and the points of their
boundaries are terminals. The cycle $C$ separates $v$ from the boundary
vertices, and it also separates $v$ from the terminals. (b) The gray area has
vertices of $V_{i}$ for $i=g(k)+1,\ldots,n^{\prime}$. These vertices
$g(k)$-isolated. (c) A nice subgraph embedded on a $1$-punctured plane
$\boxdot$ after removing all $g(k)$-isolated vertices has treeewidth at most
$g(k)$.

We first show how to remove irrelevant vertices from a nice subgraph $H$
embedded on a 1-punctured plane in Section 4.1. Then we show how to decompose
$G$ into nice subgraphs each embedded on a 1-punctured plane in Section 4.2.

###  4.1 A Nice Subgraph Embedded on a 1-Punctured Plane

We are given a nice subgraph $H$ of $G$ embedded on a 1-punctured plane
$\boxdot$. Then we show how to remove $g(k)$-isolated vertices from $H$ so
that $H$ has treewidth $2^{O(k)}$. Our algorithm is simple: we remove all
vertices sufficiently far from the boundary vertices of $H$ _with respect to
the radial distance_. Let $V_{i}$ be the set of vertices $v$ of $H$ such that
the minimum radial distance between $v$ and a boundary vertex of $H$ is
exactly $i$. That is, $V_{0}$ is the set of boundary vertices of $H$, and
$V_{i+1}$ is the set of vertices not in $V_{i}\cup V_{i-1}$ lying on a face
incident to a vertex of $V_{i}$. We can partition $V(H)$ into $V_{0},\ldots
V_{n^{\prime}}$ in this way in time linear in the complexity of $H$ using a
_doubly connected edge list_ of $H$, which a data structure for representing
an embedding of a planar graph [10].

######  Lemma 6.

A vertex in $V_{i}$ is $(i-1)$-isolated for $i\in[n^{\prime}]$.

Proof. We prove the lemma inductively. For the base case that $i=1$, the lemma
holds immediately since every non-terminal vertex is $0$-isolated.

We assume that the lemma holds for vertices in $\cup_{j\leq i}V_{j}$, and
consider a vertex $v$ in $V_{i+1}$ for $i\geq 1$. Note that no edge of $H$
connects two vertices each in $V_{0}$ and $V_{j}$, respectively, for any
$j\geq 2$. Moreover, every path in $H$ connecting a boundary vertex of $V_{0}$
and $v$ intersects $V_{1}$. This means there exists a cycle $C$ in $H[V_{1}]$
which separates $V_{0}$ and $v$ in $H$. Imagine that we remove from $H$ all
vertices separated by $C$ from $v$. Then the resulting graph $H^{\prime}$ can
be considered as a plane graph embedded on a 1-punctured plane such that the
vertices of $V(C)$ are the boundary vertices of $H^{\prime}$. Therefore, there
are $(i-1)$ concentric cycles separating $v$ and $V_{1}$ in $H^{\prime}$ (and
thus in $H$) by the induction hypothesis. Thus, $v$ is $i$-isolated.

######  Lemma 7.

For a vertex $v$ in $V_{i}$, no $i$ concentric cycles separating $v$ and
$V_{0}$ exist for $i\in[n^{\prime}]$.

Proof. We prove the lemma using the induction on the minimum radial distance
$i$ between $v$ and the boundary vertices of $H$. For the base case, we
consider a vertex $v$ in $V_{1}$. There is a face incident to both a boundary
vertex $w$ of $H$ and $v$, and thus no cycle separates $w$ and $v$. Thus, the
lemma holds.

We assume that there exists a set $\mathcal{C}$ of $(i+1)$ concentric cycles
separating $v$ and the boundary vertices of $G$. Let $C$ be the cycle farthest
from $v$ among them. As we did before, imagine that we remove from $G$ all
vertices separated by $C$ from $v$. Then the resulting graph $H^{\prime}$ can
be considered as a plane graph embedded on a 1-punctured plane such that the
vertices of $V(C)$ are the boundary vertices of $H^{\prime}$. By the induction
hypothesis, no $i$ concentric cycles separating $v$ and the boundary vertices
of $H^{\prime}$ exist if the radial distance between $v$ and $V(C)$ is $i$.
Therefore, the radial distance between $v$ and $V(C)$ is less than $i$, and
thus at least two cycles of $\mathcal{C}$ intersect $V_{1}$. This means there
is a cycle which separates some vertex in $V_{1}$ and $V_{0}$. This
contradicts to the definition of $V_{1}$. Thus, such a set $\mathcal{C}$ does
not exists, and thus this completes the proof.

Using the two lemmas stated above, we remove all vertices in $V_{i}$ for
$i=g(k)+1,\ldots,n^{\prime}$ from $H$ in time linear in the complexity of $H$
in total. By Lemma 6, all removed vertices are $g(k)$-isolated. After removing
them, $H$ has no $(g(k)+1)$ concentric cycles by Lemma 7. A planar graph
without $(g(k)+1)$ concentric cycles has treewidth at most $g(k)$. Therefore,
we have the following lemma.

######  Lemma 8.

Given a nice subgraph $H$ of $G$ embedded on a 1-punctured plane, we can
remove $g(k)$-isolated vertices so that the resulting subgraph $H$ has
treewidth at most $g(k)$.

###  4.2 General Case: Cut Reduction

In this section, we are given a graph $G$ embedded on a $2k$-punctured plane,
and show how to remove $g(k)$-isolated vertices so that the resulting graph
has treewidth at most $g(k)$. We apply the _cut reduction_ introduced in [23]
to decompose $G$ into several nice subgraphs embedded on 1-punctured planes.
Then we use the algorithm described in Section 4.1 to each nice subgraph
embedded on a 1-punctured plane.

######  Lemma 9 (Lemma 2 in [23]).

Let $H$ be a nice subgraph of $G$ embedded on a $c$-punctured plane $\boxdot$.
If $c\geq 3$, we can compute both a non-crossing closed curve $J$ contained in
$\boxdot$ and a set $X$ of $g(k)$-isolated vertices in time linear in the
complexity of $H$ such that

  * •

$J$ intersects $G$ only at vertices of $H$ and does not cross any edge of $G$,

  * •

the number of vertices of $H-X$ intersected by $J$ is at most $6g(k)+6$, and

  * •

$\boxdot\setminus J$ has at most three connected components each of which has
less than $c$ holes.

Lemma 2 of [23] shows how to decompose a nice subgraph $H$ of $G$ embedded on
a $c$-punctured plane with $c\geq 3$, but similarly, we can do this in the
case of $c=2$. For details, see its proof of the following lemma.

######  Lemma 10.

Let $G$ be a plane graph and $T$ be a set of terminal pairs. After removing
$g(k)$-isolated vertices from $G$, we can decompose $G$ into $2^{O(k)}$ nice
subgraphs each embedded on a 1-punctured plane and each having $2^{O(k)}$
boudnary vertices in linear time in total.

Proof. First, by applying Lemma 9 repeatedly, we decompose $G$ embedded on a
$2k$-punctured plane into at most $3^{2k}$ nice subgraphs of $G$ each embedded
on a $1$\- or $2$-punctured plane. For each nice subgraph $H$ of $G$ embedded
on a 2-punctured plane $\boxdot$, we do the following. Let $C_{1}$ and $C_{2}$
be the boundaries of two holes of $\boxdot$. Consider a simple arc contained
in $\boxdot$ having one endpoint on $V(C_{1})$ and one endpoint on $V(C_{2})$
that intersects $G$ only at vertices of $H$. If there are more than one such
arcs, we choose an arc $A$ that minimizes $|V(A)|$, where $V(A)$ denotes the
set of vertices of $G$ (and thus of $H$) intersected by $J$. Then let $v$ be
the median vertex of $V(A)$.

If the size of $V(A)$ is at most $6g(k)+6$, then we cut $\boxdot$ along the
non-crossing closed curve $C_{1}\cup A\cup C_{2}$ into a 1-punctured plane
$\boxdot^{\prime}$, and then we can consider $H$ as a nice subgraph of $G$
embedded on $\boxdot^{\prime}$ and having $|V(C_{1})\cup V(C_{2})\cup
V(A)|=2^{O(k)}$ boundary vertices. Otherwise, there are $g(k)$ concentric
cycles separating $v$ and $V(C_{1})\cup V(C_{2})$, and thus $v$ is
$g(k)$-isolated. Let $X$ be the set of the vertices lying on the ones, except
for the most $g(k)$ cycles farthest from $v$, among these cycles. All vertices
of $X$ are $g(k)$-isolated since $H$ is a nice subgraph of $G$. Moreover, we
can compute them in time linear in the complexity of $H$. The number of
vertices in $H-X$ intersected by $A$ is $2g(k)$ by construction. We remove all
vertices of $X$ from $H$, and then cut $\boxdot$ along the closed non-crossing
curve $C_{1}\cup A\cup C_{2}$ into a 1-punctured plane $\boxdot^{\prime}$ as
we did for the previous case. Then $H$ is a nice subgraph of $G$ embedded on
$\boxdot^{\prime}$ having at most $2g(k)=2^{O(k)}$ boundary vertices.

Figure 4: (a) $C_{1}$ and $C_{2}$ are boundaries of two holes of $\boxdot$ and
$A$ is an arc having two endpoints on $V(C_{1})$ and $V(C_{2})$. $v$ is a
median vertex of $V(A)$. Concentric cycles except the outermost $g(k)$ cycles
are colored gray. These vertices are $g(k)$-isolated. (b) $g(k)$-isolated
vertices are removed from (a). $V(C_{1})\cup V(C_{2})\cup V(A)$ has $2^{O(k)}$
boundary vertices.

After apply Lemma 10, we are given $2^{O(k)}$ nice subgraphs each embedded on
a 1-punctured plane and each having $2^{O(k)}$ boundary vertices. For each
nice subgraph, we apply the procedure for removing irrelevant vertices
described in Section 4.1. Then each of the resulting subgraphs has treewidth
$2^{O(k)}$. This implies that $G$ has treewidth $2^{O(k)}$. That is, we can
construct a tree decomposition $(\mathcal{T},\beta)$ of $G$ of width
$2^{O(k)}$ from tree decompositions of the nice subgraphs. More specifically,
let $B$ be the set of all boundary vertices of all nice subgraphs. For each
tree decomposition $(\mathcal{T}_{H},\beta_{H})$ of width $2^{O(k)}$ of a nice
subgraph $H$, we add all vertices of $B$ to all bags of $\beta_{H}(\cdot)$.
For the root $t$ of $\mathcal{T}$, we let $\beta(t)=B$, and then let $t$ point
to the roots of $\mathcal{T}_{H}$’s in $\mathcal{T}$ so that $t$ has the roots
as its children. In this way, we can obtain a tree decomposition
$(\mathcal{T},\beta)$ of $G$ of width $2^{O(k)}$. Therefore, we have the
following theorem. Furthermore, this bound is tight by Theorem 3 in [2].

######  Theorem 11.

Given an instance $(G,T,k)$ of Planar Disjoint Paths, we can remove irrelevant
vertices from $G$ in $2^{O(k)}n$ time in total so that the resulting graph $G$
has treewidth of $2^{O(k)}$.

##  5 Cutting the Plane into $O(k)$ Framed Rings

For two concentric cycles $I$ and $I^{\prime}$ such that $I$ is contained in
the interior of $I^{\prime}$, we let $\textsf{Ring}(I,I^{\prime})$ be the
subgraph of $G$ contained in the exterior of $I$ and the interior of
$I^{\prime}$ (including $I$ and $I^{\prime}$). A ring
$\textsf{Ring}(I,I^{\prime})$ is said to be _terminal-free_ if no terminal is
a vertex of $\textsf{Ring}(I,I^{\prime})$. Let $\mathcal{P}$ be a $T$-linkage
of $G$. A _segment_ of $\mathcal{P}$ in $\textsf{Ring}(I,I^{\prime})$ is a
maximal subpath of a path $P$ of $\mathcal{P}$ contained in
$\textsf{Ring}(I,I^{\prime})$. Note that both endpoints of a segment of
$\mathcal{P}$ lie on $V(I)\cup V(I^{\prime})$ if $\textsf{Ring}(I,I^{\prime})$
is terminal-free. A segment in a terminal-free ring is called a _traversing_
segment if it has one endpoint in $V(I)$ and one endpoint in $V(I^{\prime})$.
A segment of $\mathcal{P}$ is called a _visitor_ , otherwise. That is, a
visitor has both endpoints in $V(I)$ or has both endpoints in $V(I^{\prime})$.
We call a visitor an _inner visitor_ if its endpoints lie in $V(I)$, and an
_outer visitor_ , otherwise. See Figure 5(c).

In this section, we subdivide the plane with respect to a set $\mathcal{C}$ of
$O(k)$ concentric cycles of $G$, which will be called the _subframes_ , such
that there is a $T$-linkage $\mathcal{P}$ satisfying the following: For any
two consecutive cycles $C$ and $C^{\prime}$ of $\mathcal{C}$ such that
$\textsf{Ring}(C,C^{\prime})$ is terminal-free, a segment of $\mathcal{P}$ in
$\textsf{Ring}(C,C^{\prime})$ is a traversing segment. Furthermore, the number
of the segments of $\mathcal{P}$ in $\textsf{Ring}(C,C^{\prime})$ is
$2^{O(k)}$. However, the total complexity of the subframes might be large. To
handle this issue, we compute two curves $B$ and $B^{\prime}$ of total
complexity $2^{O(k)}$ in $\textsf{Ring}(C,C^{\prime})$, which we will call the
_frames_ , so that the radial distance between $C$ and $B$ (and $C^{\prime}$
and $B^{\prime}$) is $2^{O(k)}$. For illustration, see Figure 10.

###  5.1 Rings and Tight Concentric Cycles from the Outer Face

In this subsection, we construct a sequence $\mathcal{I}=\langle
I_{1},\ldots,I_{n^{\prime}}\rangle$ of concentric cycles containing $F^{*}$ in
their interiors in a _breadth-first_ fashion, which will be used to define the
frames and subframes in the following subsections, where $F^{*}$ denotes an
innermost face of $G$, that is, $G$ is a face farthest from the outer face
with respect to the radial distance. We can compute $F^{*}$ in linear time
using a variant of the breadth-first search on $G$.

To do this, we first decompose $V$ into $V_{0},\ldots,V_{n^{\prime}}$ such
that $V_{i}$ consists of all vertices of $G$ whose radial distance from
$F^{*}$ is exactly $i$. For each index $i\in[n^{\prime}]$, consider the
subgraph of $G$ induced by $V_{0}\cup V_{1}\cup\ldots V_{i}$. The subgraph is
not necessarily connected, but it has a unique outer face bouned by a single
cycle. We let $I_{i}$ be the boundary (cycle) of the outer face of the
subgraph. See Figure 5(a). Let $\mathcal{I}=\langle
I_{1},\ldots,I_{n^{\prime}}\rangle$. We say a terminal-free ring
$\textsf{Ring}(I_{i},I_{j})$ a _maximal terminal-free ring_ if
$\textsf{Ring}(I_{i^{\prime}},I_{j^{\prime}})$ contains a terminal for any two
indices $i^{\prime},j^{\prime}$ with $[i,j]\subsetneq[i^{\prime},j^{\prime}]$.
Also, a ring $\textsf{Ring}(I_{i},I_{j})$ is said to be _thick_ if
$|i-j|>2^{10k}$.

Figure 5: (a) The vertices of $I_{0},I_{1}$ and $I_{2}$ are marked with disks.
(b) This sequence of concentric cycles is not tight. The witness of non-
tightness is the path colored gray. The path violates the third condition of
the tightness. (c) The path in the figure that connecting $s$ and $t$ has four
segments in $\textsf{Ring}(C_{1},C_{p})$: the outer visitor connects $a_{1}$
and $a_{2}$, the inner visitor connects $b_{2}$ and $b_{3}$, and the two
traversing segments connecting $b_{1}$ and $a_{3}$, and $a_{4}$ and $b_{4}$,
respectively.

For each thick maximal terminal-free ring $\textsf{Ring}(I_{i},I_{j})$, we
compute two cycles $C$ and $C^{\prime}$ in $\textsf{Ring}(I_{i},I_{j})$, which
will be called the subframes, such that every segment of $\mathcal{P}$ in
$\textsf{Ring}(I_{i},I_{j})$ intersects $C$ and $C^{\prime}$ exactly once for
a specific $T$-linkage $\mathcal{P}$. For this purpose, we define a _tight_
sequence of concentric cycles in a thick maximal terminal-free ring
$\textsf{Ring}(I_{i},I_{j})$. Recall that $G$ is drawn in the plane, and thus
a cycle forms a closed curve in the plane. For a cycle $C$ of $G$, we use
$\textsf{cl}(C)$ to denote the region in the plane enclosed by $C$ including
$C$ itself. Also, we use $\textsf{int}(C)$ to denote the open region enclosed
by $C$ excluding $C$. We say a sequence $\mathcal{C}=\langle
C_{1},\ldots,C_{p}\rangle$ of concentric cycles in
$\textsf{Ring}(I_{i},I_{j})$ is _tight_ if

  * •

$C_{1}=I_{i}$, $C_{p}=I_{j}$,

  * •

the radial distance between $C_{1}$ and $C_{p}$ is exactly $p-1$, and

  * •

$\textsf{cl}(C_{i+1})\setminus\textsf{cl}(C_{i})$ does not contain any cycle
$C$ with
$\textsf{cl}(C_{i})\subsetneq\textsf{cl}(C)\subsetneq\textsf{cl}(C_{i+1})$ for
$i\in[1,2^{5k}]$,

  * •

$\textsf{int}(C_{i+1})\setminus\textsf{int}(C_{i})$ does not contain any cycle
$C$ with
$\textsf{cl}(C_{i})\subsetneq\textsf{cl}(C)\subsetneq\textsf{cl}(C_{i+1})$ for
$i\in[p-2^{5k},p]$.

For illustration, see Figure 5(b). Note that the third and fourth conditions
are symmetric.

######  Lemma 12.

For each thick maximal terminal-free ring, there is a tight sequence of
concentric cycles in the ring. Moreover, it can be constructed in time linear
in the complexity of the ring.

Proof. We construct tight concentric cycles by using a breadth-first search
through faces in two opposite directions: outwards from $C_{1}=I_{i}$ and
inwards from $C_{p}=I_{j}$. For the traversal going outwards from $C_{1}$, we
construct the concentric cycles starting from $C_{1}$: collect all the faces
incident to $C_{i}$ but not visited so far, and let $C_{i+1}$ be the outer
boundary cycle of the union of these faces. For the inward step, we can choose
the cycles symmetrically from $C_{p}$. The process terminates when all faces
are visited.

Now we show that the cycles satisfy the above conditions. For
$i\in[1,2^{5k}]$, we assume that
$\textsf{cl}(C_{i+1})\setminus\textsf{cl}(C_{i})$ contains a cycle $C$ with
$\textsf{cl}(C_{i})\subsetneq\textsf{cl}(C)\subsetneq\textsf{cl}(C_{i+1})$.
Then $\textsf{cl}(C_{i+1})\setminus\textsf{cl}(C)$ and $\textsf{cl}(C_{i})$ is
separated by the inclusive relation. Thus, the radial distance between a
vertex $v\in\textsf{cl}(C_{i+1})\setminus\textsf{cl}(C)$ and $C_{i}$ is larger
than one. However, all vertices of $C_{i+1}$ are derived from the faces
incident to $C_{i}$, so there exists a vertex $u\in C_{i}$ with
$\textsf{rdist}(u,v)=1$. This makes a contradiction, thus there is no vertex
$v\in\textsf{cl}(C_{i+1})\setminus\textsf{cl}(C)$. This means that there is no
cycle $C$ with
$\textsf{cl}(C_{i})\subsetneq\textsf{cl}(C)\subsetneq\textsf{cl}(C_{i+1})$.
For $i\in[p-2^{5k},p]$, we can define $C_{i}$ symmetrically so that satisfies
the fourth condition.

For the outward traversal, a vertex $v\in C_{i}$ is visited in the $(i-1)$
steps of the traversal. Thus, a vertex $v\in C_{i}$ has the radial distance
$(i-1)$ from $C_{1}$. Symmetrically, any vertex $v$ of a cycle $C_{i}$
constructed from the inward traversal has the radial distance $(p-i)$ from
$C_{p}$. Also, there is a face incident to the two last concentric cycles, one
from the inward traversal and one from outward traversal. Therefore, the
radial distance between the two last concentric cycles is one, and the radial
distance between $C_{1}$ and $C_{p}$ is $p-1$.

Clearly, this process takes time linear in the complextiy of
$\textsf{Ring}(I_{i},I_{j})$.

###  5.2 Monotonicity of a $T$-Linkage in Each Thick Maximal Terminal-Free
Ring

We say a $T$-linkage $\mathcal{P}$ is $\mathcal{C}$-_cheap_ if it uses a
smallest number of edges of $E(G)\setminus(\cup_{C\in\mathcal{C}}E(C))$ among
all $T$-linkages. Let $\mathcal{P}$ be a $\mathcal{C}$-cheap $T$-linkage. In
this section, we analyze the interaction between $\mathcal{P}$ and
$\mathcal{C}$ as stated in Lemma 14 and Corollary 17. To do this, we need the
following lemmas. Here, for two indices $\alpha$ and $\beta$ in $[p]$, a _cut_
for $V(C_{\alpha})$ and $V(C_{\beta})$ in a thick maximal terminal-free ring
$\textsf{Ring}(I_{i},I_{j})$ is defined as a set $W$ of vertices of a thick
maximal terminal-free ring $\textsf{Ring}(I_{i},I_{j})$ such that the removal
of $W$ from $\textsf{Ring}(I_{i},I_{j})$ disconnects every pair
$(v_{\alpha},v_{\beta})$ of vertices with $v_{\alpha}\in C_{\alpha}$ and
$v_{\beta}\in C_{\beta}$. Note that $W$ forms a _noose_ : a simple closed
curve in the plane intersecting $G$ only at the vertices of $W$. In the proof
of the following lemma, we use the fact that the treewidth of $G$ (and thus
the treewidth of $\textsf{Ring}(I_{i},I_{j})$) is $2^{O(k)}$.

Figure 6: (a) $B_{2}$ is the union of $Q_{2}$ and $C_{\alpha+2}$, which is the
subgraph of $G$ colored gray. (b) $S^{o}$ is the noose colored gray. It passes
through at most $2^{3k}$ vertices of $G$. An inner visitor $\gamma$ (colored
red) has two endpoints $a$ and $b$, and its base arc is colored blue.

######  Lemma 13.

A minimum cut for $V(C_{\alpha})$ and $V(C_{\beta})$ in
$\textsf{Ring}(C_{\alpha},C_{\beta})$ has size at most $2^{3k}$ if
$|\alpha-\beta|>2^{3k}$.

Proof. Assume to the contrary that a minimum cut for $V(C_{\alpha})$ and
$V(C_{\beta})$ in $\textsf{Ring}(C_{\alpha},C_{\beta})$ is larger than
$2^{3k}$ for two indices $\alpha$ and $\beta$ with $|\alpha-\beta|>2^{3k}$.
Let $\mathcal{Q}=\langle Q_{1},\ldots,Q_{\ell}\rangle$ be a maximum-
cardinality set of internally vertex-disjoint paths between vertices of
$C_{\alpha}$ and vertices of $C_{\beta}$. By the Menger’s theorem, the size of
$\mathcal{Q}$ is equal to the size of a minimum cut for $V(C_{\alpha})$ and
$V(C_{\beta})$, which is larger than $2^{3k}$ by the assumption. Then we can
construct a _bramble_ of order $2^{3k}$ in $\textsf{Ring}(I_{i},I_{j})$ as
follows. A bramble for an undirected graph $G$ is a family of connected vertex
sets of $G$ that all touch each other. Two vertex sets $A$ and $B$ _touch_ if
they have a vertex in common, or a vertex of $A$ is adjacent to a vertex of
$B$ in $G$. For each index $s\in[1,2^{3k}]$, we let $B_{s}$ be the union of
$V(Q_{s})$ and $V(C_{s+\alpha-1})$. See Figure 6(a). Note that $B_{s}$ is a
connected vertex set since each path of $\mathcal{Q}$ crosses each cycle in
$\\{C_{\alpha},\ldots,C_{\beta}\\}$ at least once. Moreover, any two such
vertex sets $B_{s}$ and $B_{s^{\prime}}$ touch each other. To see this, notice
that $Q_{s}$ intersects $C_{s^{\prime}+\alpha-1}$, and thus $Q_{s}$ and
$C_{s^{\prime}+\alpha-1}$ have a vertex in common. Since $V(Q_{s})\subseteq
B_{s}$ and $V(C_{s^{\prime}+\alpha-1})\subseteq B_{s^{\prime}}$ by
construction, $B_{s}$ touches $B_{s^{\prime}}$. Therefore, the family
$\mathcal{B}$ of $B_{s}$ for all indices $s\in[1,2^{3k}]$ is a bramble.

The _order_ of a bramble is defined as the smallest size of a hitting set of
the elements of the bramble. To show that the order of $\mathcal{B}$ is
$2^{3k-1}$, observe that no three elements $B_{s}$, $B_{s^{\prime}}$, and
$B_{s^{\prime\prime}}$ in $\mathcal{B}$ share a common vertex. This
observation holds because $Q_{s},Q_{s^{\prime}}$ and $Q_{s^{\prime\prime}}$
are pairwise vertex-disjoint paths, and
$C_{s+\alpha-1},C_{s^{\prime}+\alpha-1}$ and $C_{s^{\prime\prime}+\alpha-1}$
are pairwise vertex-disjoint cycles. Therefore, any vertex of $G$ hits at most
two elements of $\mathcal{B}$. This implies that the order of $\mathcal{B}$ is
at least the half of $|\mathcal{B}|$, which is $2^{3k-1}$.

It is known that $G$ has a bramble of order at least $k^{\prime}$ if and only
if it has treewidth at least $k^{\prime}-1$ [8]. In our case, $\mathcal{B}$
has order $2^{3k-1}$, which implies that $G$ has treewidth at least
$2^{3k-1}-1$. However, due to the preprocessing we made in Section 4, $G$ has
treewidth $O(k^{1.5}2^{k})$. This makes a contradiction, and thus the size of
$\mathcal{Q}$ is at most $2^{3k}$, and the size of a minimum cut for
$V(C_{\alpha})$ and $V(C_{\beta})$ in $\textsf{Ring}(I_{i},I_{j})$ is at most
$2^{3k}$.

######  Lemma 14.

For any index $r\in(2^{4k},p-2^{4k})$, no visitor of $\mathcal{P}$ in
$\textsf{Ring}(I_{i},I_{j})$ intersects $C_{r}$.

Proof. By Lemma 13, a minimum cut $S$ for $V(C_{1})$ and $V(C_{2^{3k}})$ has
size at most $2^{3k}$. Then there is a _noose_ $S^{o}$ with $S^{o}\cap V=S$. A
noose is a closed simple curve in the plane intersecting $G$ only at vertices.
Similarly, let $R$ be a minimum cut for $V(C_{p-2^{3k}})$ and $V(C_{p})$ in
$\textsf{Ring}(I_{i},I_{j})$, and let $R^{o}$ be a noose with $R^{o}\cap V=R$.
See Figure 6(b).

We prove the lemma only for the inner visitor since the outer visitor can be
proved symmetrically. (Note that the tightness of a sequence of concentric
cycles is defined symmetrically for $C_{1}$ and $C_{p}$.) For an inner visitor
not intersecting $S^{o}$, the claim holds immediately since $S^{o}$ lies in
the interior of $C_{2^{4k}}$. The number of inner visitors intersecting
$V(S^{o})$ is at most $2^{3k}$ since the visitors are internally vertex-
disjoint, and the size of $V(S^{o})$ is $2^{3k}$.

For an inner visitor $\gamma$ intersecting $S^{o}$, let $a$ and $b$ be its
endpoints in $V(C_{1})$. There are two arcs of $C_{1}$ connecting $a$ and $b$.
Exactly one of them forms a bounded region not containing the interior of
$C_{1}$ together with $\gamma$. See Figure 6(b). We call such an arc the _base
arc_ of $\gamma$. We define the _order_ of an inner visitor $\gamma$
intersecting $S^{o}$ as the number of other inner visitors intersecting
$S^{o}$ whose base arcs are contained in the base arc of $\gamma$.

Figure 7: (a) The red path $\gamma$ is an inner visitor. If its order is zero,
no segment of $\mathcal{P}$ intersecting $S^{o}$ has endpoints on the base of
$\gamma$. Therefore, the blue path does not intersect any other segments of
$\mathcal{P}$, and thus we can replace the red path with the blue path. (b)
$S$ is a traversing segment. The subpath of $S$ lying between $a$ and $b$ is
an $r$-horn. The base of the $r$-horn is colored blue.

To prove the lemma, we show that an inner visitor intersecting $S^{o}$ of
order $x$ does not intersect any of
$C_{2^{3k}+x+1},C_{2^{3k}+x+2},\ldots,C_{p}$. We prove this using induction on
the order of the inner visitors. Note that the order of an inner visitor is at
most $2^{3k}$ since the number of visitors intersecting $S^{o}$ is at most
$2^{3k}$. As a base case, consider an inner visitor $\gamma$ of order $0$. The
region bounded by $\gamma$ and its base arc does not intersect by any other
segments intersecting $S^{o}$. Moreover, a segment not intersecting $S^{o}$
does not intersect $C_{2^{3k}}$. If $\gamma$ intersects $C_{2^{3k}+1}$, we can
reroute it so that it uses strictly fewer edges not contained in the cycles of
$\mathcal{C}$: for every maximal part of $\gamma$ lying outside of the
interior of $C_{2^{3k}}$, we replace it with an arc of $C_{2^{3k}}$. See
Figure 7(a). The resulting $\gamma$ does not intersect any other path in
$\mathcal{P}$. Therefore, the claim holds for the base case.

Now we assume that no inner visitor intersecting $S^{o}$ of order $x-1$
intersects $C_{2^{3k}+x}$. Then let $\gamma$ be an inner visitor intersecting
$S^{o}$ of order $x$. If $\gamma$ intersects $C_{2^{3k}+x+1}$, the region
bounded by $\gamma$ and $C_{2^{3k}+x+1}$ is not intersected by any other
visitors by the induction hypothesis. Similarly to the previous case, we can
reroute it along arcs of $C_{2^{3k}+x}$ using fewer edges not contained in the
cycles of $\mathcal{C}$ in this case. This violates the fact that
$\mathcal{P}$ is $\mathcal{C}$-cheap, and thus $\gamma$ does not intersect
$C_{2^{3k}+x+1}$, and thus it does not intersect any of
$C_{2^{3k}+x+1},C_{2^{3k}+x+2},\ldots,C_{p}$. This proves the claim.

Since the order of an inner visitor is at most $2^{3k}$, no inner visitor
intersects any of $C_{2^{4k}+1},\ldots,C_{p}$. Symmetrically, no outer visitor
intersects any of $C_{1},C_{2},\ldots,C_{p-2^{4k}-1}$. Therefore, the lemma
holds.

Now we focus on the traversing segments of $\mathcal{P}$ in
$\textsf{Ring}(I_{i},I_{j})$. We show that for a traversing segment $S$ of
$\mathcal{P}$ and an index $r\in(2^{4k},2^{5k})\cup(p-2^{5k},p-2^{4k})$, the
vertices of $V(S)\cap V(C_{r})$ appear consecutively along $S$. We only prove
this for indices $r\in(2^{4k},2^{5k})$. The other case, that is,
$r\in(p-2^{5k},p-2^{4k})$, can be handled symmetrically. To prove this claim,
we define a _horn_ of a traversing segment $S$. A subpath $s$ of $S$ is called
an $r$-_horn_ if its endpoints lie on $C_{r}$, and no internal vertices of $s$
lie in $\textsf{cl}(C_{r})$, where $\textsf{cl}(C_{r})$ denotes the region in
the plane bounded by $C_{r}$ including $C_{r}$. See Figure 7(b). In this case,
the _base_ of $s$ is defined as the subpath of $C_{r}$ which, together with
$s$, forms a bounded region lying outside of the interior of $C_{r}$. For
illustration of the following lemma, see Figure 8(a).

Figure 8: (a) The red segment $S$ is a traversing path of $\mathcal{P}$, and
the subpath $s$ of $S$ between $a$ and $b$ is an $r$-horn. Then $\eta$ is the
part of the base of $s$ neither intersecting $P$ nor contained in the bases of
any other $r$-horns coming from $S$. (b) Since $S$ is $\mathcal{C}$-cheap,
there is a segment $S^{\prime}$ intersecting $\eta$. (c) If $b$ is contained
in $V(C_{r})$, the tightness of $\mathcal{C}$ is violated because of the
subpath of $S^{\prime}$ between $b$ and $b^{\prime}$.

######  Lemma 15.

Let $s$ be an $r$-horn of a traversing segment $S$ of $\mathcal{P}$ for
$r\in(2^{4k},2^{5k})$. Let $x$ and $y$ be the first and last vertices of $S$
on the base of $s$ (including the endpoints of $s$) along $S$ from the end
vertex of $S$ lying on $V(C_{1})$. Let $\eta$ be the subpath of the base of
$s$ connecting $x$ and $y$. Then there is a traversing segment of
$\mathcal{P}$ other than $S$ which has an $(r-1)$-horn intersecting $\eta$.

Proof. Since $\mathcal{P}$ is $\mathcal{C}$-cheap, $\eta$ is intersected by a
segment $S^{\prime}$ of $\mathcal{P}$. Otherwise, we can reroute $S$ along
$\eta$ so that it uses strictly fewer edges not contained in the cycles of
$\mathcal{C}$, which contradicts the fact that $\mathcal{P}$ is
$\mathcal{C}$-cheap. Moreover, $S^{\prime}$ is a traversing segment since no
visitor intersects $C_{r}$ by Lemma 14. Since the paths of $\mathcal{P}$ are
vertex-disjoint, and $S^{\prime}$ intersects the bounded region $R$ formed by
$\eta$ and the subpath of $S$ connecting $x$ and $y$, $S^{\prime}$ must
intersect $\eta$ at least twice. Then consider a maximal subpath $s^{\prime}$
of $S^{\prime}$ contained in $R$ and intersecting $\eta$ only at its
endpoints. See Figure 8(b). Let $a$ be the first vertex of $S^{\prime}$ lying
before $s^{\prime}$ (from the end vertex of $S^{\prime}$ lying on $V(C_{1})$)
that lies on the cycles in $\mathcal{C}$. Similarly, let $b$ be the first
vertex of $S^{\prime}$ lying after $s^{\prime}$ (from the end vertex of
$S^{\prime}$ lying on $V(C_{1})$) that lies on the cycles in $\mathcal{C}$.
Note that $a$ and $b$ are vertices of $V(C_{r})\cup V(C_{r-1})$ since
$S^{\prime}$ is a path in $G$ connecting a vertex in $C_{1}$ and a vertex in
$C_{p}$. Moreover, we claim that $a$ and $b$ are vertices of $C_{r-1}$. If $b$
is not a vertex of $C_{r-1}$, then it is a vertex of $C_{r}$. See Figure 8(c).
Let $b^{\prime}$ be the endpoint of $s^{\prime}$ appearing before the other
endpoint of $s^{\prime}$ along $S^{\prime}$ from $b$. Then a path $\gamma$
connecting $b$ and $b^{\prime}$ along $C_{r}$, together with the subpath
$\gamma^{\prime}$ of $S^{\prime}$ between $b$ and $b^{\prime}$, forms a
bounded region not intersecting the interior of $C_{r-1}$. This violates the
tightness of $\mathcal{C}$: By replacing $\gamma$ with $\gamma^{\prime}$ from
$C_{r}$, we can obtain a cycle $C$ contained in
$\textsf{cl}(C_{r})\setminus\textsf{cl}(C_{r-1})$ with
$\textsf{cl}(C_{r})\subsetneq\textsf{cl}(C)\subsetneq\textsf{cl}(C_{r-1})$.
Therefore, both $a$ and $b$ are vertices of $C_{r-1}$. This implies that
$S^{\prime}$ has an $(r-1)$-horn containing $s^{\prime}$ and having $a$ and
$b$ as the endpoints of its base. Therefore, the lemma holds.

######  Lemma 16.

No $r$-horn of a traversing segment of $\mathcal{P}$ exists for
$r\in(2^{5k},2^{6k})$.

Proof. Assume to the contrary that there is an $r$-horn $s_{1}$ of a
traversing segment of $\mathcal{P}$ for $r\in(2^{5k},2^{6k})$. Then we can
define a sequence $\mathcal{S}=\langle s_{1},\ldots,s_{q}\rangle$ of horns
inductively as follows. Given an $r^{\prime}$-horn $s_{t}$, we define
$s_{t+1}$ as follows. Let $S$ be the segment of $\mathcal{P}$ containing
$s_{t}$. Then we define $x,y$ and $\eta$ as defined in the statement of Lemma
15: Let $x$ and $y$ be the first and last vertices of $S$ on the base of
$s_{t}$ (including the endpoints of $s$) along $S$ from the end vertex of $S$
lying on $V(C_{1})$. Let $\eta$ be the subpath of the base of $s$ connecting
$x$ and $y$. If there is an $r^{\prime}$-horn (other than $s_{t}$) whose base
is contained in $\eta$, we let $s_{t+1}$ be the one with a longest base among
all such $r^{\prime}$-horns. Otherwise, we let $s_{t+1}$ be the one with a
longest base among all $(r^{\prime}-1)$-horns intersecting $\eta$. See Figure
9(a). Note that if $r^{\prime}\geq 2^{4k}$, $s_{t+1}$ is well-defined by Lemma
15. Therefore, the size of $\mathcal{S}$ must be at least
$2^{5k}-2^{4k}>2^{3k}$. By construction, the following properties hold.

  * (1)

No two consecutive horns in $\mathcal{S}$ come from the same segment of
$\mathcal{P}$.

  * (2)

If an $r$-horn $s_{t}$ and $r^{\prime}$-horn $s_{t^{\prime}}$ come from the
same segment of $\mathcal{P}$ with $t<t^{\prime}$, then $r>r^{\prime}$.

Figure 9: (a) The sequence of horns starting from the horn with endpoints $a$
and $b$ consists of three horns colored gray. (b) The left path colored gray
is $\Gamma_{1}$ that connects $a_{t^{\prime}}$ and $a_{t}$. The right path
colored gray is $\Gamma_{2}$ that connects $b_{t^{\prime}}$ and $b_{t}$.

In the following, we claim that the size of $\mathcal{S}$ is at most $2^{3k}$,
which makes a contradiction. That is, this claim implies that no segment of
$\mathcal{P}$ has a $r$-horn for $r\in(2^{5k},2^{6k})$. If every horn in
$\mathcal{S}$ comes from different segments of $\mathcal{P}$, the claim holds
immediately. This is because the number of traversing segments of
$\mathcal{P}$ is at most the size of a minimum cut for $C_{1}$ and $C_{p}$,
which is at most $2^{3k}$.

Thus assume that there are two horns of $\mathcal{S}$ coming from the same
traversing segment of $\mathcal{P}$. If there are more than two such pairs, we
choose a pair $(s_{t},s_{t^{\prime}})$ coming from the same traversing segment
$S$ of $\mathcal{P}$ with $t<t^{\prime}$ that minimizes $t^{\prime}-t$. Recall
that $t^{\prime}-t\geq 2$ as stated in Property (1). For an index $x\in[q]$,
let $a_{x}$ and $b_{x}$ be the counterclockwise and clockwise endpoints of the
base of $s_{x}$ along the cycle of $\mathcal{C}$ containing its base,
respectively. Let $\Gamma_{1}$ be the path of $G$ connecting
$a_{t^{\prime}},a_{t^{\prime}-1},\ldots,a_{t}$ in order such that $a_{x}$ and
$a_{x-1}$ are connected by a part of the base of $s_{x}$ and a subpath of
$s_{x-1}$ for $x\in[t,t^{\prime}]$. Similarly, let $\Gamma_{2}$ be the path of
$G$ connecting $b_{t},b_{t+1},\ldots,b_{t^{\prime}}$ in order such that
$b_{x}$ and $b_{x-1}$ are connected by a part of the base of $s_{x}$ and a
subpath of $s_{x-1}$ for $x\in[t,t^{\prime}]$. See Figure.

Let $r$ be the index such that $s_{t}$ is an $r$-horn, and $r^{\prime}$ be the
index such that $s_{t^{\prime}}$ is an $r^{\prime}$-horn. By Property (2),
$r>r^{\prime}$, and therefore, there is an $(r-1)$-horn
$s_{t^{\prime\prime}}\in\mathcal{S}$ not coming from the segment $S$ but
intersecting the base of $s_{t}$ with $t<t^{\prime\prime}<t^{\prime}$. Let
$S^{\prime\prime}$ be the traversing segment of $\mathcal{P}$ containing
$s_{t^{\prime\prime}}$. In the following, we show that $S^{\prime\prime}$ has
a horn in $\mathcal{S}$ lying between $s_{t}$ and $s_{t^{\prime}}$. This
contradicts the choice of $s_{t}$ and $s_{t^{\prime}}$. Since
$S^{\prime\prime}$ connects a vertex of $V(C_{1})$ and a vertex of $V(C_{p})$,
$S^{\prime\prime}$ intersects $\Gamma_{1}$ (and $\Gamma_{2}$) at a vertex
lying outside of $s_{t^{\prime\prime}}$. Consider a minimal subpath $\pi$ of
$S^{\prime\prime}$ having one endpoint on $\Gamma_{1}$ and one endpoint on
$\Gamma_{2}$. Let $\ell$ be the index such that one endpoint of $\pi$ lies
between $a_{\ell}$ and $a_{\ell+1}$ along $\Gamma_{1}$, and the other endpoint
of $\pi$ lies between $b_{\ell}$ and $b_{\ell+1}$ along $\Gamma_{2}$. Note
that the subscript $(\ell)$ of $a$ and $b$ must be the same since the paths of
$\mathcal{P}$ are pairwise vertex-disjoint. If $s_{\ell}$ comes from
$S^{\prime\prime}$, then we are done. Thus we assume that $s_{\ell}$ comes
from a segment other than $S^{\prime\prime}$. Then by the construction, $\pi$
must be included in $\mathcal{S}$ before $s_{\ell+1}$ is included in
$\mathcal{S}$. This makes a contradiction. Therefore, the size of
$\mathcal{S}$ is at most $2^{3k}$, and the lemma holds.

Lemma 16 implies the following corollary.

######  Corollary 17.

The vertices of $V(S)\cap V(C_{r})$ appear consecutively along $S$ for each
traversing segment $S$ of $\mathcal{P}$ for each index
$r\in(2^{4k},2^{5k})\cup(p-2^{5k},p-2^{4k})$.

###  5.3 Subframes and Frames for a Thick Maximal Terminal-Free Ring

Now we are ready to define two frames and two subframes for each thick maximal
terminal-free ring $\textsf{Ring}(I_{i},I_{j})$. Let $\cup\mathcal{C}$ be the
union of the tight sequence of concentric cycles for all thick terminal-free
rings. We call a $\cup\mathcal{C}$-cheap linkage $\mathcal{P}$ a _cheap_
linkage. Since all terminal-free rings are pairwise disjoint, a cheap
$T$-linkage $\mathcal{P}$ is also a $\mathcal{C}$-cheap $T$-linkage for the
tight sequence $\mathcal{C}$ of concentric cycle we computed for a thick
maximal terminal-free ring. Then Corollary 17 implies the following corollary.
We call $C_{2^{5k}}$ and $C_{p-2^{5k}}$ the _subframe_ in
$\textsf{Ring}(I_{i},I_{j})$. In this way, we can obtain at most $4k$
subframes in total for all thick maximal terminal-free rings. Moreover, note
that the subframes are concentric.

######  Corollary 18.

For a cheap $T$-linkage $\mathcal{P}$, every segment of $\mathcal{P}$ in
$\textsf{Ring}(I_{i}.I_{j})$ has at most one traversing subsegment and no
visitor in $\textsf{Ring}(C_{2^{5k}},C_{p-2^{5k}})$.

Although $C$ and $C^{\prime}$ cut the paths of $\mathcal{P}$ in a structured
way, the complexity of a subframe might be large. To handle this issue, we
deal with two noose $B$ and $B^{\prime}$ of total complexity $2^{O(k)}$ in
$\textsf{Ring}(C,C^{\prime})$ lying close to $C$ and $C^{\prime}$,
respectively, instead of dealing with $C$ and $C^{\prime}$, where
$C=C_{2^{5k}}$ and $C^{\prime}=C_{p-2^{5k}}$. Recall that $\mathcal{C}=\langle
C_{1},\ldots,C_{p}\rangle$ is a tight sequence of concentric cycles in
$\textsf{Ring}(I_{i},I_{j})$ with $p\geq 2^{10k}$. By Lemma 13, a minimum cut
for $V(C_{2^{5k}})$ and $V(C_{2^{6k}})$ in
$\textsf{Ring}(C_{2^{5k}},C_{2^{6k}})$ has size at most $2^{3k}$. Moreover,
such a cut forms a noose $B$ in $\textsf{Ring}(C_{2^{5k}},C_{2^{6k}})$. We can
compute it in $2^{O(k)}n$ time using the Ford–Fulkerson algorithm for
computing a maximum flow in $O(fN)$ time, where $f$ denotes the size of a
maximum flow, and $N$ denotes the complexity of a given graph. In our case,
$f=2^{O(k)}$ and $N=O(n)$. Similarly, we compute a noose $B^{\prime}$ in
$\textsf{Ring}(C_{p-2^{5k}},C_{p-2^{6k}})$ of complexity $2^{O(k)}$ in time
$2^{O(k)}n$. In the following, we call the two nooses $B$ and $B^{\prime}$ the
_frames_.

Figure 10: The black cycles are the boundaries of the thick maximal terminal-
free rings, the red cycles are the subframes, and the blue cycles are the
frames. The terminal-free framed rings are colored gray.

Let $\mathcal{B}=\langle
B_{1},B_{1}^{\prime},B_{2},B_{2}^{\prime},\ldots,B_{k^{\prime}},B_{k^{\prime}}^{\prime}\rangle$
be the sequence of (concentric) frames such that $B_{i}$ and $B_{i}^{\prime}$
are frames from the $i$th thick maximal terminal-free ring. See Figure 10(a).
Note that the radial distance between $V(B_{i})$ and $V(B_{i}^{\prime})$ is at
least $2^{k}$, and the radial distance between $V(B_{i}^{\prime})$ and
$V(B_{i+1})$ is at most $2^{O(k)}$ by construction for all indices
$i\in[k^{\prime})$. Moreover, no terminal is contained in
$\textsf{Ring}(B_{i},B_{i}^{\prime})$. A ring defined by two consecutive
nooses in $\mathcal{B}$ is called a _framed ring_. A framed ring containing a
terminal is called a _terminal-containing_ framed ring, and a framed ring not
containing a terminal is called a _terminal-free_ framed ring.

##### Substructure of a Terminal-Containing Framed Ring.

Let $\textsf{Ring}_{i}^{\textsf{o}}=\textsf{Ring}(B_{i-1}^{\prime},B_{i})$ be
a terminal-containing framed ring. We construct a substructure of
$\textsf{Ring}_{i}^{\textsf{o}}$, which we will call the _skeleton forest_.
For each terminal $t$ of $\bar{T}$ lying in $\textsf{Ring}_{i}^{\textsf{o}}$,
we connect $t$ and a vertex of $B_{i}$ by a radial curve (a shortest path in
$G^{\textsf{rad}}$) of complexity $2^{O(k)}$. By construction of
$\mathcal{B}$, the radial distance between $B_{i}$ and $t$ is $2^{O(k)}$. In
addition to this, we connect $B_{i-1}^{\prime}$ and of $B_{i}$ by a radial
curve of complexity $2^{O(k)}$. Recall that the radial distance between the
two radial curves is at most $2^{O(k)}$. We can compute all such radial curves
in $2^{O(k)}n$ time in total. Let $\Gamma_{i}$ be the union of these radial
curves, which forms a forest. We call $\Gamma_{i}$ the _skeleton forest_ of
$\textsf{Ring}_{i}^{\textsf{o}}$. The number of leaf nodes of $\Gamma_{i}$ is
$O(k_{i})$, where $k_{i}$ denotes the number of terminals in
$\textsf{Ring}_{i}^{\textsf{o}}$. Also, the number of nodes of $\Gamma_{i}$ of
degree at least three is $O(k_{i})$. A maximal path of $\Gamma_{i}$ consisting
of degree-2 vertices is called a _tree-path_. Also, a maximal subpath of
$B_{i}$ (and $B_{i-1}^{\prime}$) consisting of vertices not contained in
$\Gamma_{i}$ is called a _boundary-path_. Then there are $O(k_{i})$ tree-paths
and boundary-paths, and the total complexity of the tree-paths and boundary-
paths is $2^{O(k)}$.

The following lemma summarizes this section.

######  Lemma 19.

We can construct $O(k)$ framed rings in $2^{O(k)}n$ time in total. Also, we
can compute the skeleton forests for all terminal-containing framed rings in
$2^{O(k)}n$ time in total.

##  6 Crossing Pattern and Abstract Polygonal Schema

In this section, we define a canonical encoding of a cheap $T$-linkage
$\mathcal{P}$, which we will call the crossing pattern, with respect to the
frames. Let $\mathcal{B}=\langle
B_{1},B_{1}^{\prime},B_{2},B_{2}^{\prime},\ldots,B_{k^{\prime}},B_{k^{\prime}}^{\prime}\rangle$
be the sequence of (concentric) frames such that $B_{i}$ and $B_{i}^{\prime}$
are frames from the $i$th thick maximal terminal-free ring. Also, let
$\mathcal{C}=\langle
C_{1},C_{1}^{\prime},C_{2},C_{2}^{\prime},\ldots,C_{k^{\prime}},C_{k^{\prime}}^{\prime}\rangle$
be the sequence of (concentric) subframes such that $C_{i}$ and
$C_{i}^{\prime}$ are subframes from the $i$th thick maximal terminal-free
ring. Recall that the radial distance between $B_{i-1}^{\prime}$ and $B_{i}$
is $2^{O(k)}$. That is, there is a radial curve between $B_{i-1}^{\prime}$ and
$B_{i}$ of complexity $2^{O(k)}$. We call the endpoints of the radial curve
lying on $B_{i-1}^{\prime}$ and $B_{i}$ the _origins_ of $B_{i-1}^{\prime}$
and $B_{i}$, respectively.

We first define the _winding number_ of two walks in
$\textsf{Ring}(D,D^{\prime})$ for two nooses $D$ and $D^{\prime}$ of $G$. We
say two walks are _aligned_ if the pairs of the endpoints of the two walks are
the same. For two aligned walks $\pi$ and $\pi^{\prime}$ traversing
$\textsf{Ring}(D,D^{\prime})$ oriented from the endpoints on $D$ to the
endpoints on $D^{\prime}$, we record the signed numbers of crossings of $\pi$
along $\pi^{\prime}$: for every common vertex of $V(\pi)\cap V(\pi^{\prime})$
excluding their endpoints, we record +1 if $\pi$ crosses $\pi^{\prime}$ from
left to right, record -1 if $\pi$ crosses $\pi^{\prime}$ from right to left,
and record 0 if $\pi$ does not cross $\pi^{\prime}$ at that vertex. Also, if
the first and last edges of $\pi$ lie in the same direction of $\pi^{\prime}$,
we record 0. If the first edge of $\pi$ lies to the left of $\pi^{\prime}$,
but the last edge of $\pi$ on $D^{\prime}$ lies to the right of
$\pi^{\prime}$, then we record $-1$. Otherwise, we record $+1$. Then the
winding number between $\pi$ and $\pi^{\prime}$, denoted by
$\textsf{WindNum}(\pi,\pi^{\prime})$, is defined as the sum of all recorded
numbers. See Figure 11(a-b). If two walks $\pi$ and $\pi^{\prime}$ are not
aligned, we contract all the edges of $D_{\textsf{sub}}$ into a single vertex,
and contract all the edges of $D_{\textsf{sub}}^{\prime}$ into a single vertex
so that the two walks become aligned, where $D_{\textsf{sub}}$ (and
$D_{\textsf{sub}}^{\prime}$) is the subnoose of $D$ (and $D^{\prime}$) lying
from the endpoints of $\pi$ to the endpoints of $\pi^{\prime}$ in clockwise
direction. Then the winding number between $\pi$ and $\pi^{\prime}$ is defined
as their winding numbers after the contraction. See Figure 11(c).

Figure 11: $\textsf{WindNum}(\pi_{1},\pi_{5})=-1$,
$\textsf{WindNum}(\pi_{2},\pi_{5})=0$, $\textsf{WindNum}(\pi_{3},\pi_{5})=-2$,
and $\textsf{WindNum}(\pi_{4},\pi_{5})=0$

The following lemma holds due to Proposition 7.1 and Proposition 7.2 of [21].

######  Lemma 20.

Let $\textsf{Ring}(D,D^{\prime})$ be a ring defined by two nooses $D$ and
$D^{\prime}$, and let $\mathcal{P}$ and $\mathcal{Q}$ be two linkages
traversing $\textsf{Ring}(D,D^{\prime})$. Then there exists a traversing
linkage $\mathcal{P}^{\prime}$ aligned with $\mathcal{P}$ such that for a
fixed path $Q\in\mathcal{Q}$, $|\textsf{WindNum}(P^{\prime},Q)|\leq 7$ for all
paths $P^{\prime}$ of $\mathcal{P}^{\prime}$.

Proof. By Proposition 7.2 in [21], there exists a linkage
$\mathcal{P}^{\prime}$ aligned with $\mathcal{P}$ so that each $P^{\prime}$ in
$\mathcal{P}^{\prime}$ satisfies
$|\textsf{WindNum}(P^{\prime},Q^{\prime})|\leq 6$ with a path $Q^{\prime}$ in
$\mathcal{Q}$. Furthermore, for a fixed path $Q\in\mathcal{Q}$, Proposition
7.1 in [21] implies that $\textsf{WindNum}(P^{\prime},Q^{\prime})$ and
$\textsf{WindNum}(P^{\prime},Q)$ differ by at most one since $Q$ and
$Q^{\prime}$ are exactly same or vertex-disjoint paths. This completes the
proof.

###  6.1 Reference Paths and a Base $T$-Linkage

Given a cheap $T$-linkage $\mathcal{P}$, we reroute each path of $\mathcal{P}$
to control the winding number of each path of $\mathcal{P}$ and a precomputed
path, called a _reference path_ , using Lemma 25. For each two consecutive
subframes $C_{i}$ and $C_{i}^{\prime}$ of $\mathcal{C}$, we compute a maximum-
cardinality set $\mathcal{Q}_{i}$ of vertex-disjoint paths from $C_{i}$ to
$C_{i}^{\prime}$. The paths in $\mathcal{Q}_{i}$ are called the _reference
paths_ in $\textsf{Ring}(C_{i},C_{i}^{\prime})$. Let $Q$ be a fixed path
$\mathcal{Q}_{i}$, which we call the _initial_ path of $\mathcal{Q}_{i}$. By
Lemma 13, the size of $\mathcal{Q}_{i}$ is $2^{O(k)}$, and thus we can compute
$\mathcal{Q}_{i}$ in $2^{O(k)}n$ time for all $i\in[k^{\prime}]$ using the
Ford–Fulkerson algorithm.

Also, the size of $\mathcal{Q}_{i}$ is at least the number of traversing
segments of $\mathcal{P}$ in $\textsf{Ring}(C_{i},C_{i}^{\prime})$ since the
traversing segments of $\mathcal{P}$ in $\textsf{Ring}(C_{i},C_{i}^{\prime})$
are also vertex-disjoint paths from $C_{i}$ to $C_{i}^{\prime}$. By Lemma 25,
there is a linkage $\mathcal{P}^{\prime}$, aligned with the set of all
traversing segments of $\mathcal{P}$ in $\textsf{Ring}(C_{i},C_{i}^{\prime})$
with $|\textsf{WindNum}(P^{\prime},Q)|\leq 7$ for all paths
$P^{\prime}\in\mathcal{P}^{\prime}$. We replace each traversing segment of
$\mathcal{P}$ in $\textsf{Ring}(C_{i},C_{i}^{\prime})$ with its corresponding
segment of $\mathcal{P}^{\prime}$. We do this for all two consecutive
subframes defining a terminal-free ring. Since
$\textsf{Ring}(C_{i},C_{i}^{\prime})$ has no visitor, the resulting paths are
pairwise vertex-disjoint. We call the resulting linkage $\mathcal{P}$ the
_base $T$-linkage_. Note that the base $T$-linkage always exists if $(G,T,k)$
is a YES-instance.

##### Oscillating Subsegments and Traversing Subsegments.

Now let $\mathcal{P}$ be a base $T$-linkage. Let $\mathcal{S}$ be the set of
the traversing segments of $\mathcal{P}$ in
$\textsf{Ring}(C_{i},C_{i}^{\prime})$, and let $\mathcal{Q}_{i}$ be the set of
all reference paths in $\textsf{Ring}(C_{i},C_{i}^{\prime})$. Since
$\textsf{Ring}(C_{i},C_{i}^{\prime})$ is terminal-free, every subsegment of a
segment in $\mathcal{S}$ having both endpoints on $V(C_{i})$ (or
$V(C_{i}^{\prime})$) is fully contained in $V(C_{i})$ (or
$V(C_{i}^{\prime})$). Also, we may assume that every path of $\mathcal{Q}_{i}$
intersects $V(C_{i})$ and $V(C_{i}^{\prime})$ only at its endpoints; if it is
not the case, we can take its maximal subpath having one endpoint on
$V(C_{i})$ and $V(C_{i}^{\prime})$. However, it is possible that a path of
$\mathcal{S}\cup\mathcal{Q}_{i}$ crosses $B_{i}$ (and $B_{i}^{\prime}$) more
than once.

Figure 12: (a) The subpath of $S$ lying between $a$ and $b$ is the subsegment
oscillating around $B_{i}$, and the subpath of $S$ lying between $b^{\prime}$
and $b^{\prime}$ is the subsegment oscillating around $B_{i}^{\prime}$. (b)
The red oscillating subsegment has two pieces, and the blue one has four
pieces. The piece with endpoints $x$ and $y$ has order three, and the piece
with endpoints $x^{\prime}$ and $y^{\prime}$ has order zero. We push the
pieces towards their base arcs. See the arrow. (c) After pushing the pieces,
we obtain two walks traversing along $B_{i}$. Then we remove the six blue
edges lying between $p$ and $q$ during the U-turn elimination process.

To handle this, we decompose each path $S$ in $\mathcal{S}\cup\mathcal{Q}_{i}$
into five pieces: a prefix, two oscillating subsegments, a traversing
subsegment, and a suffix. First, we consider $S$ as oriented from its endpoint
on $C_{i}$ to its endpoint on $C_{i}^{\prime}$. Let $a$ (and $b$) is the first
(and last) vertex of $s$ lying on $B_{i}$. Then, let $a^{\prime}$ (and
$b^{\prime}$) be the first (and last) vertex of $S$ lying on $B_{i}^{\prime}$
among all vertices of $S$ lying after $b$ along $S$. See Figure 12(a). We say
the subpath lying between $a$ and $b$ (and between $a^{\prime}$ and
$b^{\prime}$) is the _subsegment oscillating around_ $B_{i}$ (and
$B_{i}^{\prime}$). Also, the subpath lying between $b$ and $a^{\prime}$ is
called the _traversing subsegment_ of $S$. The other pieces are called the
prefix and suffix of $S$, respectively. Also, the subsegment between $a$ and
$b^{\prime}$ is called the _middle subsegment_ of $S$.

######  Lemma 21.

For each path $S$ of $\mathcal{S}$, the absolute value of the winding number
between the middle subsegments of $S$ and $Q$ is $2^{O(k)}$.

Proof. Let $\bar{S}$, $S_{\textsf{pre}}$, and $S_{\textsf{su}}$ be the middle
subsegment, prefix, and suffix of $S$, respectively. Analogously, we let
$\bar{Q}$, $Q_{\textsf{pre}}$, and $Q_{\textsf{su}}$ be the middle subsegment,
prefix, and suffix of $Q$, respectively. Our goal is to give an upper bound of
$|\textsf{WindNum}(\bar{S},\bar{Q})|$. It is at most the sum of
$|\textsf{WindNum}(S,Q)|$ and the absolute value of the winding numbers
between the two middle subsegments, the two prefixes, and the two suffixes. We
show that the absolute value of the winding number between each pair of pieces
is $2^{O(k)}$. Note that, by construction $|\textsf{WindNum}(S,Q)|\leq 7$.

We first show that $|\textsf{WindNum}(S_{\textsf{pre}},Q_{\textsf{pre}})|$ is
at most $2^{O(k)}$. By the definition, two prefixes are segments of traversing
segments in $\textsf{Ring}(C_{i},B_{i})$. Note that, By the tightness, there
is a radial curve $\mu$ connecting $C_{i}$ and $B_{i}$ whose length is at most
$2^{O(k)}$ in $\textsf{Ring}(C_{i},B_{i})$. Note that
$|\textsf{WindNum}(S_{\textsf{pre}},\mu)|$ and
$|\textsf{WindNum}(Q_{\textsf{pre}},\mu)|$ are at most the complexity of
$\mu$, which is $2^{O(k)}$. Furthermore, by Proposition 7.1 in [21],
$|\textsf{WindNum}(S_{\textsf{pre}},Q_{\textsf{pre}})|$ differs by at most one
from the sum of $|\textsf{WindNum}(S_{\textsf{pre}},\mu)|$ and
$|\textsf{WindNum}(Q_{\textsf{pre}},\mu)|$. Therefore,
$|\textsf{WindNum}(S_{\textsf{pre}},Q_{\textsf{pre}})|$ is $2^{O(k)}$, and
$|\textsf{WindNum}(S_{\textsf{su}},Q_{\textsf{su}})|$ is $2^{O(k)}$.

Now we show that $|\textsf{WindNum}(\bar{S},Q_{\textsf{pre}})|$ is $2^{O(k)}$.
The crossing between $\bar{S}$ and $Q_{\textsf{pre}}$ appears in
$\textsf{Ring}(C_{i},B_{i})$. The part of $\bar{S}$ contained in
$\textsf{Ring}(C_{i},B_{i})$ has both end vertices in $V(B_{i})$. Furthermore,
the number of such subsegments is $2^{O(k)}$ since $|B_{i}|\in 2^{O(k)}$. The
absolute value of the winding number between such a subsegment and a
traversing subsegment is at most one. Thus,
$|\textsf{WindNum}(\bar{S},Q_{\textsf{pre}})|$ is $2^{O(k)}$. Analogously,
$|\textsf{WindNum}(\bar{S},Q_{\textsf{su}})|$,
$|\textsf{WindNum}(S_{\textsf{pre}},\bar{Q})|$, and
$|\textsf{WindNum}(S_{\textsf{su}},\bar{Q})|$ are also $2^{O(k)}$. Therefore,
we can conclude that the absolute value of the winding number between the
middle subsegments is $2^{O(k)}$.

###  6.2 Canonical Weak Linkage for a Base $T$-Linkage $\mathcal{P}$

In this subsection, we define a _canonical weak linkage_ $\mathcal{W}$ which
is discretely homotopic to the base $T$-linkage $\mathcal{P}$. To work with
discrete homotopy, we use the radial completion $G^{\textsf{rad}}$ of $G$.
Note that $\mathcal{P}$ is also a $T$-linkage of $G^{\textsf{rad}}$. The
frames of $G$ are nooses of $G$, thus we can consider them as cycles in
$G^{\textsf{rad}}$. For any two walks in the canonical weak linkage
$\mathcal{W}$ we construct in this subsection, an edge traversed by the walks
of $\mathcal{W}$ by more than once lies on the frames or skeleton forests
only. Moreover, no walk of $\mathcal{W}$ uses an edge of
$E(G^{\textsf{rad}})\setminus E(G)$ which does not lie on any frame or
skeleton forest. These two properties are crucial for reconstructing a
$T$-linkage of $G$ from $\mathcal{W}$ in Section 8.

To obtain $\mathcal{W}$, we first _push_ some subsegments of the segments of
$\mathcal{P}$ in each framed ring in a specific order so that no two paths of
$\mathcal{P}$ cross during the pushing procedure. For a terminal-free framed
ring, we push the subsegments of the paths of $\mathcal{P}$ oscillating around
the frames onto the frames. For a terminal-containing framed ring, we push the
minimal subsegments $\pi$ of the paths of $\mathcal{P}$ such that the end
vertices of $\pi$ lie on the same tree-path of the skeleton forest defined in
the ring.

##### Pushing Segments on a tree-path $\tau$.

For a terminal-containing ring, imagine that we cut each segment of
$\mathcal{P}$ in the ring with respect to the skeleton forest. An endpoint of
the subsegments lies on the skeleton forest or the boundary of the ring. For
the subsegments having both endpoints on the same tree-path, we push them to
the tree-path. For a tree-path $\tau$, let $L$ be the set of all minimal
subsegments $\pi$ having both endpoints on $\tau$. Note that $|L|=2^{O(k)}$
since the length of $\tau$ is $2^{O(k)}$, and the paths of $\mathcal{P}$ are
pairwise vertex-disjoint. The _base arc_ of a subsegment $\pi\in L$ is defined
as the subpath of $\tau$ having the same endpoints as $\pi$. The _order_ of
$\pi$ is defined as the number of the other subsegments in $L$ contained in
the region bounded by $\pi$ and its base arc. We push the subsegments in $L$
in the increasing order by applying the face operations. In this way, the base
$T$-linkage $\mathcal{P}$ is transformed into a weak $T$-linkage. Since we
transform $\mathcal{P}$ to the weak $T$-linkage using the face operations,
they are homotopic.

##### Pushing Segments on $B_{i}$.

For each terminal-free ring $\textsf{Ring}_{i}^{\textsf{x}}$, we first cut
each subsegment oscillating around $B_{i}$ into several _pieces_ at the
vertices intersected by $B_{i}$. Let $S_{\textsf{os}}$ be the set of all
subsegments oscillating around $B_{i}$, and let $\Pi$ be the set of all pieces
obtained from the subsequences of $S_{\textsf{os}}$ by cutting them at the
vertices intersected by $B_{i}$. Each piece $\pi$ has its _base arc_ on
$B_{i}$ and its _order_. The definition of base arcs and orders are similar to
their definitions in the proof of Lemma 14. For a piece $\pi$ oriented from
$x$ to $y$, there are two paths between $x$ and $y$ in $B_{i}$. Furthermore,
exactly one of them forms, together with $\pi$, a bounded region not
containing the interior of $C_{i}$ in its interior. We call this arc the _base
arc_ of $\pi$. We consider it as oriented from $x$ to $y$. See Figure 12(b).
We define the order of $\pi$ as the number of other pieces (which could come
from the same subsegment) whose base arcs are contained in the base arc of
$\pi$. Then we push all pieces of $\Pi$ to their base arcs in the increasing
order of their orders. We can push all pieces of $\Pi$ by applying face
operations. Therefore, the set $\mathcal{W}_{\textsf{pushed}}$ of the walks
obtained in this way is homotopic to $S_{\textsf{os}}$.

##### Eliminating “U-turns”.

At this point, a walk of $\mathcal{W}_{\textsf{pushed}}$ moves along $B_{i}$
back and forth. We further simplify the walks of
$\mathcal{W}_{\textsf{pushed}}$ by eliminating “U-turns”. To make the
description easier, for an edge of $B_{i}$ used by the walks of
$\mathcal{W}_{\textsf{pushed}}$ more than once, say $N$ times, we make $N$
copies of the edge so that they become parallel edges in $B_{i}$. The
complexity of $G^{\textsf{rad}}$ increases in this way, but our algorithm does
not compute these parallel edges. In fact, all arguments in this subsection
show the existence of a weak linkage of $G$ satisfying certain properties,
which be used only for the analysis of our algorithm. Due to the duplication
of edges, we can consider $\mathcal{W}_{\textsf{pushed}}$ as a weak _edge-
disjoint_ linkage.

Whenever two edges of a walk $W$ of $\mathcal{W}_{\textsf{pushed}}$ lying
consecutive along $W$ form a face $F$, we apply the face operation for $W$ on
$F$ so that the two consecutive edges of $W$ are eliminated. Note that this
happens only when the two edges are copies of the same edge of $G$, and $W$
traverses them in the opposite directions. See Figure 12(c). We repeat this
until no such two consecutive edges exist. Recall that we do this only for the
purpose of analysis, and thus we do not need to care about the running time of
this procedure. Let $\mathcal{W}_{\textsf{elim}}$ be the walks we obtained
from $\mathcal{W}_{\textsf{pushed}}$ by eliminating all U-turns.

######  Lemma 22.

The walks in $\mathcal{W}_{\textsf{elim}}$ are non-crossing. Moreover, either
they are vertex-disjoint paths, or they turn around $B_{i}$ in the same
direction. Moreover, the total complexity of $\mathcal{W}_{\textsf{elim}}$ is
$2^{O(k)}$.

Proof. Since pushing and eliminating U-turns keeps a homotopic relation, the
walks in $\mathcal{W}_{\textsf{elim}}$ are non-crossing. To make the
description easier, we represent the interaction between the copies of an edge
$e$ of $B_{i}$ and the walks of $\mathcal{W}_{\textsf{elim}}$ as a string over
the alphabet $\Sigma=\\{1,2,\ldots,r^{\prime}\\}$, where
$r^{\prime}=|\mathcal{W}_{\textsf{elim}}|$. Each symbol $\ell$ in the alphabet
represents the $\ell$th walk of $\mathcal{W}_{\textsf{elim}}$ for
$\ell\in[r^{\prime}]$. Assume that all edges of $B_{i}$ is oriented in
clockwise direction along $B_{i}$. A copy of $e$ has a symbol $\ell$ if the
$\ell$th walk traverses the copy of $e$ in clockwise order, and a symbol
$\ell^{-1}$ if the $\ell$th walk traverses $e$ in counterclockwise order.
Since each copy of an edge of $G$ is traversed by the walks in
$\mathcal{W}_{\textsf{elim}}$ only once, each copy of $e$ has at most one
symbol. For an edge $e$ of $G$, we define $\sigma(e)$ as a sequence of symbols
of the copies of $e$ in the order.

We first claim that $\sigma(e)$ does not contain $\ell\ell^{-1}$ or
$\ell^{-1}\ell$ as its substring for any $\ell\in\Sigma$. Assume to the
contrary that there exists an edge $e$ whose string $\sigma(e)$ has a
substring $\ell\ell^{-1}$. Let $W$ be the $\ell$th walk of
$\mathcal{W}_{\textsf{elim}}$. Imagine that we walk along $W$ from the copy of
$e$ contributing to $\ell$ to the copy of $e$ contributing to $\ell^{-1}$.
Then there must be an edge $e^{\prime}$ of $G$ such that $W$ traverses two
copies of $e^{\prime}$ in the opposite directions consecutively. Moreover,
since the copies of $e$ contributing to $\ell$ and $\ell^{-1}$ are consecutive
among all copies of $e$, the copies of $e_{1}$ traversed by $W$ are also
consecutive among all copies of $e_{1}$. Therefore, the two copies of
$e^{\prime}$ form a U-turn. The elimination step removes all U-turns, and thus
this makes a contradiction.

Moreover, $\sigma(e)$ contains at most one of $\ell$ and $\ell^{-1}$ for all
$\ell\in\Sigma$. To see this, assume to the contrary that a copy of $e$ has
symbol $\ell$ (or $\ell^{-1}$) and another copy of $e$ has symbol $\ell^{-1}$
(or $\ell$). Among all substrings of $\sigma(e)$ starting with $\ell$ (or
$\ell^{-1}$) and ending at $\ell^{-1}$ (or $\ell$) for a symbol
$\ell\in\Sigma$, we choose a shortest one $\sigma^{\prime}(e)$. If
$\sigma^{\prime}(e)$ has length two, it means
$\sigma^{\prime}(e)=\ell\ell^{-1}$ or $\ell^{-1}\ell$, and it contradicts the
claim we proved earlier. Thus, we assume that $\sigma^{\prime}(e)$ has length
larger than two. This means that there is another symbol $\ell_{1}$ or
$\ell_{1}^{-1}$ in $\sigma^{\prime}(e)$. Without loss of generality, assume
that $\sigma(e)$ starts with $\ell$ and ends with $\ell^{-1}$. Furthermore,
$\ell_{1}\in\sigma(e)$. The other cases can be handled analogously.

Figure 13: (a) The blue line is $W$ and the red line is $W_{1}$. $W_{1}$
leaves the frame $B_{i}$ at $p$ that must cross with $W$. (b) The case where
$W_{1}$ has the counterclockwise direction at $p$ makes a U-turn. (c) The blue
line is $W$ and the red line is $W^{\prime}$. $W$ traverse $B_{i}$ in
counterclockwise direction and $W^{\prime}$ traverse $B_{i}$ in clockwise
direction. The $W^{\prime}$ must cross with $W$ for leaving or entering the
frame.

Let each $W$ and $W_{1}$ be the $\ell$th and $\ell_{1}$th walk of
$\mathcal{W}_{\textsf{elim}}$. Similarly to the earlier proof, we walk along
$W_{1}$ from a copy of $e$. The copy of $e$ contributing to $\ell_{1}$ lies
between two copies of $e$ contributing to each $\ell$ and $\ell^{-1}$. Thus,
the copies of $e_{1}$ traversed by the walk along $W_{1}$ lies between two
copies of $e_{1}$ contributing to each of $\ell$ and $\ell^{-1}$. Since $W$
and $W_{1}$ are non-crossing walks, $W_{1}$ ends $p$ which has 4 incident
edges in $W$ or traverses another copy of $e$ with opposite direction between
$W$. The second case means that $\sigma(e)$ has $\ell_{1}^{-1}$ also. This
contradicts that $\sigma(e)$ is the shortest one. We consider the first case.
By the definition of $\mathcal{W}_{\textsf{elim}}$, the path corresponded by
$W_{1}$ leaves the frame $B_{i}$ at $p$. Since the walk $W_{1}$ is surrounded
by $W$ at $p$, the path must cross with $W$ to leave the frame. This
contradicts to the non-crossing condition. See Figure 13(a,b).

We have shown that, each walk $W$ in $\mathcal{W}_{\textsf{elim}}$ traverses
$B_{i}$ in clockwise or counterclockwise direction. Now we show that two walks
$W$ and $W^{\prime}$ traverse $B_{i}$ in the same direction if they traverse
two copies of a common edge $e\in B_{i}$. We suppose that $W$ traverses
$B_{i}$ in counterclockwise direction and $W^{\prime}$ traverses $B_{i}$ in
clockwise direction. Let $\ell$ and $\ell^{\prime}$ be the indices of $W$ and
$W^{\prime}$ in $\mathcal{W}_{\textsf{elim}}$. We consider the maximal
substring $\sigma^{\prime}(e)$ of $\sigma(e)$ which starts with $\ell^{-1}$ or
$\ell^{\prime}$. Without loss of generality, we assume that it starts with
$\ell^{-1}$. This means that the subwalk of the reverse of $W^{\prime}$ must
cross the walk $W$. This contradicts to the fact that $W$ and $W^{\prime}$ are
non-crossing. See Figure 13(c).

The remaining task is to bound the complexity of
$\mathcal{W}_{\textsf{elim}}$. The complexity of $\mathcal{W}_{\textsf{elim}}$
is at most the sum of length of the base arcs of $S_{\textsf{os}}$. The number
of subsegments in $S_{\textsf{os}}$ is at most $|B_{i}|$. Furthermore, the
length of each base arc is also at most $|B_{i}|$. Thus, the complexity of
$\mathcal{W}_{\textsf{elim}}$ is at most $|B_{i}|^{2}\in 2^{O(k)}$. This
proves the lemma.

We replace each oscillating segment of $\mathcal{S}_{\textsf{os}}$ with its
corresponding walk in $\mathcal{W}_{\textsf{elim}}$. We do this for
$B_{i}^{\prime}$, and We also do this for all rings
$\textsf{Ring}(C_{i},C_{i}^{\prime})$ with $i\in[k^{\prime}]$. The resulting
weak $T$-linkage is called the _canonical_ weak $T$-linkage for $\mathcal{P}$.
Note that an edge (and a vertex) of $G$ traversed by the walks in the
canonical weak linkage $\mathcal{W}$ more than once lies on frames of
$\mathcal{B}$. Also, no walk of $\mathcal{W}$ uses an edge of
$E(G^{\textsf{rad}})\setminus E(G)$ which does not lie on any frame.

######  Lemma 23.

No maximal subwalk of the walks of $\mathcal{W}$ contained in
$\textsf{Ring}_{i}^{\textsf{o}}\setminus(E(B_{i-1}^{\prime})\cup E(B_{i}))$
has their endpoints on the same boundary-path or the same tree-path.

###  6.3 Crossing Pattern with respect to Abstract Polygonal Schema

Now we are ready to define the crossing pattern of the canonical weak linkage
$\mathcal{W}$ of $\mathcal{P}$. To do this, we encode the information on the
interaction between $\mathcal{W}$ and each framed ring. In the following, we
let
$\textsf{Ring}_{i}^{\textsf{o}}=\textsf{Ring}(B_{i-1}^{\prime},B_{i})\setminus(E(B_{i-1}^{\prime})\cup
E(B_{i}))$ and
$\textsf{Ring}_{i}^{\textsf{x}}=\textsf{Ring}(B_{i},B_{i}^{\prime})$. In this
way, each edge of $E(G^{\textsf{rad}})$ belongs to exactly one of the framed
rings. Note that $\textsf{Ring}_{i}^{\textsf{o}}$ contains a terminal of
$\bar{T}$, but $\textsf{Ring}_{i}^{\textsf{x}}$ contains no terminal of
$\bar{T}$. Moreover, the radial distance between $B_{i-1}^{\prime}$ and
$B_{i}$ is $2^{O(k)}$ by construction. That is, the shortest path in
$G^{\textsf{rad}}$ between a vertex of $B_{i-1}^{\prime}$ and a vertex in
$B_{i}$ is $2^{O(k)}$.

##### Interaction between $\mathcal{W}$ and $\textsf{Ring}_{i}^{\textsf{o}}$.

A maximal subwalk $W$ of a walk in $\mathcal{W}$ contained in
$\textsf{Ring}_{i}^{\textsf{o}}$ has endpoints on the frames or the terminals.
Also, no edge of the frames are included in $\textsf{Ring}_{i}^{\textsf{o}}$.

Figure 14: (a) The black lines are tree-paths in $\Gamma_{i}$, and the dashed
lines are boundary-paths. The colored vertices of the leaf nodes in
$\Gamma_{i}$ are terminals. (b) By cutting $\textsf{Ring}_{i}^{\textsf{o}}$
along $\Gamma_{i}$, every terminal lies on the boundary, and each tree-path
appears exactly twice. (c) The black vertices are tree-paths, the squares are
boundary-paths, and the colored vertices are terminals in
$\textsf{Ring}_{i}^{\textsf{o}}$.

We first cut $\textsf{Ring}_{i}^{\textsf{o}}$ along the skeleton forest
$\Gamma_{i}$ of $\textsf{Ring}_{i}^{\textsf{o}}$ so that every terminal in
$\textsf{Ring}_{i}^{\textsf{o}}$ lies on the boundary of
$\textsf{Ring}_{i}^{\textsf{o}}$ and each tree-path appears exactly twice. See
Figure 14. Since the complexity of $\Gamma_{i}$ is $2^{\Theta(k)}$ in the
worst case, we represent it in a more compact way as an _abstract polygonal
schema_ $\Delta_{i}$: a convex polygon with $O(k_{i})$ vertices, where $k_{i}$
denotes the number of terminals in $\textsf{Ring}_{i}^{\textsf{o}}$. This idea
also used in [12] for computing shortest non-crossing walks in a planar graph.
Each vertex of $\Delta_{i}$ corresponds to a tree-path, a boundary-path, or a
vertex of $\Gamma_{i}$ of degree one or degree at least three. A maximal
subwalk $W$ of a walk of $\mathcal{W}$ contained in
$\textsf{Ring}_{i}^{\textsf{o}}$ corresponds to a diagonal of $\Delta_{i}$ due
to Lemmas LABEL:lem:visitor-oring and 23. Note that two distinct maximal
subwalk of a walk of $\mathcal{W}$ might correspond to the same diagonal of
$\Delta_{i}$. We define the _weight_ of a diagonal of $\Delta_{i}$ as the
number of distinct maximal subwalks of the walks of $\mathcal{W}$
corresponding to the diagonal. Note that each diagonal has weight $2^{O(k)}$.
In this way, the interaction between $\mathcal{W}$ and
$\textsf{Ring}_{i}^{\textsf{o}}$ is encoded as a weighted triangulation of
$\Delta_{i}$.

##### Interaction between $\mathcal{W}$ and $\textsf{Ring}_{i}^{\textsf{x}}$.

A maximal subwalk $\omega$ of a walk of $\mathcal{W}$ contained in
$\textsf{Ring}_{i}^{\textsf{x}}$ has one endpoint on $V(B_{i})$ and the other
endpoint on $V(B_{i}^{\prime})$. But in this case, the edges of the frames
$B_{i}$ and $B_{i}^{\prime}$ are included in $\textsf{Ring}_{i}^{\textsf{x}}$.
Therefore, $\omega$ first rotates around $B_{i}$ several times, and then it
departs from $B_{i}$. Then it hits $B_{i}^{\prime}$, and then rotates around
$B_{i}^{\prime}$ several times. Since $\textsf{Ring}_{i}^{\textsf{x}}$ is
terminal-free, it suffices to record the winding numbers of the maximal walks
as the crossing pattern.

Let $\mathcal{W}^{i}=\langle\omega^{1},\ldots,\omega^{\ell}\rangle$ be the
sequence of maximal walks of the walks of $\mathcal{W}$ in
$\textsf{Ring}_{i}^{\textsf{x}}$ sorted in sorted along the their endpoints in
$V(B_{i})$. Also, let $\mathcal{W}^{i}_{\textsf{mid}}$ be the sequence of the
subsegments of $\omega^{j}$’s excluding the prefixes and suffixes of the walks
of $\mathcal{W}^{i}$. Also, let $Q_{\textsf{mid}}$ be the part of the initial
path of $\mathcal{Q}_{i}$ excluding its prefix and its suffix. As the crossing
pattern, we first record $\ell$, the size of $\mathcal{W}^{i}$. Then we record
$\textsf{WindNum}(\omega,Q_{\textsf{mid}})$ for all subsegments $\omega$ of
$\mathcal{W}^{i}_{\textsf{mid}}$ in a _compact_ way. There exists a
$\omega_{j}$ in $\mathcal{W}^{i}_{\textsf{os}}$ (and
$\mathcal{W}^{i}_{\textsf{os}}$) such that
$\textsf{WindNum}(\omega_{j^{\prime}},Q_{\textsf{mid}})$ is the same for all
$j^{\prime}\leq j$, and
$\textsf{WindNum}(\omega_{j^{\prime\prime}},Q_{\textsf{mid}})$ is the same for
all $j^{\prime\prime}>j$ by the proof of Lemma 22. Therefore, it is sufficient
to record the index $j$, $\textsf{WindNum}(\omega_{j},Q_{\textsf{mid}})$, and
$\textsf{WindNum}(\omega_{j+1},Q_{\textsf{mid}})$.

The crossing pattern of $\mathcal{W}$ consists of the weighted triangulations
for all terminal-containing framed rings $\textsf{Ring}_{i}^{\textsf{o}}$ and
the two components of the encoding for all terminal-free framed rings
$\textsf{Ring}_{i}^{\textsf{x}}$.

######  Lemma 24.

We can enumerate $2^{O(k^{2})}$ different crossing patterns in $2^{O(k^{2})}n$
time one of which is the crossing pattern of the canonical weak linkage of a
base $T$-linkage.

Proof. To enumerate crossing patterns, we first compute $\Delta_{i}$ for all
terminal-containing framed rings $\textsf{Ring}_{i}^{\textsf{o}}$ in
$2^{O(k)}n$ time. Also, we compute the set $\mathcal{Q}_{i}$ of the reference
paths for all terminal-free framed rings $\textsf{Ring}_{i}^{\textsf{x}}$ in
$2^{O(k)}n$ time. Then for each index $i$, we decompose the initial path of
$\mathcal{Q}_{i}$ into five pieces: the prefix, suffix, oscillating
subsequences, and traversing subsequences. This also takes $2^{O(k)}n$ time.

We first analyze the number of different crossing patterns for the terminal-
containing rings. The crossing pattern for each ring
$\textsf{Ring}_{i}^{\textsf{o}}$ is a weighted triangulation of $\Delta_{i}$.
Recall that the complexity of $\Delta_{i}$ is $O(k_{i})$, where $k_{i}$
denotes the number of terminals contained in $\textsf{Ring}_{i}^{\textsf{o}}$.
Also, the weight of each diagonal of $\Delta_{i}$ is $2^{O(k)}$. The number of
distinct triangulations of $\Delta_{i}$ is $2^{O(k_{i})}$. For a fixed
triangulation, the number of distinct combinations of the weights of the
diagonals is $(2^{O(k)})^{O(k_{i})}$ since $\Delta_{i}$ has $O(k_{i})$
diagonals. The total number of different crossing patterns for all terminal-
containing rings is $\prod_{i}(2^{O(k)})^{O(k_{i})}=2^{O(k^{2})}$ since the
sum of $k_{i}$ for all terminal-containing rings is $k$.

Now we analyze the number of different crossing patterns for the terminal-free
framed rings. Recall that the number of terminal-free framed rings is at most
$k$. As the crossing pattern, we record the number of walks, and a specific
index of the walks and the winding numbers of two specific walks, which are
all integers of $2^{O(k)}$. The number of combinations of the four integers
for all terminal-free rings is $(2^{O(k)})^{k}=2^{O(k^{2})}$. Therefore, the
total number of distinct crossing patterns for all terminal-free framed rings
is $2^{O(k^{2})}$.

Therefore, the total number of different crossing patterns is $2^{O(k^{2})}$,
and we can enumerate each crossing pattern in time linear in the complexity of
the crossing pattern. Therefore, in total, we can enumerate all crossing
patterns in $2^{O(k^{2})}n$ time.

##  7 Reconstructing a Weak Linkage from a Crossing Pattern

In this subsection, given a crossing pattern $\sigma$, we show how to compute
a weak $T$-linkage $\mathcal{W}$ homotopic to a $T$-linkage $\mathcal{P}$
whose crossing pattern is $\sigma$. The weak linkage $\mathcal{W}$ which we
will construct in this subsection might traverse the same vertex more than
once. But in this case, such a vertex lies on a frame. Recall that the total
complexity of the frames is $2^{O(k)}$, which will be crucial to reconstruct a
$T$-linkage from a weak $T$-linkage efficiently in Section 8.

We compute the subwalks of the walks of $\mathcal{W}$ contained in each framed
ring, and then we merge the subwalks from two framed rings so that they become
a weak $T$-linkage. To make the merge procedure easier, for a frame $B_{i}$
(and $B_{i}^{\prime}$), we contract all edges on $B_{i}$ (and
$B_{i}^{\prime}$) so that $B_{i}$ (and $B_{i}^{\prime}$) consists a single
loop with both endpoints on the origin of $B_{i}$ (and $B_{i}^{\prime}$). Let
$G_{\textsf{contract}}$ be the plane graph obtained from $G$ by contracting
all edges on the frames. A weak linkage of $G_{\textsf{contract}}$ corresponds
to a weak linkage of $G$ in a straightforward way. Moreover, if two weak
linkages of $G_{\textsf{contract}}$ are homotopic, then their corresponding
weak linkages in $G$ are also homotopic.

In the following, we consider $\textsf{Ring}_{i}^{\textsf{o}}$ and
$\textsf{Ring}_{i}^{\textsf{x}}$ as the framed rings of
$G_{\textsf{contract}}$. Also, we let $\mathcal{W}$ be the weak $T$-linkage we
are going to construct in this section.

Figure 15: (a) The reconstruction of $\mathcal{W}$ in the case that
$\textsf{WindNum}(\omega,Q_{\textsf{mid}})=-2$ for all
$\omega\in\mathcal{W}_{\textsf{mid}}$, and
$\textsf{WindNum}(Q,Q_{\textsf{mid}})=0$ for all
$Q\in\mathcal{Q}_{\textsf{mid}}$. (b) The reconstruction of $\mathcal{W}$ in
the case that $\textsf{WindNum}(\omega,Q_{\textsf{mid}})=0$ for all
$\omega\in\mathcal{W}$, and $\textsf{WindNum}(Q,Q_{\textsf{mid}})=-1$ for
exactly one middle subsequences $Q$ of $\mathcal{Q}_{\textsf{mid}}$.

##### Reconstructing a Weak Linkage lying on $\textsf{Ring}_{i}^{\textsf{x}}$.

Let $\mathcal{Q}_{i}$ be the set of reference paths of
$\textsf{Ring}_{i}^{\textsf{x}}$, and let $\mathcal{Q}_{\textsf{mid}}$ be the
middle subsequences of the reference paths. Let $Q_{\textsf{mid}}$ be the
middle subsegment of the initial path of $\mathcal{Q}_{i}$. Also, let
$\mathcal{W}_{\textsf{mid}}=\langle\omega_{1},\ldots,\omega_{\ell}\rangle$ be
the set of middle subsegments of the walks of $\mathcal{W}$.

As the crossing pattern for $\textsf{Ring}_{i}^{\textsf{x}}$, we are given the
size of $\mathcal{W}_{\textsf{mid}}$, and the winding numbers of
$\mathcal{W}_{\textsf{mid}}$ with respect to $Q_{\textsf{mid}}$. We can
construct $\ell$ walks each of which traverses $B_{i}$ (which is a loop)
several times, and then traverses a path of $\mathcal{Q}_{\textsf{mid}}$ due
to Lemma 25.

######  Lemma 25.

For any crossing pattern in $\textsf{Ring}_{i}^{\textsf{x}}$, we can
reconstruct a weak linkage $\mathcal{W}_{\textsf{mid}}$ having the given
crossing pattern in time linear in $2^{O(k)}n$ time.

Proof. Our goal is to compute $\omega_{x}$ for all $x\in[\ell]$, where
$\mathcal{W}_{\textsf{mid}}=\langle\omega_{1},\ldots,\omega_{\ell}\rangle$.
Note that $\mathcal{W}_{\textsf{mid}}$ and $\mathcal{Q}_{i}$ are sorted along
its end vertices in clockwise order. There are two tasks to construct
$\omega_{x}$: first, we are required to decide which walk of
$\mathcal{Q}_{\textsf{mid}}$ $\omega$ traverses. Next, we are required to
determine how many times $\omega$ traverses around $B_{i}$. These canbe
determined by looking at the winding numbers of
$\omega_{1},\dots,\omega_{\ell}$. Without loss of generality, we assume that
the winding number for the walks $\omega_{1},\dots\omega_{j}$ is $N$ and for
the others $\omega_{j+1},\dots\omega_{\ell}$ is $(N-1)$. Otherwise, we can
rotate $\mathcal{W}$ and $\mathcal{W}_{\textsf{mid}}$ (Recall that
$\mathcal{W}$ is a cyclic sequence). Analogously, we assume that the last path
$Q_{-1}$ of $\mathcal{Q}_{\textsf{mid}}$ has the largest winding number with
respect to the initial path $Q_{1}$ of $\mathcal{Q}_{\textsf{mid}}$.

We construct the $x$th walk $\omega_{x}$ of $\mathcal{W}_{\textsf{mid}}$ as
follows: we first traverse $B_{i}$ in clockwise direction
$(N_{x}-q_{x})$-times and then traverse $Q_{x}$, where $N_{x}$ and $q_{x}$ be
the winding numbers of $\omega_{x}$ and $Q_{x}$, respectively, with respect to
the initial path of $\mathcal{Q}_{\textsf{mid}}$. For illustration, see Figure
15. The constructed weak linkage $\mathcal{W}_{\textsf{mid}}$ has the give the
crossing pattern.

In this way, we can construct $\ell$ walks in $\textsf{Ring}_{i}^{\textsf{x}}$
such that the winding numbers with respect to $Q_{\textsf{mid}}$ are
determined in the same way as the crossing pattern for
$\textsf{Ring}_{i}^{\textsf{x}}$.

##### Reconstructing a Weak Linkage Lying on $\textsf{Ring}_{i}^{\textsf{o}}$.

Recall that the crossing pattern for $\textsf{Ring}_{i}^{\textsf{o}}$ is a
weighted triangulation of $\Delta_{i}$. To obtain a weak linkage on
$\textsf{Ring}_{i}^{\textsf{o}}$, we use Lemma 26. We construct $G^{\prime}$
and $T^{\prime}$ satisfying the condition of Lemma 26 as follows. Recall that
every vertex of $\Pi_{i}$ corresponds to a boundary-path, a tree-path, or a
degree-1 vertex of the forest $\Gamma$. We first compute $\Gamma$, and cut
$\textsf{Ring}_{i}^{\textsf{o}}$ along $\Gamma$ so that the tree-paths of
$\Gamma$ appear exactly twice, and they become incident to the outer face of
the resulting graph. Let $\textsf{Ring}_{i}^{\textsf{cut}}$ be the resulting
graph. Then we contract all the edges in each tree-path of $\Gamma$ on
$\textsf{Ring}_{i}^{\textsf{cut}}$. Let $G^{\prime}$ be the resulting graph. A
vertex of $G^{\prime}$ lying on the outer face corresponds to a vertex of
$\Delta_{i}$. Then a diagonal of $\Delta_{i}$ corresponds to a vertex pair or
$G^{\prime}$. We let $T^{\prime}$ be the set of all diagonals (pairs of
vertices of $G^{\prime}$) of the weighted triangulation of $\Delta_{i}$ in the
crossing pattern. If the diagonal (vertex pair) of the triangulation of
$\Delta_{i}$ has weight $w$, we add $w$ copies of the vertex pair to
$T^{\prime}$.

By applying Lemma 26 to $(G^{\prime},T^{\prime})$, we can compute a weak
$T^{\prime}$-linkage of $G^{\prime}$ such that the paths of the weak linkage
are vertex-disjoint and edge-disjoint, except for their endpoints, in
$2^{O(k)}n$ time. Then we “uncontract” the vertices of $G^{\prime}$ to
reconstruct $\textsf{Ring}_{i}^{\textsf{cut}}$. In this way, the walks of the
weak $T^{\prime}$-linkage of $G^{\prime}$ becomes the walks of
$\textsf{Ring}_{i}^{\textsf{cut}}$ accordingly. Then we reconstruct
$\textsf{Ring}_{i}^{\textsf{o}}$ from $\textsf{Ring}_{i}^{\textsf{cut}}$ by
“uncutting” the boundary edges of $\textsf{Ring}_{i}^{\textsf{cut}}$ along
$\Gamma$. They form a weak linkage $\mathcal{W}_{i}^{\textsf{o}}$ of
$\textsf{Ring}_{i}^{\textsf{o}}$ such that any two such walks traverse the
same vertex only at the origins of the frames and $\Gamma$.

######  Lemma 26.

Let $G^{\prime}$ be a planar graph with $n$ vertices, and $T^{\prime}$ be a
(multi)set of terminal pairs such that the terminals are incident to the outer
face of $G$. Then we can find a weak $T^{\prime}$-linkage such that the walks
of the weak linkage are vertex-disjoint (and also edge-disjoint), except for
their endpoints, in $O(n|T^{\prime}|)$ time, if it exists.

Proof. We assume that $G^{\prime}$ is connected. Otherwise, we consider each
component independently. Let $C$ be the boundary cycle which incident to the
outer face. Every terminals are contained in $C$. We say two terminal nodes
$t$ and $t^{\prime}$ in $T^{\prime}$ is consecutive if $t^{\prime}$ be the
very first terminal node from $t$ in clockwise (or counterclockwise) direction
along $C$.

Our algorithm works as follows: choose a terminal pair $(t,t^{\prime})\in
T^{\prime}$ which consecutive, and compute the path between $t$ and
$t^{\prime}$ along the outer face of $G^{\prime}$ in the clockwise direction.
If there is not such consecutive terminal pair, then we return NO. Then we
remove internal vertices and edges of the path from $G^{\prime}$, and remove
$(t,t^{\prime})$ from $T^{\prime}$. Furthermore, if a vertex $t$ has no pair
in $T^{\prime}$, we delete $t$ also. Even if the obtained $G^{\prime}$ is not
connected, we can consider each connected component separately. We repeat this
procedure until $T^{\prime}$ becomes empty. Let $\mathcal{W}$ be the weak
$T^{\prime}$-linkage obtained in this way. Then the walks of $\mathcal{W}$ are
vertex-disjoint and edge-disjoint, except for their endpoints.

We show that, if the instance is a YES-instance, then there exists a pair
$(t,t^{\prime})$ in $T^{\prime}$ such that $t$ and $t^{\prime}$ lie
consecutively along $C$. We assume to the contrary that there is a solution
$\mathcal{W}$ to the instance, but there is no such terminal pair in
$T^{\prime}$. Then for any pair $a=(t,t^{\prime})$, $G^{\prime}$ is separated
by two subgraphs with respect to the path of $\mathcal{W}$ connecting $t$ and
$t^{\prime}$. Let $\pi_{a}$ and $\pi_{a}^{\prime}$ be the parts of $C$
contained in the two subgraphs. We define the _order_ of a pair
$a=(t,t^{\prime})\in T^{\prime}$ as the minimum of $|V(\pi_{a})\cap\bar{T}|$
and $|V(\pi_{a}^{\prime})\cap\bar{T}|$. Let $a=(t,t^{\prime})$ be the pair of
$T^{\prime}$ with a smallest order. Without loss of generality, we assume that
$\pi_{a}$ contains a smaller number of terminals than $\pi_{a}^{\prime}$. Let
$W$ be the path in $\mathcal{W}$ connecting $t$ and $t^{\prime}$. If there
exists a terminal pair in $T^{\prime}$ consisting of two terminals contained
in different paths among $\pi_{a}$ and $\pi_{a}^{\prime}$, then any path
connecting them crosses $W$. Thus, for every pair in $T^{\prime}$, the two
terminals of the pair are contained in the same path among $\pi_{a}$ and
$\pi_{a}^{\prime}$. If there is no terminal pair in $T^{\prime}$ whose
terminals are contained in $\pi_{a}$, this contradicts to the assumption that
$t$ and $t^{\prime}$ does not lie consecutively along $C$. If it is not the
case, there is a terminal pair whose terminals are contained in $\pi_{a}$,
this contradicts that $(t,t^{\prime})$ is a pair with a smallest order. Thus,
there exists a terminal pair in $T^{\prime}$ whose terminals lie consecutively
along $C$ if the given instance is a YES-instance.

Now we show that the algorithm returns a feasible solution if there exists a
feasible weak $T^{\prime}$-linkage $\mathcal{W}$. Let $(t,t^{\prime})$ be a
terminal pair in $T^{\prime}$ such that $t$ and $t^{\prime}$ lie on $C$
consecutively. We claim that $\mathcal{W}$ remains to be a weak
$T^{\prime}$-linkage even after we replace $\omega$ with $\omega^{\prime}$,
where $\omega$ is the walk of $\mathcal{W}$ between $t$ and $t^{\prime}$, and
$\omega^{\prime}$ is the walk connecting $t$ and $t^{\prime}$ returned by our
algorithm. Note that $\omega$ and $\omega^{\prime}$ form a bounded face whose
boundary and interior have no terminal node, except $t$ and $t^{\prime}$.
Thus, if there exists another walk in $\mathcal{W}$ which intersects
$\omega^{\prime}$, it would touch $\omega^{\prime}$ first. This contradicts
the fact that the walks in $\mathcal{W}$ are vertex-disjoint (except for their
endpoints). Thus, $\mathcal{W}$ remains to be a weak $T^{\prime}$-linkage even
after we replace $\omega$ with $\omega^{\prime}$.

In each iteration, we find a consecutive terminal pair and a path connecting
them along $C$ in $O(n)$ time. The number of iterations is $O(|T^{\prime}|)$
since we we remove one terminal pair in each iteration. Therefore, the total
running time is $O(n|T^{\prime}|)$.

##### Merging the Subwalks Obtained from Each Framed Ring.

We simply merge all subwalks obtained from the framed rings. Since each frame
forms a loop in $G_{\textsf{contract}}$, we can merge them in a
straightforward way. Also, clearly, the resulting walks, say $\mathcal{W}$,
are non-crossing. Then we “uncontract” the loops of $G_{\textsf{contract}}$ so
that each loop becomes a cycle of $G^{\textsf{rad}}$. Then $\mathcal{W}$ are
“uncontracted” accordingly, and it becomes a weak $T$-linkage of $G$ such that
an edge traversed by the resulting weak linkage more than once lies on the
frames and the backbone forest.

This section is summarized in the following lemma.

######  Lemma 27.

Given a crossing pattern $\sigma$, we can compute a weak $T$-linkage
$\mathcal{W}$ of $G^{\textsf{rad}}$ in $2^{O(k)}n$ time whose crossing pattern
is $\sigma$ such that an edge of $G^{\textsf{rad}}$ traversed by $\mathcal{W}$
more than once lies on a frame or a skeleton forest, and an edge of
$E(G^{\textsf{rad}})\setminus E(G)$ traversed by $\mathcal{W}$ lies on a