# Planar Disjoint Paths, Treewidth, and Kernels

Michał Włodarczyk111Address<EMAIL_ADDRESS>
Ben Gurion University  Meirav Zehavi222Address<EMAIL_ADDRESS>
Ben Gurion University

###### Abstract

In the Planar Disjoint Paths problem, one is given an undirected planar graph
with a set of $k$ vertex pairs $(s_{i},t_{i})$ and the task is to find $k$
pairwise vertex-disjoint paths such that the $i$-th path connects $s_{i}$ to
$t_{i}$. We study the problem through the lens of kernelization, aiming at
efficiently reducing the input size in terms of a parameter. We show that
Planar Disjoint Paths does not admit a polynomial kernel when parameterized by
$k$ unless coNP $\subseteq$ NP/poly, resolving an open problem by [Bodlaender,
Thomassé, Yeo, ESA’09]. Moreover, we rule out the existence of a polynomial
Turing kernel unless the WK-hierarchy collapses. Our reduction carries over to
the setting of edge-disjoint paths, where the kernelization status remained
open even in general graphs.

On the positive side, we present a polynomial kernel for Planar Disjoint Paths
parameterized by $k+\mathsf{tw}$, where $\mathsf{tw}$ denotes the treewidth of
the input graph. As a consequence of both our results, we rule out the
possibility of a polynomial-time (Turing) treewidth reduction to
$\mathsf{tw}=k^{\mathcal{O}(1)}$ under the same assumptions. To the best of
our knowledge, this is the first hardness result of this kind. Finally,
combining our kernel with the known techniques [Adler, Kolliopoulos, Krause,
Lokshtanov, Saurabh, Thilikos, JCTB’17; Schrijver, SICOMP’94] yields an
alternative (and arguably simpler) proof that Planar Disjoint Paths can be
solved in time $2^{\mathcal{O}(k^{2})}\cdot n^{\mathcal{O}(1)}$, matching the
result of [Lokshtanov, Misra, Pilipczuk, Saurabh, Zehavi, STOC’20].

##  1 Introduction

Disjoint Paths is a fundamental routing problem: for several decades, it has
been extensively studied in a wide variety of areas in computer science and
graph theory. We focus on the area of algorithm design, specifically of
parameterized algorithms. Phrased as a parameterized problem, given an
$n$-vertex undirected graph $G$ and a set of $k$ pairwise disjoint vertex
pairs, $\\{s_{i},t_{i}\\}^{k}_{i=1}$, the objective is to decide whether there
exist $k$ pairwise vertex-disjoint paths connecting $s_{i}$ to $t_{i}$ for
each $i\in\\{1,\ldots,k\\}$. Here, the classic parameter choice is $k$. The
problem was shown to be NP-hard by Karp (attributing it to Knuth) in 1975
[59], in a follow-up paper to his classic list of 21 NP-complete problems
[58]. Since then, the problem was shown to be NP-hard on various simple graph
classes [49, 74, 80] including the class of grid graphs [64], a highly
restricted subclass of planar graphs. Notably, Disjoint Paths is a cornerstone
for the widely celebrated graph minors project of Robertson and Seymour,
considered to be one of the greatest feats of modern mathematics (see Section
1.5). Moreover, Disjoint Paths finds applications in various practical fields
such as VLSI layout and virtual circuit routing [42, 82, 92, 93].

Due to its computational hardness, Disjoint Paths was studied from the
perspectives of parameterized complexity and approximation algorithms. In
particular, Disjoint Paths was shown to be in FPT (that is, solvable in time
$f(k)\cdot n^{O(1)}$ for some computational function $f$ of $k$) in 1995 as
part of the graph minors project [88], being one of the first problems
classified in FPT. Here, the polynomial is $n^{3}$. In 2012, the polynomial
was improved to $n^{2}$ [60]. Unfortunately, the dependency on $k$ in both
algorithms is “galactic” [68, 57], being a tower of exponents. Concerning
approximation algorithms, the state-of-the-art is grim as well: despite
substantial efforts, the currently best-known approximation algorithm is still
a simple greedy one that achieves a ratio of $O(\sqrt{n})$ [63].

We focus on Planar Disjoint Paths, the most well-studied special case of
Disjoint Paths, where the input graph is restricted to be planar.
Understanding this special case is critical for algorithms for Disjoint Paths,
Minor Testing and Topological Minor Testing on general graphs (see Section
1.5). Moreover, it finds most of the general case’s applications. Fortunately,
this special case is known to be more tractable than the general one. Already
in the 90s, Disjoint Paths on planar [85, 86] and bounded genus graphs [85,
31, 62] were shown to admit algorithms with running times whose dependency on
$n$ in linear. Regarding the dependency on $k$, the state-of-the-art for
Planar Disjoint Paths is $2^{O(k^{2})}\cdot n^{O(1)}$ [71], improving upon
earlier works [2, 85]. Very recently, the dependency on $n$ was improved to be
linear without compromising this dependency on $k$ [17]. It is also noteworthy
that when extended to directed graphs, Planar Disjoint Paths is in FPT [24]
(and, for three decades, already known to be in XP [91]), while Disjoint Paths
is NP-hard already when $k=2$ [40]. Planar Disjoint Paths has also been
intensively studied from the perspective of approximation algorithms, with a
burst of activity in recent years. Some of the highlights of this line of
works include a polynomial-time approximation algorithm with a factor of
$n^{9/19}\log^{O(1)}n$ [19], and, under reasonable complexity-theoretic
assumptions, the proof of hardness of polynomial-time approximation within a
factor of $2^{o(\sqrt{\log n})}$ [20].

##### 1.1. Our focus: Kernelization of planar disjoint paths.

From the perspective of parameterized complexity, the (arguably) biggest open
question that remains regarding Planar Disjoint Paths is whether it admits a
polynomial kernel. Kernelization is a mathematical paradigm for the analysis
of preprocessing procedures [36]. Due to the profound impact of preprocessing,
kernelization has been termed “the lost continent of polynomial time” [35].
Formally, a parameterized problem $\Pi$ admits a kernel if there is a
polynomial-time algorithm (called a kernelization algorithm) that, given an
instance $(I,k)$ of $\Pi$, translates it into an equivalent instance
$(I^{\prime},k^{\prime})$ of $\Pi$ of size $f(k)$ for some computable function
$f$ depending only on $k$. (Equivalence means that $(I,k)$ is a yes-instance
if and only if $(I^{\prime},k^{\prime})$ is a yes-instance.) A (decidable)
problem admits a kernel if and only if it is in FPT [13]. So, the central
question in kernelization is: Which problems admit kernels of size $f(k)$
where $f$ is polynomial in $k$, called polynomial kernels. Originally in 2009,
Disjoint Paths was shown not to admit a polynomial kernel with respect to $k$
unless coNP $\subseteq$ NP/poly [10, 11], being one of the first problems for
which such a result was proved. In the same paper, it was already asked
whether Planar Disjoint Paths has a polynomial kernel. Still, up until this
paper, it was not even known whether its extension to directed planar graphs
admits a polynomial kernel.

Remarkably, the literature abounds with problems that do not admit polynomial
kernels on general graphs unless coNP $\subseteq$ NP/poly, but admit
polynomial kernels on planar graphs [36]. What is more, many of them are
W[1]-hard333A W[1]-hard problem is unlikely to be in FPT [23]. or even
W[2]-hard on general graphs, while the sizes of their polynomial kernels on
planar graphs are, in fact, linear; Dominating Set is a prime example for this
phenomenon. Today, we have very general techniques to design such kernels on
planar graphs [38, 36] and there exist only few444We are aware of one example:
for Steiner Tree on planar graphs parameterized by the number of terminals,
the unlikely existence of a polynomial kernel is implied by the combination of
the lower and upper bounds given in [78]. natural problems that are in FPT on
planar graphs, but have non-trivial kernelization lower bounds. By non-trivial
we mean that the proof for planar graphs is not essentially the same as for
general graphs.

In this paper, we decipher the complexity of preprocessing procedures (kernels
and treewidth reductions) for Planar Disjoint Paths. Below, we present our
main theorems and their implications. Next, we discuss the role of our work in
the efforts of making the graph minors theory efficient.

##### 1.2. On the negative side: Our first main theorem.

First, we resolve the almost decade-and-a-half open question of whether Planar
Disjoint Paths admits a polynomial kernel with respect to $k$: unless the
polynomial hierarchy collapses, the answer is negative.

######  Theorem 1.1 (Main Theorem I).

Unless coNP $\subseteq$ NP/poly, Planar Disjoint Paths does not admit a
polynomial kernel with respect to $k$.

Our reduction also shows that Planar Disjoint Paths is WK[1]-hard555The WK-
hierarchy organizes parameterized problems with respect to polynomial
parameter transformations. WK[1]-complete problems include Set Cover (par. by
the universe size), Connected Vertex Cover (par. by the solution size), Min
Ones 3-SAT (par. by the number of 1’s in an assignment), or Binary
Nondeterministic Turing Machine Halting (par. by the number of steps)., which
means (see [50]) that it is unlikely even to admit a weaker form of a
preprocessing procedure called a polynomial Turing kernel. Formally, a
parameterized problem $\Pi$ admits a Turing kernel if there exists a
polynomial-time algorithm for $\Pi$ using an oracle that solves instances of
$\Pi$ of size at most $f(k)$ for some computable function $f$. Similarly to
standard kernelization, polynomial Turing kernel refers to the case where $f$
is polynomial in $k$. Note that a kernel is a special case of a Turing kernel
where the algorithm can perform exactly one call to the oracle. To date, we
know of many problems that admit a polynomial Turing kernel but are unlikely
to admit a polynomial kernel. This is the case for the other most famous path
problem in parameterized complexity, called $k$-Path (determine whether a
given undirected graph contains a path on $k$ vertices): while $k$-Path is
unlikely to admit a polynomial kernel when restricted to planar graphs (which
can be shown by a trivial OR-composition [36]), it does admit a polynomial
Turing kernel on planar graphs [51] or even on topological-minor-free graphs
[54]. In light of this result, we find Theorem 1.2 quite surprising.

######  Theorem 1.2.

Planar Disjoint Paths is WK[1]-hard.

Additionally, our reduction carries over to Planar Edge-Disjoint Paths, where
the solution paths are required to be edge-disjoint rather than vertex-
disjoint. Specifically, we show that it is also unlikely to admit a polynomial
kernel (or even a polynomial Turing kernel). Remarkably, prior to our work, it
was not even known whether the problem admits a polynomial kernel on general
graphs, although it was already asked as an open question close to a decade
ago [9, 49].

######  Theorem 1.3.

Unless coNP $\subseteq$ NP/poly, Planar Edge-Disjoint Paths does not admit a
polynomial kernel with respect to $k$. Moreover, Planar Edge-Disjoint Paths is
WK[1]-hard.

The Edge-Disjoint Paths problem in general, and the Planar Edge-Disjoint Paths
problem in particular, have been intensively studied in the literature (see,
e.g., [5, 15, 16, 41, 83, 60, 81, 49]), although perhaps to a lesser extent
than their vertex counterparts. We remark that the vertex and edge versions
sometimes behave very differently—for example, while Disjoint Paths is in FPT
with respect to treewidth [90], Edge-Disjoint Paths is NP-complete even on
series-parallel graphs [81] and thus on graphs of treewidth at most 2. Still,
the work of Robertson and Seymour implies that Edge-Disjoint Paths is solvable
in time $f(k)\cdot n^{3}$; later, the polynomial factor was reduced to $n^{2}$
by Kawarabayashi et al. [60].

##### 1.3. On the positive side: Our second main theorem.

We prove that Planar Disjoint Paths admits a polynomial kernel with respect to
$k+\mathsf{tw}$, where $\mathsf{tw}$ is the treewidth of the input graph.666A
trivial AND-composition [36] implies that parameterization by $\mathsf{tw}$
alone is unlikely to yield a polynomial kernel. This theorem is (arguably) the
broadest and the most involved positive result known to date regarding the
kernelization complexity of Disjoint Paths; other results in the literature
concern highly restricted graph classes: split graphs [49, 95] and well-
partitioned chordal graphs [4].

######  Theorem 1.4 (Main Theorem II).

Planar Disjoint Paths admits a polynomial kernel with respect to
$k+\mathsf{tw}$, where $\mathsf{tw}$ is the treewidth of the input graph.

The interest in the parameterization of Disjoint Paths and Planar Disjoint
Paths by $\mathsf{tw}$ stems, mainly, from the fact that all known algorithms
for these problems as well as for (Topological) Minor Testing rely on
treewidth reduction (defined below), and, in particular, require the
resolution of these problems when $\mathsf{tw}$ is small as part of their
execution (see Section 1.5). In fact, some of the running times are stated as
a function of $k+\mathsf{tw}$ rather than $k$ alone (e.g., the algorithm of
[71] is stated to run in time $\mathsf{tw}^{O(k)}\cdot n^{O(1)}$). Moreover,
treewidth is the most well-studied structural parameter is parameterized
complexity [23, 30]. It is known that Disjoint Paths parameterized by
$\mathsf{tw}$ is solvable in time $2^{O(\mathsf{tw}\log\mathsf{tw})}\cdot n$
[90], while, under the Exponential Time Hypothesis (ETH), Disjoint Paths and
Planar Disjoint Paths cannot be solved in times
$2^{o(\mathsf{tw}\log\mathsf{tw})}\cdot n^{O(1)}$ [70] and
$2^{o(\mathsf{tw})}\cdot n^{O(1)}$ [6], respectively.

A treewidth reduction for a parameterized graph problem $\Pi$ is a polynomial-
time algorithm that, given an instance $(I,k)$ of $\Pi$, translates it into an
equivalent instance of $\Pi$ where the treewidth of the new graph is bounded
by $f(k)$ for some computational function $f$ of $k$. For Disjoint Paths,
unfortunately, the best-known function is a tower of exponents [88, 60].
However, for Planar Disjoint Paths, $f(k)=2^{O(k)}$ [2]. Thus, since the
problem is solvable in time $n^{O(k)}$ [91], Theorem 1.4 yields a
$2^{O(k^{2})}\cdot n^{O(1)}$-time algorithm: Reduce the treewidth of the graph
to $2^{O(k)}$ in polynomial time [17], then run our kernelization algorithm in
polynomial time, obtaining an equivalent instance with $2^{O(k)}$ vertices,
and lastly solve the new instance in time $2^{O(k^{2})}$ using the
$n^{O(k)}$-time algorithm. This provides an alternative (and much shorter)
proof of the result of [71]. Unlike [17, 71], we use the algorithm of [91] as
a black box, so any improvement upon it (i.e., an $n^{o(k)}$-time algorithm)
would immediately entail an improvement also in the FPT running time.

######  Theorem 1.5.

The algorithm of Schrijver [91] can be used in a black-box manner to solve
Planar Disjoint Paths in time $2^{O(k^{2})}\cdot n^{O(1)}$.

##### 1.4. Implication for treewidth reductions.

A remarkable corollary of the combination of Theorems 1.1 and 1.4 rules out
the existence of a polynomial treewidth reduction: If there existed a
polynomial treewidth reduction for Planar Disjoint Paths with respect to $k$,
then combined with Theorem 1.4, this would have yielded a polynomial kernel
with respect to $k$, contradicting Theorem 1.1. This result can be viewed as a
significant strengthening of Theorem 1.1: not only we cannot efficiently
preprocess the graph so that its size will be polynomial in $k$, but we even
cannot preprocess it so that only its treewidth will be polynomial in $k$.

######  Theorem 1.6.

Unless coNP $\subseteq$ NP/poly, Planar Disjoint Paths does not admit a
polynomial treewidth reduction with respect to $k$.

To the best of our knowledge, this is the first non-trivial result of this
form,777Here, by non-trivial, we mean that the result does not follow simply
because the problem does not admit any treewidth reduction (e.g., since it is
in FPT with respect to $\mathsf{tw}$ but it is not in FPT with respect to the
parameter under consideration). although treewidth reduction is a common tool
in parameterized complexity, particularly since it is tightly linked to the
irrelevant vertex technique as well as to Bidimensionality theory [23]. We
refer to [72, 76, 52, 77, 43, 46, 37, 75, 45, 25, 26, 28] for a few
illustrative examples of treewidth reductions for problems other than Disjoint
Paths and Minor Testing. Prior to our work, there was hope that Planar
Disjoint Paths would admit a polynomial treewidth reduction with respect to
$k$—notably, coupled with the $\mathsf{tw}^{O(k)}$-time algorithm of [71],
this would have yielded a $2^{O(k\log k)}\cdot n^{O(1)}$-time algorithm.

A negative hint was given by Adler et al. [3], who constructed yes-instances
of Planar Disjoint Paths where the treewidth of the graph is $2^{\Omega(k)}$
and every vertex is relevant, that is, the removal of any vertex would turn
the instance into a no-instance. This is indeed a negative hint since all
known algorithms for (Planar) Disjoint Paths apply treewidth reduction by
iteratively finding and removing irrelevant vertices until the treewidth of
the graph becomes “small enough”. However, the result of [3] does not imply
that Planar Disjoint Paths does not admit a polynomial treewidth
reduction—indeed, it provably cannot even show that the removal of irrelevant
edges rather than irrelevant vertices is futile. To see this, consider any
yes-instance and some solution of it, and remove from the graph all the edges
that are not part of the solution (which are irrelevant edges)—then we are
left with a collection of paths, having treewidth $1$. Our result rules out
not just the success of removal of irrelevant edges, but the success of any
method implementing a polynomial treewidth reduction for Planar Disjoint
Paths. In fact, since we show that the problem is WK[1]-hard, our result even
rules out a “Turing-version” of a polynomial treewidth reduction (defined in
the natural way), strengthening Theorem 1.2.

######  Theorem 1.7.

Unless the WK-hierarchy collapses, Planar Disjoint Paths does not admit a
polynomial Turing treewidth reduction with respect to $k$.

##### 1.5. Part of the development of an efficient graph minors theory.

The concept of a minor has been extensively studied already in the early 20th
century, and it is defined as follows: A graph $H$ is a minor of a graph $G$
if $H$ can be obtained from $G$ by deleting vertices and edges, and
contracting edges. Kuratowski’s famous theorem states that a graph is planar
if and only if it does not contain the graphs $K_{3,3}$ and $K_{5}$ as
topological minors [67], which holds also for minors [94]. Thus, the class of
planar graphs is characterized by a set of two forbidden minors. The graph
minors project of Robertson and Seymour is a series of 23 papers spanning more
than two decades, dedicated to proving the generalization of Kuratowski’s
theorem called Wagner’s conjecture [94]: The class of all graphs is well-quasi
ordered by the minor relation, or, equivalently, any minor-closed family of
graphs can be characterized by a finite set of forbidden minors. The graph
minors project had tremendous impact on various areas of theoretical computer
science and on graph theory, particularly due to numerous concepts, structural
results, and algorithms that it yielded. Notably, it is considered to be the
origin of the field of parameterized complexity [29] and the source for a
large number of its most central notions and techniques [73].

Unfortunately, the dependencies on the parameters of most algorithms based on
the graph minors project are huge, being towers of exponents, and so they are
called “galactic algorithms” [68, 57]. As written in [73]: “keeping in mind
that the primary objective of the paradigm of parameterized complexity is to
cope with computational intractability, we are facing a blatant discrepancy.”
Thus, the holy grail of parameterized complexity is to amend this discrepancy,
making the graph minors theory efficient. While substantial efforts have been
made in this direction (e.g., see [47, 60, 61, 14, 18, 21]), it will likely
take a long time for the matter to be well understood. In particular, two
central concrete goals posed for this purpose are to solve Minor Testing and
Disjoint Paths efficiently [73].

All known algorithms for (Topological) Minor Testing and Disjoint Paths use
the following case distinction. First, if the treewidth of the graph is
“small”, then they directly solve the problem using dynamic programming
(classically) or a different mean [17, 71]. Else, if the graph contains a
large clique as a minor, then they use rerouting arguments to find an
irrelevant vertex within it. Lastly, we are left with the case where the
treewidth is large and the graph does not have a large clique as a minor. This
reduces the problem to almost-embeddable graphs [89], where a so-called flat
wall theorem ensures the existence of a large almost planar piece within the
graph, which is afterwards analyzed. Hence understanding the planar case is
paramount to understand the problem in general. Our contributions can be
viewed as a piece of the ongoing efforts of many researchers to establish
which parts of the graph minor theory can be made algorithmically efficient.

##### 1.6. Organization.

First, in Section 2, we outline the proofs of our results. Afterwards, in
Section 3, we present the more basic preliminaries required for our work.
Then, in Sections 4 and 5, we provide the full details of the proofs of our
positive and negative results, respectively. Finally, in Section 6, we
conclude the paper with several open questions. Whenever we want to emphasize
the importance of a statement (e.g., when it is a building block of the main
proof), we use the “proposition” environment, instead of “lemma”.

##  2 Outline

In this section, we give an informal overview of our technical contributions,
beginning from the positive result, which requires fewer intermediate steps.

###  2.1 Polynomial kernel for parameter $k+\mathsf{tw}$

Our kernelization algorithm is based on several steps that reduce the size of
certain subgraphs of $G$ while treating their boundary vertices as temporary
terminals. Since we have no control over which pairs of these terminals might
be connected by paths in a solution, it is convenient to work in a slightly
more general setting. We say that two graphs $G_{1},G_{2}$ sharing a set of
vertices $X$ are $X$-linkage-equivalent if for every set of pairs
$\mathcal{T}\subseteq X^{2}$, the instances $(G_{1},\mathcal{T})$ and
$(G_{2},\mathcal{T})$ of Disjoint Paths are equivalent. In fact, we prove a
theorem that is more general than Theorem 1.4 as we do not need to know in
advance which pairs of terminals should be connected.

######  Theorem 2.1.

Let $G$ be a planar graph of treewidth $\mathsf{tw}$ and $X\subseteq V(G)$ be
of size $k$. Then we can construct, in polynomial time, a planar graph
$G^{\prime}$ with $X\subseteq V(G^{\prime})$ such that
$|V(G^{\prime})|=\mathcal{O}(k^{12}\mathsf{tw}^{12})$ and $G^{\prime}$ is
$X$-linkage-equivalent to $G$.

##### Single-face case.

The problem becomes simpler when we are equipped with an embedding of $G$ with
all the terminals from $X$ lying on a single face (we can assume that this is
the outer face by flipping the embedding). In fact, in this case Disjoint
Paths is solvable in polynomial time [87], similarly as Steiner Tree [33]. To
design a useful subroutine, we need to reduce the size of $G$ to be polynomial
in $|X|$ while maintaining $X$-linkage-equivalency. To this end, we take
advantage of the criterion by Robertson and Seymour [87], stating that when
$X$ lies on the outer face of $G$ and $\mathcal{T}\subseteq X^{2}$, then the
instance $(G,\mathcal{T})$ is solvable if and only if (1) $\mathcal{T}$ is
cross-free888 When $X$ lies on the outer face, then $\mathcal{T}\subseteq
X^{2}$ is called cross-free if there are no pairs $(a,b),(c,d)\in\mathcal{T}$
such that $a,c,b,d$ lie in this order on the outer face.  with respect to the
cyclic ordering of $X$ and (2) for every partition of $X$ into continuous
segments $(X_{1},X_{2})$ the number of requested paths with one endpoint in
$X_{1}$ and the other one in $X_{2}$ is not greater than the minimum vertex
$(X_{1},X_{2})$-cut (see Figure 1). So, to compress $G$ we need a mimicking
network that preserves such minimum cuts. There are known constructions of
mimicking networks for planar [44, 66] and general [65] graphs, but they are
designed to preserve edge-cuts. We give a self-contained construction of a
mimicking network of size $\mathcal{O}(|X|^{6})$ preserving the necessary
vertex-cuts.

Figure 1: A visualization of cutting a graph open alongside a tree $T$ in the
radial graph. Left: The tree $T$ is sketched with dotted lines; we have
$V(T)\cap V(G)=\\{1,2,3,4\\}$. The vertices $1,3,4$ (black squares) belong to
$X$. A $(1,3)$-path $P$ is drawn with solid orange lines. Middle: After
opening the graph, the vertex 2 is split into three copies $2a,2b,2c$, while
the path $P$ is split into a $(1,2c)$-path and a $(2a,3)$-path. The white and
black squares are the new terminals. Right: After flipping the embedding, we
can assume that the face where the cut happened is the outer face. The dotted
lines illustrate all the cuts that must be preserved in a mimicking network.
As an example, the brown heavier line stands for the minimum cut between
$\\{4,2c\\}$ and $\\{1,2a,3,2b\\}$.

To reduce the general case to the single-face case, we follow the idea from
the kernelization algorithm for Planar Steiner Tree parameterized by the
solution size [84] (cf. [12]). To adapt it to our setting, we consider the
radial graph of the plane graph $G$, obtained by inserting a vertex inside
each face, connecting it to all vertices from $G$ lying on this face, and
removing original edges from $E(G)$. Let $T$ be a tree in the radial graph
that spans all the terminals from $X$. Imagine “cutting the graph open”
alongside $T$ by widening the fissure marked by $T$ on the plane and
duplicating the vertices of $G$ lying on this fissure (see Figure 1). This
operation creates a new face, incident to all the copies of terminals. We
could compress the obtained graph using the approach outlined above and
afterwards stitch it back alongside $T$. However, now we need to treat all the
vertices lying on $T$ (not only the ones from $X$) as terminals in order to
keep track of paths that might traverse $T$. This means that, prior to opening
the graph, we need to ensure that the tree $T$ is not too large, that is, the
vertices from $X$ are close to each other in the radial graph. In other words,
we need to reduce the radial diameter of the graph, i.e., the maximum number
of faces one must cross to reach a certain vertex from another one. Such an
approach has been applied in the reductions to a single-face case for Vertex
Multiway Cut [53] and Vertex Planarization [55].

##### Radial diameter reduction.

The radial diameter of a plane graph $G$ is proportional to the maximal number
of concentric cycles in $G$ (i.e., these cycles are vertex-disjoint and each
one is located in the interior of the next one, resembling a well). In
particular, when the radial diameter is as large as
$\Omega(k\cdot\mathsf{tw}^{2})$, then one can find a sequence
$C_{1},C_{2},\dots,C_{m}$ of concentric cycles such that
$m=\Omega(\mathsf{tw}^{2})$ and each terminal from $X$ is located in either
the interior of $C_{1}$ or the exterior of $C_{m}$. We show that in this case,
$G$ must contain an irrelevant edge, that is, an edge $e$ for which the graph
$G\setminus e$ is $X$-linkage-equivalent to $G$. Our strategy is to
iteratively remove irrelevant edges from $G$ until its radial diameter becomes
bounded by $O(k\cdot\mathsf{tw}^{2})$. Afterwards, we will be able to find a
Steiner tree $T$ of $X$ of size $O(k^{2}\cdot\mathsf{tw}^{2})$ in the radial
graph. This will allow us to reduce the problem to the single-face case with
$O(k^{2}\cdot\mathsf{tw}^{2})$ terminals.

Consider a sequence of concentric cycles $C_{1},C_{2},\dots,C_{t}$. It is
known [48] that the existence of $t$ vertex-disjoint paths between $V(C_{1})$
and $V(C_{t})$ yields a minor model of a $t\times t$-grid, thus implying that
the treewidth of the graph is at least $t$. Conversely, if we know that
treewidth is less than $t$, Menger’s theorem implies that there is a vertex
$(V(C_{1}),V(C_{t}))$-separator of size less than $t$. We can always find such
a separator located within the well, that is, between $C_{1}$ and $C_{t}$
(inclusively). In our setting, this implies that we can find a
$(V(C_{1}),V(C_{m}))$-separator of size at most $\mathsf{tw}$ located inside
the cycle $C_{\mathsf{tw}+1}$, and similarly, one located outside
$C_{m-\mathsf{tw}-1}$. Therefore, the search of an irrelevant edge can be
reduced to the two-face case: we are given a plane graph $G$ with a set of
terminals $V_{out}$ located on the outer face, another set of terminals
$V_{in}$ located on some internal face, such that
$|V_{in}|,|V_{out}|\leq\mathsf{tw}$, and a sequence of
$\Omega(\mathsf{tw}^{2})$ concentric $C_{1},C_{2},\dots,C_{m}$ cycles around
$V_{in}$ (see Figure 2). Now the task is to find an edge $e\in E(G)$ such that
$G\setminus e$ and $G$ are $(V_{in}\cup V_{out})$-linkage-equivalent.

We begin with computing the minimum $(V_{in},V_{out})$-separator $S_{in}$ that
is closest to $V_{in}$. By “closest to $V_{in}$” we mean that for any other
minimum separator $S$ the set of vertices reachable from $V_{in}$ in $G-S$ is
a superset of those reachable from $V_{in}$ in $G-S_{in}$. It is well-known
[23, Thm. 8.4] that such a separator exists. Similarly, we compute the minimum
$(V_{in},V_{out})$-separator $S_{out}$ closest to $V_{out}$. Every inclusion-
minimal vertex separator $S$ in a plane graph $G$ can be represented by a
noose in the plane that intersects the image of $G$ exactly at the vertices of
$S$. Since $|S_{in}|,|S_{out}|\leq\mathsf{tw}$, the corresponding nooses
cannot cross more than $\mathsf{tw}$ cycles from $C_{1},C_{2},\dots,C_{m}$.
These nooses form a partition of $G$ into three parts, one of which must
contain $\Omega(\mathsf{tw}^{2})$ cycles from $C_{1},C_{2},\dots,C_{m}$.
Depending on which part is “deep”, we apply different strategies for detecting
an irrelevant edge.

Figure 2: Left: An overview of the two-face case. The well comprises a
sequence of concentric cycles $C_{1},\dots,C_{m}$ such that each terminal from
$X$ (the red squares) is either inside $C_{1}$ or outside $C_{m}$. The nooses
representing separators $V_{in},V_{out}$ are drawn blue, while the nooses of
$S_{in},S_{out}$ are red; each of them can intersect at most $\mathsf{tw}$
cycles. The cycles contained entirely in each of the three parts of the graph
are highlighted in green. A family of vertex-disjoint paths with endpoints at
$X$ is sketched with black lines. We can assume that the
$(V_{in},V_{in})$-subpaths and the $(V_{out},V_{out})$-subpaths, which do not
traverse the well from inside to outside, intersect only few cycles. Since the
remaining $(V_{in},V_{out})$-subpaths must cross the separator $S_{in}$, which
is the minimum $(V_{in},V_{out})$-separator closest to $V_{in}$, there is a
space for an augmenting path between $V_{in}$ and $S$ (the orange noose). This
fact, crucial for the analysis of Case I, is illustrated with two dashed
lines. Right: An illustration of the notion of the winding number from Case
II. The blue, green, and orange paths have winding numbers 1, -1, -7,
respectively.

##### Case I: Deep well in the interior/exterior.

First consider the case that there are $\Omega(\mathsf{tw}^{2})$ concentric
cycles between $V_{in}$ and $S_{in}$. (The case with a deep subgraph between
$S_{out}$ and $V_{out}$ is analogous.) Let $\mathcal{P}$ be a family of
vertex-disjoint paths (a linkage) with endpoints in $V_{in}\cup V_{out}$ and
$\mathcal{P}_{long}$ denote the subfamily of paths in $\mathcal{P}$ that
connect $V_{in}$ to $V_{out}$. By a standard argument, the paths from
$\mathcal{P}\setminus\mathcal{P}_{long}$ can be assumed to cross only few
cycles from $C_{1},C_{2},\dots,C_{m}$, namely at most
$\max(|V_{in}|,|V_{out}|)\leq\mathsf{tw}$, so our main focus is on the paths
from $\mathcal{P}_{long}$. Each of these paths must traverse the separator
$S_{in}$, let $p$ denote its size, so $|\mathcal{P}_{long}|\leq p$. But since
$S_{in}$ is the minimum $(V_{in},V_{out})$-separator closest to $V_{in}$, for
any $(V_{in},V_{out})$-separator $S$, located inclusively between $V_{in}$ and
$S_{in}$, there exists at least $p+1$ vertex-disjoint $(V_{in},S)$-paths,
i.e., $\mu(V_{in},S)>p$. This allows us to focus on the following variant of
the two-face case: $S$ replaces the set of terminals $V_{out}$ lying on the
outer face, $\mu(V_{in},S)>p$, there are still $\Omega(\mathsf{tw}^{2})$
concentric cycles between $V_{in}$ and $S$, and we want to detect an edge $e$
that is not relevant for any family $\mathcal{P}$ of at most $p$ vertex-
disjoint $(V_{in},S)$-paths. Here, by “not relevant for $\mathcal{P}$” we mean
that there exists a linkage $\mathcal{P}^{\prime}$ in $G\setminus e$
connecting the same pairs of vertices as $\mathcal{P}$. Let
$V^{\prime}\subseteq V_{in}$ (resp. $S^{\prime}\subseteq S$) denote the
endpoints of $\mathcal{P}$ at $V_{in}$ (resp. at $S$). We prove a criterion
that under the given assumptions, such a linkage exists if and only if (1) the
cyclic ordering of $V^{\prime}$ matches the cyclic ordering of $S^{\prime}$
and (2) the cut-condition $\mu(V^{\prime},S^{\prime})\geq|\mathcal{P}|$ holds.
To prove this, we take advantage of the slack $\mu(V_{in},S)>p$ to show that
any family of at most $p$ disjoint $(V^{\prime},S^{\prime})$-paths can be
“shifted” clockwise using $\Omega(\mathsf{tw})$ concentric cycles. As we need
at most $\mathsf{tw}$ shifts to transform any
$(V^{\prime},S^{\prime})$-linkage into $\mathcal{P}$, having
$\Omega(\mathsf{tw}^{2})$ concentric cycles suffices. With this criterion at
hand, we show that there always exists an edge $e$ whose removal does not
affect the cut-condition for any pair $(V^{\prime},S^{\prime})$, implying that
$e$ is irrelevant.

##### Case II: Deep well in the middle.

Now consider the case that there are $\Omega(\mathsf{tw}^{2})$ concentric
cycles between $S_{in}$ and $S_{out}$. Recall that
$p=|S_{in}|=|S_{out}|=\mu(S_{in},S_{out})$. Let $\mathcal{P}$ be a family of
vertex-disjoint $(S_{in}\cup S_{out})$-paths. If $\mathcal{P}$ contains less
than $p$ paths that connect $S_{in}$ to $S_{out}$, then the analysis is the
same as in the previous case. Therefore, the problem boils down to a very
restricted case: every path in $\mathcal{P}$ connects $S_{in}$ to $S_{out}$
and every vertex in $(S_{in}\cup S_{out})$ is an endpoint of a path from
$\mathcal{P}$. We call such $\mathcal{P}$ a cylindrical linkage. It is now
convenient to fix a concrete plane embedding of the graph: assume that the
vertices from $S_{in}$ lie on the circle $\\{(x,y)\in\mathbb{R}^{2}\mid
x^{2}+y^{2}=1\\}$ and the vertices from $S_{out}$ lie on
$\\{(x,y)\in\mathbb{R}^{2}\mid x^{2}+y^{2}=4\\}$. Furthermore, assume that the
$j$-th element of $S_{in}$, $0\leq j<p$, has polar coordinates
$(1,\frac{-2\pi}{p}j)$ and the $j$-th element of $S_{out}$ has polar
coordinates $(2,\frac{-2\pi}{p}j)$. For an $(S_{in},S_{out})$-path $P$, we
define its winding number $\theta(P)\in\mathbb{Z}$ as $\frac{p}{2\pi}$ times
the total angle traversed by the curve corresponding to $P$, measured
clockwise (see Figure 2). It is easy to see that all paths in a cylindrical
linkage $\mathcal{P}$ share the same winding number, so we can also define a
winding number $\theta(\mathcal{P})$ of $\mathcal{P}$. We say that
$\theta\in\mathbb{Z}$ is feasible if there exists a cylindrical linkage
$\mathcal{P}$ with $\theta(\mathcal{P})=\theta$. Note that if
$\theta(\mathcal{P}_{1})\equiv\theta(\mathcal{P}_{2})\mod p$ then the linkages
$\mathcal{P}_{1},\mathcal{P}_{2}$ connect the same pairs of terminals.
Therefore there are at most $p$ different connection-patterns that we need to
preserve.

The structure of cylindrical linkages has been studied by Robertson and
Seymour [87] who showed that when $\theta_{1}<\theta_{2}<\theta_{3}$ and
$\theta_{1},\theta_{3}$ are feasible, then so is $\theta_{2}$. This means that
it suffices to preserve just the minimal and maximal values
$\theta_{min},\theta_{max}$ that are feasible. They can be efficiently
computed because the problem becomes polynomial-time solvable in this special
case [87]. Moreover, the observation above allows us to assume that the values
$\theta_{min},\theta_{max}$ differ by at most $p-1$. We prove that there exist
cylindrical linkages $\mathcal{P}_{1},\mathcal{P}_{2}$ with
$\theta(\mathcal{P}_{1})=\theta_{min}$,
$\theta(\mathcal{P}_{2})=\theta_{max}$, such that the intersection of any
$P_{1}\in\mathcal{P}_{1}$ and $P_{2}\in\mathcal{P}_{2}$ has at most one
connected component. Combined with the presence of many concentric cycles
between $S_{in}$ and $S_{out}$, this implies that there exists an edge $e$
used by neither $\mathcal{P}_{1}$ nor $\mathcal{P}_{2}$. Consequently,
removing $e$ from the graph preserves the set of feasible values of $\theta$
(modulo $p$) and hence yields an $(S_{in}\cup S_{out})$-linkage-equivalent
instance. This concludes the description of radial diameter reduction.

##### Comparison to the previous approach.

The known $2^{O(k^{2})}\cdot n^{O(1)}$-time algorithms for Planar Disjoint
Paths [17, 71] are based on bounding the number of relevant homotopy classes
of a solution by $2^{O(k^{2})}$. Afterwards, for each fixed homotopy class,
the problem can be solved in polynomial time [91]. An important case in the
analysis of the homotopy classes resembles the two-face case, described above.
To bound the winding numbers of paths, these proofs rely on a highly technical
argument originating from the FPT algorithm for the directed variant of the
problem [24]. By dividing the analysis into two cases, one with non-maximal
linkages and one with highly structured linkages, we avoid these
technicalities and obtain a stronger result (i.e., a kernel) by simpler means.

###  2.2 Kernelization hardness for parameter $k$

To establish the kernelization hardness, we present a polynomial-time
reduction from Set Cover with parameter (the universe size) $k$ to Planar
Disjoint Paths with parameter (the number of terminal pairs)
$k^{\prime}=k^{\mathcal{O}(1)}$. Under this parameterization, Set Cover is
known not to admit a polynomial kernel unless coNP $\subseteq$ NP/poly [27]
and to be WK[1]-complete [50]. Hence, such a reduction entails Theorems 1.1
and 1.2.

Before we present the reduction, we discuss the intuition that guided its
construction (and, in particular, of the so-called vector-containment gadget
described later). Recall that Planar Disjoint Paths is solvable in polynomial
time once we fix the homotopy class of a sought solution [91]. This suggests
that a polynomial reduction from an NP-hard problem should map different NP-
witnesses (each encoding a solution candidate that can be verified in
polynomial time) into different homotopy classes of a solution. Notice that
the solution candidates to Set Cover are tuples of sets (whose number can be
huge), while the number of different homotopy classes is bounded by
$n^{\mathcal{O}(k^{\prime})}$ [91].999The number of different homotopy classes
is also known to be bounded by $2^{\mathcal{O}(k^{2})}$ [71], if we restrict
ourselves to only “relevant” ones. The precise definition of “relevant” in
this context is immaterial for our work. Thus, we must map the solution
candidates to Set Cover into homotopies in an economical fashion. The main
crux of the reduction is an intricate mechanism that allows to encode a set
family of size as large as $2^{\Omega(k)}$ using a homotopy class of just
$k^{\mathcal{O}(1)}$ paths.

##### Non-crossing multicommodity flow.

We present our reduction in the language of non-crossing edge-disjoint walks.
Focusing on edge-disjoint walks allows us to utilize the convenient link
between max-flows and shortest paths in the dual graph. What is more, this
setting generalizes finding both vertex-disjoint or edge-disjoint paths in
planar graphs [7]101010 We remark that there is a flaw in [7, Proposition 12]
because replacing a vertex with merely a cycle is not sufficient. We give a
correct argument using a cylindrical wall instead of a single cycle. , which
will make Theorems 1.1, 1.2, 1.3 simple corollaries from the main reduction.

For a multigraph $G$ with a fixed plane embedding, two pairs of edges
$(e_{1},f_{1})$ and $(e_{2},f_{2})$, with all edges incident to a vertex $v\in
V(G)$, cross if $e_{1},e_{2},f_{1},f_{2}$ appear in this order in the cyclic
ordering of edges around $v$. Next, two edge-disjoint walks $W_{1},W_{2}$ in
$G$ are non-crossing if there are no pairs of consecutive edges
$(e_{1},f_{1})$ in $W_{1}$ and $(e_{2},f_{2})$ in $W_{2}$ that cross (see
Figure 3). In the Non-crossing Multicommodity Flow problem (cf. [7, 71]), we
are given a plane multigraph $G$ and a family $\mathcal{T}$ of $k$ tuples
$(s_{i},t_{i},d_{i})\in V(G)\times V(G)\times\mathbb{N}$, called requests. A
solution is a family $\mathcal{P}$ of pairwise edge-disjoint non-crossing
walks containing $d_{i}$ walks connecting $s_{i}$ to $t_{i}$, for $i\in[k]$,
called a non-crossing $\mathcal{T}$-flow.111111 In this paper, we consider
only integral flows.  We add one more technical requirement for a solution,
which is irrelevant in this informal outline (see Definition 5.2). Since we do
not impose any bounds on the demands $d_{i}$, the total size of the family
$\mathcal{P}$ may be exponential in the parameter $k$. We address this issue
later.

(a)  (b)

Figure 3:  Left: Three non-crossing walks traversing a vertex. In the
reduction from Non-crossing Multicommodity Flow to Planar (Edge-)Disjoint
Paths we replace each vertex with a cylindrical wall. This transformation
makes the graph simple and subcubic, so the three notions of (a) edge-disjoint
non-crossing walks, (b) edge-disjoint paths, and (c) vertex-disjoint paths
become equivalent. Right: A system of gadgets for $k=3$, $\ell=2$, in a
reduction from Set Cover. The existential gadgets are on the top and the
subset gadgets are on the right. The terminal pairs in each gadget are
numbered clockwise. The three squares in the middle are the junction gadgets.
The highlighted stripe shows a way of communication between the first
existential gadget and the first subset gadget. The red flow encodes a
solution $S_{1}=\\{1\\}$, $S_{2}=\\{2,3\\}$.

##### The main gadgets.

We employ three types of gadgets sharing a common interface: each gadget is a
plane multigraph $G$ with a set of requests $\mathcal{T}\subseteq V(G)\times
V(G)\times\mathbb{N}$ and distinguished vertices
$s_{1},t_{1},\dots,s_{m},t_{m}$ lying on the outer face in this clockwise
order. For a subset $F\subseteq[m]$, let
$\mathcal{T}_{F}=\\{(s_{i},t_{i},1)\mid i\in F\\}$. A gadget $(G,\mathcal{T})$
encodes some downward-closed family of sets $\mathcal{F}$ as follows: the
instance $(G,\mathcal{T}\cup\mathcal{T}_{F})$ should be solvable if and only
if $F\in\mathcal{F}$. In other words, routing all $(s_{i},t_{i})$-walks for
$i\in F$ through the gadget should be possible only when $F$ satisfies
property $\mathcal{F}$.

The first type of a gadget is an $\ell$-$\mathsf{Existential\,Gadget}$ with
$\ell$ terminal pairs $(s_{i},t_{i})$. For this gadget, $\mathcal{F}$ is
defined as a family of all proper subsets of $[\ell]$. That is,
$(G,\mathcal{T}\cup\mathcal{T}_{F})$ is solvable if and only if $|F|<\ell$.
Suppose we are given an instance $(k,\mathcal{S},\ell)$ of Set Cover, i.e.,
$\mathcal{S}$ is a family of subsets of $[k]$ and we ask whether there are
$\ell$ sets in $\mathcal{S}$ that cover $[k]$. We will make a single copy of
an $\ell$-$\mathsf{Existential\,Gadget}$ for each $i\in[k]$. For $j\in[\ell]$
the intended meaning of $j\not\in F$ in the $i$-th gadget is that the element
$i$ should be covered by the $j$-th set in a solution. The
$\ell$-$\mathsf{Existential\,Gadget}$ ensures that for at least one
$j\in[\ell]$ this condition will hold.

Next, we introduce an $(r,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$. By
padding the family $\mathcal{S}$ with empty sets, we can assume that
$|\mathcal{S}|=2^{r}$ for some integer $r\leq k$. The
$(r,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$ has $k$ terminal pairs
$(s_{i},t_{i})$ and we require $F\in\mathcal{F}$ if and only if there exists
$S\in\mathcal{S}$ with $F\subseteq S$. In other words, the set of additional
terminals should encode a subset of some set from $\mathcal{S}$.

Imagine the following construction: we make $k$ copies of an
$\ell$-$\mathsf{Existential\,Gadget}$, $\ell$ copies of an
$(r,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$ and, for each $i\in[k]$,
$j\in[\ell]$, we add terminals $u_{i,j}$, $v_{i,j}$, connected to the $j$-th
pair of terminals in the $i$-th existential gadget and the $i$-th pair of
terminals in the $j$-th subset gadget. For each created pair $u_{i,j}$,
$v_{i,j}$, we demand a single unit of flow between $u_{i,j}$ and $v_{i,j}$. By
the property of an $\ell$-$\mathsf{Existential\,Gadget}$, for each $i\in[k]$
there should be at least one $j\in[\ell]$ for which the
$(u_{i,j},v_{i,j})$-walk goes through the $j$-th subset gadget. On the other
hand, for each $j\in[\ell]$ the set of such indices $i$ forms a subset of some
set from $\mathcal{S}$. Therefore satisfying all the requests is possible
exactly when there are $\ell$ sets in $\mathcal{S}$ whose union is $[k]$, as
intended.

The problem with this construction is that already for $\ell=k=3$ such a graph
contains $K_{3,3}$ as a minor, so it cannot be planar. To circumvent this, we
need yet another gadget to allow the links between each $i$-th existential
gadget and each $j$-th subset gadget to cross. To this end, we utilize a
$\mathsf{Junction\,Gadget}$ $(G,\mathcal{T})$ with 4 terminal pairs
$(s_{i},t_{i})$. We demand that $(G,\mathcal{T}\cup\mathcal{T}_{F})$ should be
solvable if and only if $\\{1,3\\}\not\subseteq F$ and $\\{2,4\\}\not\subseteq
F$. That is, when we allow a walk on the left then we cannot route a walk on
the right, and when we allow a walk at the top then we cannot route a walk at
the bottom, and vice versa. These two exclusion mechanisms are independent
from each other, thus allowing two bits of information to “travel” in a
crossing fashion (see Figure 3).

The existential and junction gadgets have been employed in the original NP-
hardness proof of Planar Disjoint Paths [64] and we can easily adapt them for
our purposes. The main challenge though is to construct the
$(r,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$. In order to design a meaningful
reduction we can produce only $(r+k)^{\mathcal{O}(1)}$ requests while we need
to encode as many as $2^{r}$ sets from $\mathcal{S}$.

##### Subset gadget: The first attempt.

We begin with a simplified construction, first presenting the pattern
propagation mechanism alone. This also reflects how the full construction is
presented in Sections 5.3.1 and 5.3.2. Additionally, here we do not delve into
formulas regarding the numbers of parallel edges and the non-crucial demands
$d_{i}$, aiming at the simplest presentation of the main ideas. By a slight
abuse of notation, we treat $\mathcal{S}$ as a function from $\\{0,1\\}^{r}$
to subsets of $[k]$. We will build the gadget from $k$ blocks, each of which
could “choose” a pattern encoded by a vector $\mathbf{b}\in\\{0,1\\}^{r}$.
When $i\in F$ and the $i$-th block chooses a vector $\mathbf{b}^{i}$, this
should imply $i\in\mathcal{S}(\mathbf{b}^{i})$. The pattern propagation will
ensure that each block chooses exactly the same vector $\mathbf{b}$. In turn,
this will imply that $i\in F\Rightarrow i\in\mathcal{S}(\mathbf{b})$, matching
the gadget specification.

Let $r$-ladder be the $(r+1)\times 2$-grid, with internal faces numbered
bottom-up as $f_{1},\dots,f_{r}$. We construct the $i$-th block using two
$r$-ladders, an upper one $L_{i}^{+}$ and a lower one $L_{i}^{-}$, and connect
the consecutive blocks as depicted in Figure 4. We also connect the first and
the last block, thus creating a ring-like structure with the lower ladders in
its interior. In each ladder $L$ we attach two vertices $L[u_{0}]$, $L[u_{1}]$
to, respectively, the bottom and the top of $L$, and add a request
$(L[u_{0}]$, $L[u_{1}],1)$ to $\mathcal{T}$. We will enforce that the
$(L[u_{0}]$, $L[u_{1}])$-walk $W$ must be entirely contained within $L$, and
so it can be associated with a vector $\mathbf{b}^{L}\in\\{0,1\\}^{r}$
encoding which faces $f_{1},\dots,f_{r}$ are to the left of $W$ (then the
corresponding bit in $\mathbf{b}^{L}$ is set to 0) and which are to the right
(then the corresponding bit is 1). We shall call $\mathbf{b}^{L}$ the pattern
in $L$.

Next, for each $i\in[k]$ and $j\in[r]$ we attach a vertex inside the face
$f_{j}$ of the ladder $L_{i}^{+}$ (we refer to this vertex as
$L_{i}^{+}[x_{j}]$) and a vertex inside the face $f_{j}$ of the ladder
$L_{i}^{-}$ (denoted $L_{i}^{-}[x_{j}]$). We create a request
$(L_{i}^{+}[x_{j}],L_{i}^{-}[x_{j}],2^{j-1})$. Because the
$(L_{i}^{+}[x_{j}],L_{i}^{-}[x_{j}])$-walks cannot cross the
$(L_{i}^{+}[u_{0}]$, $L_{i}^{+}[u_{1}])$-walk, they need to use the passage on
the left when the $j$-th bit of the pattern is 0, or the passage on the right
when this bit is 1. This already implies that the patterns in the ladders
$L_{i}^{-}$, $L_{i}^{+}$ must be the same, and we will refer to this common
pattern as $\mathbf{b}^{i}$.

Figure 4:  A simplified construction of a
$(3,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$ and a sketch of a solution (the
colorful lines). The vertices that need to be connected by walks share common
colors and shapes. The $i$-th block is built from two $3$-ladders
$L_{i}^{+},L_{i}^{-}$, and a
$(3,Z^{\mathcal{S}}_{i})$-$\mathsf{Vector\,Containment\,Gadget}$. The blocks
are combined into a ring-like structure (on the right). The area separating
the upper and lower ladder is referred to as the middle belt. Due to pattern
propagation, the choice of which colors are being routed through the left or
right passage must the same in all blocks. The common pattern
$\mathbf{b}=(010)$ chosen by the solution is sketched with solid lines.
Accommodating an $(s_{i},t_{i})$-walk (purple) through the $i$-th vector-
containment gadget is possible if and only if $\mathbf{b}\in
Z^{\mathcal{S}}_{i}$.

We set the capacity of each passage going through the middle belt to be
$2^{r}-1$, i.e., we place this many parallel edges in each of $k$ passages.
Note that the $x$-requests from the $i$-th block send
$\sum_{j=1}^{r}2^{j-1}\cdot 1_{[\mathbf{b}^{i}_{j}=0]}$ units of flow through
the passage to the left of the $i$-th block and $\sum_{j=1}^{r}2^{j-1}\cdot
1_{[\mathbf{b}^{i}_{j}=1]}$ units of flow through the right passage. If all
the patterns are the same, then the total amount of flow going through each
passage is $\sum_{j=1}^{r}2^{j-1}=2^{r}-1$. Because we work on a ring
structure, when some patterns differ then there is a passage through which one
would need to push at least $2^{r}$ units of flow. Consequently, all the
vectors $\mathbf{b}^{i}$ must coincide and so pattern propagation works as
intended.

So far we have established a mechanism that makes a solution choose a single
vector $\mathbf{b}\in\\{0,1\\}^{r}$ that appears as a pattern in each block of
the $(r,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$. The next step is to enforce
that $i\in F\Rightarrow i\in\mathcal{S}(\mathbf{b})$. It is convenient to
define $Z^{\mathcal{S}}_{i}$ as the set of vectors $\mathbf{b}$ for which
$i\in\mathcal{S}(\mathbf{b})$. Then the set $Z^{\mathcal{S}}_{i}$ can be
encoded in the graph, and we need to check whether the pattern $\mathbf{b}$
chosen by a solution belongs to $Z^{\mathcal{S}}_{i}$. To this end, we will
need another kind of a gadget, with a slightly different interface. For
$Z\subseteq\\{0,1\\}^{r}$, an $(r,Z)$-$\mathsf{Vector\,Containment\,Gadget}$
is a plane multigraph $G$ with distinguished vertices $z_{1},\dots,z_{r}$ and
$w_{0},w_{1}$, with the last two lying on the outer face. For
$\mathbf{b}\in\\{0,1\\}^{r}$ we define $\mathcal{T}_{\mathbf{b},d}$ as the
family of following requests:

  1. 1.

$(w_{0},z_{j},1)$ for each $j\in[r]$ with $\mathbf{b}_{j}=0$,

  2. 2.

$(w_{1},z_{j},1)$ for each $j\in[r]$ with $\mathbf{b}_{j}=1$,

  3. 3.

the request $(w_{0},w_{1},d)$.

(The vertex $z_{j}$ needs to be connected by a walk to either $w_{0}$ or
$w_{1}$ depending on the $j$-th bit in $\mathbf{b}$.) We require that the
instance $(G,\mathcal{T}_{\mathbf{b},0})$ is satisfiable for any
$\mathbf{b}\in\\{0,1\\}^{r}$ but the instance $(G,\mathcal{T}_{\mathbf{b},1})$
is satisfiable if and only if $\mathbf{b}\in Z$. In other words, the choice of
the vector $\mathbf{b}$ governs whether we can insert a $(w_{0},w_{1})$-walk
on top of the $r$ walks with endpoints at $z_{1},\dots,z_{r}$.

Assuming that such a gadget exists, we could finish the construction of the
subset gadget as follows. For each $i\in[k]$ we insert an
$(r,Z^{\mathcal{S}}_{i})$-$\mathsf{Vector\,Containment\,Gadget}$ below the
$i$-th block and connect it to the lower corners of the ladder $L_{i}^{-}$. We
refer to its distinguished vertices with $i$ in the superscript, e.g.,
$w^{i}_{0},z^{i}_{j}$. Next, for each $i\in[k]$, $j\in[r]$, we create another
vertex inside the face $f_{j}$ of the ladder $L_{i}^{-}$ (denoted
$L_{i}^{-}[y_{j}]$) and add a request $(L_{i}^{-}[y_{j}],z^{i}_{j},1)$. By the
same argument as above, these walks must go through $w^{i}_{0}$ when
$\mathbf{b}_{j}=0$ or through $w^{i}_{1}$ when $\mathbf{b}_{j}=1$. Therefore,
they contain subwalks satisfying the requests from
$\mathcal{T}_{\mathbf{b},0}$. Next, we create vertices $s_{i},t_{i}$ attached
to the upper corners of the ladder $L_{i}^{+}$; note that they end up in the
exterior of the ring structure, i.e., on the outer face of the subset gadget.
The only possible way from $s_{i}$ to $t_{i}$ leads through the $i$-th vector-
containment gadget. Hence when $i\in F$ and we need to satisfy the request
$(s_{i},t_{i},1)$, there must exist a non-crossing
$\mathcal{T}_{\mathbf{b},1}$-flow in the
$(r,Z^{\mathcal{S}}_{i})$-$\mathsf{Vector\,Containment\,Gadget}$. By its
definition, this implies $\mathbf{b}\in Z^{\mathcal{S}}_{i}$ and so
$i\in\mathcal{S}(\mathbf{b})$, as intended. The last issue is that the
passages through the middle belt are already saturated by the $x$-requests.
This is not a big problem though as we can multiply the demands in the
$x$-requests by a constant and similarly multiply the number of the parallel
edges in the passages, creating a little slack sufficient for routing the
$(s_{i},t_{i})$-walks.

##### Vector-containment gadget.

Unfortunately, the construction above does not work because we do not know how
to construct an $(r,Z)$-$\mathsf{Vector\,Containment\,Gadget}$. Instead, we
now present a gadget with a slightly more complicated specification. First, we
explain how to construct a gadget that behaves almost like an
$(r,Z)$-$\mathsf{Vector\,Containment\,Gadget}$ and then augment the
construction of the subset gadget with additional elements necessary to plug
in the proper vector-containment gadget.

It is convenient to analyze the gadget from the dual perspective. For each
$\mathbf{b}\in\\{0,1\\}^{r}$ we can draw a curve (the red dashed curve in
Figure 4) that has to intersect all the walks in a
$\mathcal{T}_{\mathbf{b},d}$-flow. When there is a path $P$ in the dual graph
whose homotopy aligns with this curve (that is, $P$ traverses $z_{j}$ from the
side of $w_{0}$ when $\mathbf{b}_{j}=0$ and from the side of $w_{1}$ when
$\mathbf{b}_{j}=1$) then the length of $P$ imposes an upper bound on the
maximal number of walks in a $\mathcal{T}_{\mathbf{b},d}$-flow, what in turn
entails an upper bound on $d$. Given the set $Z$, we would like to construct a
plane graph, being a prototype of a dual graph of the gadget, with two
vertices $s,t$ on the outer face and $r$ distinguished internal faces
$f_{1},\dots,f_{r}$ with the following property: the length of a shortest
$(s,t)$-path with homotopy class encoding the vector $\mathbf{b}$ (with
respect to the faces $f_{1},\dots,f_{r}$) depends on whether $\mathbf{b}\in
Z$.

Figure 5: The graph $H_{4}$ with $2^{4}$ vertices in each vertical path. Four
distinguished faces $f_{1},f_{2},f_{3},f_{4}$ are highlighted in light blue.
For $\mathbf{b}=(1001)$ the path $P_{\mathbf{b}}$ is drawn in orange and for
$\mathbf{v}=(1110)$ the path $P_{\mathbf{v}}$ is drawn in green. These vectors
encode whether a path passes above or below each of the faces
$f_{1},f_{2},f_{3},f_{4}$. The red dashed curves illustrate the directions of
walks in a $\mathcal{T}_{\mathbf{b},d}$-flow in the dual of $H_{4}$: note that
each of them intersects $P_{\mathbf{b}}$.

We construct a plane graph $H_{r}$ (see Figure 5) having a unique shortest
$(s,t)$-path $P_{\mathbf{b}}$ for each homotopy class given by
$\mathbf{b}\in\\{0,1\\}^{r}$. Moreover, the paths $P_{\mathbf{b}}$ are
pairwise edge-disjoint. The graph $H_{r}$ has size $2^{\mathcal{O}(r)}$, which
is polynomial in the size of family $\mathcal{S}$, and its treewidth is
$2^{\Omega(r)}$ due to large grid subgraphs; this is inevitable in the light
of Theorem 1.4. The faces $f_{1},\dots,f_{r}$ are the dual counterparts of the
vertices $z_{1},\dots,z_{r}$, while the areas above and below $H_{r}$ are the
placeholders for $w_{0},w_{1}$. In order to achieve our goal, we would like to
modify $H_{r}$ to increase the length of the path $P_{\mathbf{b}}$ exactly
when $\mathbf{b}\in Z$, thus allowing more slack for flows in the dual of
$H_{r}$. This can be obtained by subdividing the first edge (incident to $s$)
on the path $P_{\mathbf{b}}$ when $\mathbf{b}\in Z$; due to edge-disjointness
of the paths $P_{\mathbf{b}}$, this does not affect the remaining homotopy
classes. This modification raises the upper bound on the size of a
$\mathcal{T}_{\mathbf{b},d}$-flow by one; by applying some other adjustments
to $H_{r}$ we can make this upper bound tight for non-crossing flows. As a
consequence, we can accommodate one more $(w_{0},w_{1})$-walk in the dual
exactly when the pattern $\mathbf{b}$ belongs to $Z$, as intended.

The main technical hurdle comes from the fact that the length of the path
$P_{\mathbf{b}}$ in $H_{r}$ depends on $\mathbf{b}$: it is very short for
$\mathbf{b}$ being a 0-vector and very long for $\mathbf{b}$ comprising
alternating 0’s and 1’s. So the bound on the size of a
$\mathcal{T}_{\mathbf{b},d}$-walk depends not only on whether $\mathbf{b}\in
Z$ but also on some function $\gamma(\mathbf{b})$, making it useless for the
current construction of the subset gadget. To circumvent this, we first prove
that the function $\gamma$ enjoys a very special form, which will play a
crucial role later.

$\gamma(b_{1}b_{2}\dots b_{r})=\sum_{1\leq p<q\leq r}1_{[b_{p}\neq
b_{q}]}\cdot 2^{r-q+p-1}$

We will now work with a generalization of an
$(r,Z)$-$\mathsf{Vector\,Containment\,Gadget}$, namely an
$(r,\gamma,Z)$-$\mathsf{Vector\,Containment\,Gadget}$. The difference is that
a non-crossing $\mathcal{T}_{\mathbf{b},d}$-flow should be feasible exactly
when $d\leq\gamma(\mathbf{b})+1_{[\mathbf{b}\in Z]}$. In fact, the proper
definition (5.5) requires more subtleties concerning factors depending on $r$
but we omit them here.

Figure 6:  A refined construction of a
$(3,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$, showing new blocks inserted
between the $i$-th block and the $(i+1)$-th block from the previous
construction. The faces with the endpoints of the new requests are
highlighted. The “pipes” are drawn with dotted lines. The blue paths show
other new requests whose purpose is to block the connections between the upper
and lower pipes. The common pattern of the solution is depicted with solid
lines while the red lines illustrate the workaround for the new requests
traversing the $i$-th vector-containment gadget. Observe that one pair of
highlighted faces is not being separated by the pattern so the corresponding
request can be satisfied locally.

##### Subset gadget: The real deal.

The current task is to adapt the construction of an
$(r,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$ to be compatible with the more
complicated $(r,\gamma,Z)$-$\mathsf{Vector\,Containment\,Gadget}$. The
condition $\mathbf{b}\in Z$ becomes meaningful for the vector-containment
gadget only when it needs to additionally accommodate $\gamma(\mathbf{b})$
units of $(w_{0},w_{1})$-flow. We will extend the previous construction with
“dynamic flow generators”: new requests that could be satisfied either
locally, within their ladder, or via walks passing through the vector-
containment gadget. We insert ${r\choose 2}$ new blocks (without vector-
containment gadgets) between each pair of blocks in the ring structure. In
each new block, labeled now with a triple $(i,p,q)$, $i\in[k]$, $1\leq p<q\leq
r$, we request $2^{r-q+p-1}$ walks from a vertex within the face $f_{p}$ of
the corresponding lower ladder $L$ to a vertex within the face $f_{q}$ of the
same ladder (see Figure 6). Due to pattern propagation, these faces will end
up on the same side of the $(L[u_{0}],L[u_{1}])$-walk only when a solution
chooses a pattern $\mathbf{b}$ with $\mathbf{b}_{p}=\mathbf{b}_{q}$. In this
case the new requests can be satisfied by walks contained in $L$. However,
when $\mathbf{b}_{p}\neq\mathbf{b}_{q}$ the faces $f_{p},f_{q}$ in the ladder
$L$ become separated and the corresponding $2^{r-q+p-1}$ walks must be routed
elsewhere. Observe that the total amount of flow that cannot be satisfied
locally, summing over all pairs $1\leq p<q\leq r$, matches the formula for
$\gamma(\mathbf{b})$.

We need a way to satisfy the requests, that cannot be satisfied locally, with
walks that traverse the $i$-th vector-containment gadget. To this end, we
design an “irrigation system” of workarounds that are too narrow (in the
number of parallel edges) to be used by the other requests. It comprises two
groups of “pipes”, one inside the ring structure, gathering the walks starting
on the left-sides of the ladders and leading towards $w^{i}_{0}$, and the
other one outside the ring structure, gathering the walks starting on the
right-sides of the ladders and leading towards $w^{i}_{1}$. By designing these
systems carefully, we can ensure that (a) the walks going through the pipes
can traverse the vector-containment gadget without crossing each other or the
remaining walks, (b) the only way from the upper pipe system to the lower pipe
system leads through the vector-containment gadget, and (c) the terminals
$s_{i},t_{i}$ stay on the outer face of the subset gadget, as required by its
specification. This concludes the description of the
$(r,k,\mathcal{S})$-$\mathsf{Subset\,Gadget}$ $(G,\mathcal{T})$ with the total
number of requests $|\mathcal{T}|=\mathcal{O}(k\cdot r^{3})$.

##### Implementing weights.

The last issue is to deal with the fact in the Non-crossing Multicommodity
Flow problem we allow requests of the form $(s_{i},t_{i},d_{i})$ where the
demand $d_{i}$ may be exponentially large in the parameter. As our final goal
is to reduce the problem to Planar Disjoint Paths, we would like to set all
the demands to $d_{i}=1$ without increasing the number of requests too much.
To this end, we take advantage of the construction by Adler and Krause [3] who
presented an instance of Planar Disjoint Paths with parameter $\ell$ and a
roughly $2^{\ell}\times 2^{\ell}$-grid subgraph in which every vertex must be
used in the unique solution (hence no vertex is irrelevant despite large
treewidth). What is important for us, the unique solution must traverse the
grid $2^{\ell}-1$ times from left to right (see Figure 29 on page 29). We
utilize this property to implement a request of the form
$(s_{i},t_{i},2^{\ell}-1)$ using only $\ell$ unitary requests. We replace the
endpoint $s_{i}$ with a gadget mimicking the left-side of the grid and $t_{i}$
with a gadget for the right-side of the grid. By the arguments from [3] we
obtain that a solution must contain $2^{\ell}-1$ subwalks between these two
gadgets, which can be translated back into $2^{\ell}-1$ walks between $s_{i}$
and $t_{i}$. Finally, we can partition each request $(s_{i},t_{i},d_{i})$ into
$\mathcal{O}(\log d_{i})$ requests of the form as above, thus increasing the
total size of $\mathcal{T}$ by a factor of $\mathcal{O}(k^{2})$ when the
demands are bounded by $2^{\mathcal{O}(k)}$. This concludes the outline of the
reduction.

##  3 Preliminaries

The set $\\{1,\ldots,p\\}$ is denoted by $[p]$. A graph $G$ has vertex set
$V(G)$ and edge set $E(G)$ of distinct pairs of vertices. We also consider
multigraphs that may have parallel edges but no loops, i.e., $E(G)$ becomes a
multiset of pairs of distinct vertices. For a vertex $v\in V(G)$ we denote by
$E_{G}(v)$ the set of edges incident to $v$. For $A,B\subseteq V(G)$ we define
$E_{G}(A,B)=\\{uv\mid u\in A,v\in B,uv\in E(G)\\}$. The open neighborhood of
$v\in V(G)$ is $N_{G}(v):=\\{u\mid uv\in E(G)\\}$. For a vertex set
$S\subseteq V(G)$ the open neighborhood of $S$, denoted $N_{G}(S)$, is defined
as $\bigcup_{v\in S}N_{G}(v)\setminus S$. For $S\subseteq V(G)$, the graph
induced by $S$ is denoted by $G[S]$. We use shorthand $G-S$ for the graph
$G[V(G)\setminus S]$. For $v\in V(G)$, we write $G-v$ instead of $G-\\{v\\}$.
For $A\subseteq E(G)$ we denote by $G\setminus A$ the graph with vertex set
$V(G)$ and edge set $E(G)\setminus A$. For $e\in E(G)$ we write $G\setminus e$
instead of $G\setminus\\{e\\}$.

##### Paths, linkages, and separators.

For $X,Y\subseteq V(G)$ an $(X,Y)$-walk in $G$ is an alternating sequence of
vertices and edges from $G$ so that the first element is a vertex from $X$,
the last one element is a vertex from $Y$, and each edge is incident to the
proceeding and succeeding vertex. An $(X,Y)$-path is an $(X,Y)$-walk without
vertex repetitions; we often identity a path with a subgraph of $G$. When
$X=\\{x\\}$, $Y=\\{y\\}$, we simply refer to $(x,y)$-walks and $(x,y)$-paths.
The length of a path equals the number of its edges. For $x,y\in V(G)$ we
define $\mathsf{dist}_{G}(x,y)$ as the length of the shortest $(x,y)$-path.

A linkage in $G$ is a family of vertex-disjoint paths in $G$. For
$X,Y\subseteq V(G)$ we say that $\mathcal{P}$ is an $(X,Y)$-linkage when
$\mathcal{P}$ comprises $(X,Y)$-paths. We use shorthand $X$-linkage for an
$(X,X)$-linkage. For $\mathcal{T}\subseteq V(G)\times V(G)$ we say that
$\mathcal{P}$ is a $\mathcal{T}$-linkage when $|\mathcal{P}|=|\mathcal{T}|$
and $\mathcal{P}$ contains an $(s_{i},t_{i})$-path for each
$(s_{i},t_{i})\in\mathcal{T}$. We say that $\mathcal{T}$ is realizable in $G$
if there exists a $\mathcal{T}$-linkage in $G$. Two linkages
$\mathcal{P}_{1},\mathcal{P}_{2}$ are aligned if there is a bijection
$f\colon\mathcal{P}_{1}\to\mathcal{P}_{2}$ such that $P\in\mathcal{P}_{1}$ has
the same endpoints as $f(P)$. For $\mathcal{T}\subseteq V(G)\times V(G)$ we
denote by $V_{\mathcal{T}}$ the set of all vertices occurring in
$\mathcal{T}$.

For two sets $X,Y\subseteq V(G)$, a set $S\subseteq V(G)$ is an
$(X,Y)$-separator if no connected component of $G-S$ contains a vertex from
both $X\setminus S$ and $Y\setminus S$. Note that such a separator may
intersect $X\cup Y$. By Menger’s theorem, the minimum cardinality of such a
separator is equal to the maximum cardinality of an $(X,Y)$-linkage. We denote
this quantity by $\mu_{G}(X,Y)$. An $(X,Y)$-separator $S$ is inclusion-minimal
if no proper subset of $S$ is an $(X,Y)$-separator.

######  Theorem 3.1 ([23, Thm. 8.4, 8.5]).

Let $G$ be a graph and $X,Y\subseteq V(G)$ be disjoint sets of vertices. There
exists a minimum-size $(X,Y)$-separator $S$ such that for any other minimum-
size $(X,Y)$-separator $S^{\prime}$ the set of vertices reachable from $X$ in
$G-S$ is a subset of the set of vertices reachable from $X$ in $G-S^{\prime}$.
Furthermore, $S$ can be constructed in polynomial time.

We say that $S$ is the minimum-size $(X,Y)$-separator closest to $X$. Next, we
shall need the following fact, which follows from the analysis of the residual
graph in the Ford-Fulkerson algorithm.

######  Lemma 3.2 (Augmenting path, [39, 22] (Implicit)).

Let $X,Y\subseteq V(G)$ and $X^{\prime}\subset X,\,Y^{\prime}\subset Y$ be
such that
$|X^{\prime}|=|Y^{\prime}|=\mu_{G}(X^{\prime},Y^{\prime})<\mu_{G}(X,Y)$. Then
there exist $x\in X\setminus X^{\prime}$, $y\in Y\setminus Y^{\prime}$, and an
$(X^{\prime}\cup\\{x\\},Y^{\prime}\cup\\{y\\})$-linkage of size
$|\mu_{G}(X^{\prime},Y^{\prime})|+1$.

##### Contractions and minors.

The operation of contracting an edge $uv\in E(G)$ introduces a new vertex
adjacent to all of $N_{G}(\\{u,v\\})$, after which $u$ and $v$ are deleted.
When working with multigraphs, we accumulate multiplicities of edges with a
common endpoint. The result of contracting $uv\in E(G)$ is denoted $G/uv$. For
$A\subseteq V(G)$ such that $G[A]$ is connected, we say we contract $A$ if we
simultaneously contract all edges in $G[A]$ and introduce a single new vertex.

We say that $H$ is a minor of $G$, if we can turn $G$ into $H$ by a (possibly
empty) series of edge contractions, edge deletions, and vertex deletions. The
result of such a process is given by a minor-model, i.e., a mapping $\Pi\colon
V(H)\to 2^{V(G)}$, such that the branch sets $(\Pi(h))_{h\in V(H)}$ are
pairwise disjoint, induce connected subgraphs of $G$, and $h_{1}h_{2}\in E(H)$
implies that $E_{G}(\Pi(h_{1}),\Pi(h_{2}))\neq\emptyset$.

##### Treewidth.

A tree decomposition of graph $G$ is a pair $(T,\chi)$ where $T$ is a rooted
tree, and $\chi\colon V(T)\to 2^{V(G)}$ is a function, such that:

  1. 1.

For each $v\in V(G)$ the nodes $\\{t\mid v\in\chi(t)\\}$ form a non-empty
connected subtree of $T$.

  2. 2.

For each edge $uv\in E(G)$ there is a node $t\in V(G)$ with
$\\{u,v\\}\subseteq\chi(t)$.

The _width_ of a tree decomposition is defined as $\max_{t\in
V(T)}|\chi(t)|-1$. The _treewidth_ of a graph $G$, denoted
$\mathrm{\textbf{tw}}(G)$, is the minimum width of a tree decomposition of
$G$.

##### Planar graphs and multigraphs.

We provide only the necessary background here and refer to the textbook [79]
for more details. A plane embedding of a multigraph $G$ is given by a mapping
from $V(G)$ to $\mathbb{R}^{2}$ and a mapping that associates with each edge
$uv\in E(G)$ a simple curve on the plane connecting the images of $u$ and $v$,
such that the curves given by two distinct edges can intersect only in a
common endpoint. A multigraph is called planar if it admits a plane embedding.
A plane (multi)graph is a (multi)graph with a fixed planar embedding, in which
we identify the set of vertices with the set of their images on the plane. For
a vertex $v$ in a plane multigraph $G$ we denote by $\pi_{G}(v)$ the clockwise
ordering of the set $E_{G}(v)$. The family of such orderings is called a
rotation system. For a topological disc $D\subseteq\mathbb{R}^{2}$ such that
$G[V(G)\cap D]$ is connected, the outcome of contracting $V(G)\cap D$ is the
unique (with respect to the rotation system) plane multigraph obtained by
contracting $G\cap D$ into a point.

A face in a plane embedding of a multigraph $G$ is a maximal connected subset
of the plane minus the image of $G$. We say that a vertex or an edge lies on a
face $f$ if its images belongs to the closure of $f$. In every plane embedding
there is exactly one face of infinite area, referred to as the outer face. For
a plane multigraph $G$ we define its dual multigraph $G^{*}$ with $V(G^{*})$
being the set of faces of $G$ and edges given by pairs of distinct faces that
are incident to an image of a common edge from $E(G)$. Each (a) vertex $v$,
(b) edge $e$, and (c) face $f$ of $G$ has a counterpart in $G^{*}$,
respectively: (a) face $v^{*}$, (b) edge $e^{*}$, and (c) vertex $f^{*}$.

For a plane graph $G$ with a set of faces $F$, we define its radial graph
$\widehat{G}$ as a bipartite graph with the set of vertices
$V(\widehat{G})=V(G)\cup F$ and edges given by pairs $(v,f)$ where $v\in
V(G)$, $f\in F$, and $v$ lies on the face $f$. For two vertices $u,v\in V(G)$
we define their radial distance $\mathsf{rdist}_{G}(u,v)$ to be one less than
the minimum length of a sequence of vertices that starts at $u$, ends in $v$,
and in which every two consecutive vertices lie on a common face. For two sets
$X,Y\subseteq V(G)$ we define $\mathsf{rdist}_{G}(X,Y)=\min_{x\in X,y\in
Y}\mathsf{rdist}_{G}(x,y)$. The radial diameter of a plane graph $G$ equals
$\max_{u,v\in V(G)}\mathsf{rdist}_{G}(u,v)$.

######  Lemma 3.3 ([52, Prop. 2.1]).

Let $G$ be a plane graph with non-empty disjoint vertex sets $X$ and $Y$, such
that $G[X]$ and $G[Y]$ are connected and $\mathsf{rdist}_{G}(X,Y)=d\geq 2$.
For any $r$ with $0<r<d$ there is a cycle $C$ in $G-(X\cup Y)$ such that all
vertices $u\in V(C)$ satisfy $\mathsf{rdist}_{G}(X,u)=r$, and such that $V(C)$
is an $(X,Y)$-separator in $G$.

A noose is a subset of $\mathbb{R}^{2}$ homeomorphic to the circle
$\mathbb{S}^{1}$. For a plane graph $G$, a $G$-noose is a noose that
intersects $G$ only at vertices; the length of a $G$-noose is defined as the
number of vertices it intersects. For a noose $I$ we define $\mathsf{Disc}(I)$
as the closure of the bounded region of $\mathbb{R}^{2}\setminus I$. For a
closed set $D\subseteq\mathbb{R}^{2}$ we define its interior $\mathsf{int}(D)$
as $D$ minus its boundary $\partial D$. For two nooses $I_{in},I_{out}$, such
that $I_{in}$ lies in the interior of $\mathsf{Disc}(I_{out})$, we define
$\mathsf{Ring}(I_{in},I_{out})=\mathsf{Disc}(I_{out})\setminus\mathsf{int}(\mathsf{Disc}(I_{in}))$.
A plane graph $G$ is properly embedded in a set $D\subseteq\mathbb{R}^{2}$ if
$G\subseteq D$ and $G\cap\partial D\subseteq V(G)$.

######  Lemma 3.4 ([79, Prop. 8.2.3]).

Let $G$ be a plane graph, $X,Y\subseteq V(G)$ be non-empty, disjoint, and
inducing connected subgraphs of $G$, and $S\subseteq V(G)\setminus(X\cup Y)$
be an inclusion-minimal $(X,Y)$-separator. Then there exists a $G$-noose
$\gamma$ such that $S=\gamma\cap V(G)$ and $\gamma$ separates the plane into
two regions, one containing $X$ and the second containing $Y$.

We remark that the original statement in [79] involves singleton sets $X,Y$
and triangulated plane graphs, but it can be adapted to our setting by
contractions and inserting new vertices inside faces.

######  Lemma 3.5.

Let $G$ be a plane graph, $C_{1},C_{2}$ be vertex-disjoint cycles in $G$ such
that $C_{1}$ lies in the interior of $C_{2}$. Let $S$ be an inclusion-minimal
$(C_{1},C_{2})$-separator, not necessarily disjoint from $C_{1},C_{2}$. Then
there exists a $G$-noose $\gamma$ such that $S=\gamma\cap V(G)$ and
$\mathsf{Disc}(C_{1})\subseteq\mathsf{Disc}(\gamma)\subseteq\mathsf{Disc}(C_{2})$.

###### Proof.

By the minimality of the separator, $S$ does not contain vertices in the
interior of $\mathsf{Disc}(C_{1})$ and in the exterior of
$\mathsf{Disc}(C_{2})$. Consider a graph $G^{\prime}$ obtained from $G$ by
removing all the vertices in the interior of $\mathsf{Disc}(C_{1})$, inserting
a vertex $u$ inside $C_{1}$ adjacent to the entire $V(C_{1})$, removing all
the vertices in the exterior of $\mathsf{Disc}(C_{2})$ and inserting a vertex
$v$ outside $C_{2}$ adjacent to the entire $V(C_{2})$. Then $S$ is an
inclusion-minimal $(u,v)$-separator in $G^{\prime}$, disjoint from $u,v$. The
claim follows from Lemma 3.4. ∎

##  4 Polynomial kernel for parameter $k+\mathsf{tw}$

In this section we prove Theorem 2.1, being a generalization of Theorem 1.4.
We begin with providing additional preliminaries about linkages. Next, we
present the radial diameter reduction (Section 4.2), analyzing the two cases
described in the outline, and then combining them into a procedure for the
irrelevant edge detection. Afterwards, we deal with the single-face case
(Section 4.3) and then apply it to process the low-radial-diameter instances
in Section 4.4.

###  4.1 Preliminaries for processing linkages

We gather several useful facts about linkages that will form our toolbox for
proving Theorem 2.1. This is mostly a compilation of know facts, adapted to
our setting. We begin with the concept of linkage-equivalency and explain how
it helps in compressing subgraphs without terminals.

######  Definition 4.1.

Two graphs $G_{1},G_{2}$ sharing a set of vertices $X$ are $X$-linkage-
equivalent if for every set of disjoint pairs $\mathcal{T}\subseteq X^{2}$,
$\mathcal{T}$ is realizable in $G_{1}$ if and only if $\mathcal{T}$ is
realizable in $G_{2}$.

######  Lemma 4.2.

Let $G$ be a graph and $X,Y\subseteq V(G)$, $U\subseteq V(G)\setminus(X\cup
Y)$, $N_{G}(U)\subseteq Y$. Suppose that there is an edge $e\in E(G[U\cup Y])$
such that $G[U\cup Y]\setminus e$ is $Y$-linkage-equivalent to $G[U\cup Y]$.
Then $G\setminus e$ is $X$-linkage-equivalent to $G$.

###### Proof.

Let $\mathcal{P}$ be an $X$-linkage in $G$. For a path $P\in\mathcal{P}$ let
$\Gamma(P)$ be the family of maximal subpaths of $P$ with vertex sets
contained in $U\cup Y$. Since $U\cap X=\emptyset$ and $N_{G}(U)\subseteq Y$
then every path in $\Gamma(P)$ is a $(Y,Y)$-path. Therefore, the linkage
$\mathcal{P}_{U}$ given by the union of $\Gamma(P)$ over $P\in\mathcal{P}$ is
a $Y$-linkage in $G[U\cup Y]$. Because $G[U\cup Y]\setminus e$ is $Y$-linkage-
equivalent to $G[U\cup Y]$, there exists a linkage $\mathcal{P}^{\prime}_{U}$
in $G[U\cup Y]\setminus e$ that is aligned with $\mathcal{P}_{U}$. For
$P\in\mathcal{P}$ let $\widehat{P}$ be obtained from $P$ by replacing each
subpath from $\Gamma(P)$ with its counterpart from $\mathcal{P}^{\prime}_{U}$.
Then $\\{\widehat{P}\mid P\in\mathcal{P}\\}$ is a linkage in $G\setminus e$
that is aligned with $\mathcal{P}$. ∎

The following concept has been introduced in the work about treewidth
reduction for Planar Disjoint Paths [2].

######  Definition 4.3 (Tight concentric cycles).

Let $G$ be a plane graph, $X_{in},X_{out}\subseteq V(G)$, and
$C_{1},\dots,C_{m}$ be a sequence of cycles in $G$. We call
$C_{1},\dots,C_{m}$ concentric, if for all $i\in[m-1]$, the cycle $C_{i}$ is
contained in the interior of $\mathsf{Disc}(C_{i+1})$. When additionally
$X_{in}\subseteq\mathsf{int}(\mathsf{Disc}(C_{1}))$ and
$X_{out}\cap\mathsf{Disc}(C_{m})=\emptyset$, then we call it an
$(X_{in},X_{out})$-sequence of concentric cycles.

A $(X_{in},X_{out})$-sequence of concentric cycles is tight if, in addition,
for every $i\in[m-1]$, $\mathsf{Disc}(C_{i+1})\setminus\mathsf{Disc}(C_{i})$
does not contain a cycle $C$ with
$\mathsf{Disc}(C_{i})\subseteq\mathsf{Disc}(C)\subsetneq\mathsf{Disc}(C_{i+1})$,
and $\mathsf{Disc}(C_{1})\setminus X_{in}$ does not contain a cycle $C$ with
$X_{in}\subseteq\mathsf{Disc}(C)\subsetneq\mathsf{Disc}(C_{1})$.

When a plane graph $G$ properly embedded in $\mathsf{Ring}(I_{in},I_{out})$ is
clear from the context, we denote $V_{in}=V(G)\cap I_{in}$ and
$V_{out}=V(G)\cap I_{out}$.

######  Lemma 4.4.

Consider a graph $G$ properly embedded in $\mathsf{Ring}(I_{in},I_{out})$ with
$d=\mathsf{rdist}_{G}(V_{in},V_{out})$. Let $X_{in}\subseteq V_{in}$ and
$X_{out}\subseteq V_{out}$. Then there exists a tight
$(X_{in},X_{out})$-sequence of concentric cycles $C_{1},\dots,C_{d-1}$.

###### Proof.

Consider a graph $G^{\prime}$ obtained from $G$ by inserting a vertex $v_{in}$
inside $I_{in}$ adjacent to entire $X_{in}$ and a vertex $v_{out}$ outside
$I_{out}$ adjacent to entire $X_{out}$. The sets $X_{in}\cup\\{v_{in}\\}$ and
$X_{out}\cup\\{v_{out}\\}$ induce connected subgraphs of $G^{\prime}$ and
their radial distance is at least $d$. By Lemma 3.3 there exists cycles in
$C_{1},\dots,C_{d-1}$ in $G-(X_{in}\cup X_{out})$ that are
$(X_{in},X_{out})$-separators in $G$. By Lemma 3.4 each $C_{i}$ has $X_{in}$
in its interior and $X_{out}$ in its exterior, so $C_{1},\dots,C_{d-1}$ are
concentric. As long as this sequence is not tight, we can find a local
refinement pushing some cycle closer to $X_{in}$. After a finite number of
refinements we obtain a tight $(X_{in},X_{out})$-sequence of concentric
cycles. ∎

######  Lemma 4.5.

Consider a graph $G$ properly embedded in $\mathsf{Ring}(I_{in},I_{out})$. Let
$C_{1},\dots,C_{m}$ be a $(V_{in},V_{out})$-sequence of concentric cycles and
$S$ be an inclusion-minimal $(V_{in},V_{out})$-separator. Then there exists an
interval $J\subseteq[m]$ of size at most $|S|$ so that $S\cap
V(C_{j})\neq\emptyset$ implies $j\in J$.

###### Proof.

The minimality of $S$ implies that there exists a $G$-noose $\gamma$ with
$\gamma\cap V(G)=S$. Therefore each pair of consecutive vertices on $\gamma$
shares a face and the maximal radial distance between vertices of $S$ is at
most $|S|-1$. On the other hand, for $u\in C_{i}$, $v\in C_{j}$, we have
$\mathsf{rdist}_{G}(u,v)\geq|i-j|$. The lemma follows. ∎

When working with linkages traversing concentric cycles, it is convenient to
assume that each path in a linkage intersects each cycle exactly once. We can
enforce this property as long as the sequence of concentric cycles is tight.
The following proof is an adaptation of [56, Lemma 6.15].

######  Lemma 4.6.

Consider a graph $G$ properly embedded in $\mathsf{Ring}(I_{in},I_{out})$,
$X_{in}\subseteq V_{in}$, and $X_{out}\subseteq V_{out}$. Let
$C_{1},\dots,C_{m}$ be a tight $(X_{in},X_{out})$-sequence of concentric
cycles and $\mathcal{P}$ be a $(X_{in},X_{out})$-linkage in $G$ such that each
vertex in $X_{in}$ is an endpoint of a path in $\mathcal{P}$. Then there
exists a linkage $\mathcal{P}^{\prime}$ aligned with $\mathcal{P}$ such that
the intersection of each $P\in\mathcal{P}^{\prime}$ and each $C_{i}$ has
exactly one connected component.

###### Proof.

Let $\mathcal{P}^{\prime}$ be a linkage aligned with $\mathcal{P}$ that
minimizes the number of edges in $\bigcup_{P\in\mathcal{P}^{\prime}}V(P)$ that
do not belong to any cycle $C_{i}$. Suppose there is $i\in[d]$ and
$P\in\mathcal{P}^{\prime}$ such that $P\cap C_{i}$ has at least two connected
components. Choose the minimal $i\in[d]$ with this property. Then $P$ contains
a subpath $Q$ with endpoints on $C_{i}$ and internal vertices disjoint from
$V(C_{i})$.

First suppose that these vertices lie in the interior of
$\mathsf{Disc}(C_{i})$. By the choice of $i$ either $i=1$ or the path $Q$ does
not intersect $C_{i-1}$. If $i=1$ then by the assumption that each vertex in
$X_{in}$ is an endpoint of some path we infer that $Q$ cannot intersect
$X_{in}$. In both cases we could use $Q$ to construct a cycle $C$ enclosing
$X_{in}$ (resp. $C_{i-1}$) with
$\mathsf{Disc}(C)\subsetneq\mathsf{Disc}(C_{i})$, contradicting the tightness
of the sequence $C_{1},\dots,C_{m}$.

Now suppose that that the internal vertices of $Q$ are disjoint from
$\mathsf{Disc}(C_{i})$. Let $D$ be the bounded region of
$\mathbb{R}^{2}\setminus(C_{i}\cup Q)$ incident to $Q$ and
$Q^{\prime}\subseteq C_{i}$ be the path within $C_{i}$ whose image is
$C_{i}\cap\partial D$; then $Q^{\prime}$ connects the endpoints of $Q$ (see
Figure 7). If the internal vertices of $Q^{\prime}$ were disjoint from all the
other paths in $\mathcal{P}^{\prime}$ we could replace $Q$ with $Q^{\prime}$
(and remove some redundant vertices if we get a self-crossing of $P$) but this
would contradict the choice of $\mathcal{P}^{\prime}$. Therefore there is some
path $P^{\prime}\in\mathcal{P}^{\prime}$, $P^{\prime}\neq P$, using a vertex
$v\in V(C_{i})$ being internal in $Q^{\prime}$. When $i>1$ then the
$(X_{in},v)$-subpath of $P^{\prime}$ must intersect $C_{i-1}$ so by the choice
of $i$ the $(v,X_{out})$-subpath of $P^{\prime}$ cannot intersect $C_{i-1}$.
As $P^{\prime}$ is disjoint from $Q$ it must contain a subpath with endpoints
on $C_{i}$ and internal vertices in
$\mathsf{int}(\mathsf{Disc}(C_{i})\setminus\mathsf{Disc}(C_{i-1}))$. When
$i=1$ we obtain a subpath of $P^{\prime}$ with endpoints on $C_{1}$ and
internal vertices in $\mathsf{int}(\mathsf{Disc}(C_{1})\setminus X_{in}$
because $P^{\prime}$ does not have internal vertices from $X_{in}$. In both
cases we get a contradiction with the tightness of $C_{1},\dots,C_{m}$. ∎

Figure 7: An illustration of the two cases in Lemma 4.6. Left: The green
subpath $Q$ of $P$ is contained in
$\mathsf{Disc}(C_{i})\setminus\mathsf{Disc}(C_{i-1})$ what contradicts the
tightness of the sequence. Right: $Q$ is internally disjoint from
$\mathsf{Disc}(C_{i})$. Since the chosen linkage minimizes the number of used
edges that do not belong to any cycle, some other path $P^{\prime}$ must visit
the arc of $C_{i}$ between the endpoints of $Q$, again leading to a
contradiction.

We will work with the notion of a cylindrical grid, which can be regarded as
an outcome of identifying the opposite sides of a standard grid.

######  Definition 4.7.

Let $k\geq 3$, $m\geq 1$. The $(k,m)$-cylindrical grid $C_{k}^{m}$ is a plane
graph constructed as follows. We draw $m$ concentric cycles referred to as
$C^{1},\dots,C^{m}$, counting from the innermost one. Then we draw $k$
pairwise disjoint lines connecting $C^{1}$ to $C^{m}$; these lines are called
$C_{1},\dots,C_{k}$, counting clockwise. We turn each intersection of $C_{i}$
and $C^{j}$ into a vertex, referred to as $c_{i}^{j}$.

We require $k\geq 3$ in order to avoid using parallel edges and restrict our
arguments only to simple graphs. The (4, 8)-cylindrical grid is shown in
Figure 8. It is known [48, Lemma 4.2] that a large linkage between two sets
that are far apart in the radial distance entails a minor model of a large
cylindrical grid. We need an intuitive strengthening of this fact relating the
endpoints in this linkage to the branch sets in the minor model.

######  Lemma 4.8.

Consider a graph $G$ properly embedded in $\mathsf{Ring}(I_{in},I_{out})$ and
$m=\mathsf{rdist}_{G}(V_{in},V_{out})\geq 2$. Suppose that
$\mathcal{T}=(s_{1},t_{1}),\dots,(s_{k},t_{k})$ is realizable in $G$, where
$k\geq 3$, and $s_{1},\dots,s_{k}$ lie in this cyclic order on $I_{in}$ and
$t_{1},\dots,t_{k}$ lie in this cyclic order on $I_{out}$ (both counted
clockwise). Then $G$ contains a minor model of the cylindrical grid
$C^{m-1}_{k}$ such that for each $i\in[k]$ the vertex $s_{i}$ belongs to the
branch set of $c^{1}_{i}$ and $t_{i}$ belongs to the branch set of
$c^{m-1}_{i}$.

###### Proof.

Let $X_{in}=V_{\mathcal{T}}\cap V_{in}$ and $X_{out}=V_{\mathcal{T}}\cap
V_{out}$; then $\mathsf{rdist}_{G}(X_{in},X_{out})\geq m$. By Lemma 4.4 there
exists a tight $(X_{in},X_{out})$-sequence of concentric cycles
$C_{1},\dots,C_{m-1}$ in $G$. We can apply Lemma 4.6 to obtain that there
exists a $\mathcal{T}$-linkage $\mathcal{P}$ such that the intersection of
each $P\in\mathcal{P}$ and each $C_{i}$ is a single segment of $C$. Let
$G^{\prime}$ be the union of all paths in $\mathcal{P}$ and the cycles
$C_{1},\dots,C_{m-1}$. Let $P_{i}$ denote the $(s_{i},t_{i})$-path in
$\mathcal{P}$; then $P_{1},\dots,P_{k}$ are ordered clockwise. The set
$V(P_{i})\cap V(C_{j})$ induces a connected subgraph of $G^{\prime}$; we
contract it into a single vertex referred to as $c_{i}^{j}$. Let
$G^{\prime\prime}$ be the graph obtained by these contractions; then
$G^{\prime\prime}$ is a minor of $G$ and each vertex $c_{i}^{j}$ has exactly
four neighbors in $G^{\prime\prime}$. Next, we contract every degree-2 vertex
with one of its neighbors. Finally, we contract each degree-1 vertex with its
only neighbor so $s_{i}$ gets contracted with $c_{i}^{1}$ and $t_{i}$ gets
contracted with $c_{i}^{m-1}$. The claim follows. ∎

A linkage in a cylindrical grid can be transformed into a linkage in graph $G$
using the following observation.

######  Observation 4.9.

Let $G,H$ be graphs and $(V_{h})_{h\in V(H)}$ be a minor model of $H$ in $G$.
Consider a set of pairs $(s_{1},t_{1}),\dots,(s_{k},t_{k})$ from $V(G)\times
V(G)$ with all the vertices distinct. Suppose there exists an injection
$\pi:\bigcup_{i=1}^{k}\\{s_{i}\\}\cup\\{t_{i}\\}\to V(H)$ such that $s_{i}\in
V_{\pi(s_{i})}$ and $t_{i}\in V_{\pi(t_{i})}$. If
$(\pi(s_{1}),\pi(t_{1})),\dots,(\pi(s_{k}),\pi(t_{k}))$ is realizable in $H$
then $(s_{1},t_{1}),\dots,(s_{k},t_{k})$ is realizable in $G$.

Because $\mathrm{\textbf{tw}}(C_{t}^{t})\geq t$ [23, §7.7.1] and treewidth is
a monotone measure with respect to taking minors, we also obtain the following
corollary from Lemma 4.8. Note that $|i-j|\geq t+1$ implies
$\mathsf{rdist}(C_{i},C_{j})\geq t+1$.

######  Corollary 4.10.

Let $G$ be a plane graph and $C_{1},\dots,C_{m}$ be a concentric sequence of
cycles. Suppose there exists $i,j\in[m]$ such that $|i-j|\geq t+1$ and
$\mu_{G}(C_{i},C_{j})\geq t$. Then $\mathrm{\textbf{tw}}(G)\geq t$.

A $(V_{in}\cup V_{out})$-linkage may contain paths (or subpaths) with both
endpoints in $V_{in}$ or both in $V_{out}$. The next lemma assures that we can
always assume that such paths do not go “too deep” inside the graph. The proof
uses similar ideas as [2, Lemma 3].

######  Lemma 4.11.

Let $G$ be a plane graph properly embedded in $\mathsf{Ring}(I_{in},I_{out})$
and $t=\max(|V_{in}|,|V_{out}|)$. Let $C_{1},\dots,C_{m}$ be a
$(V_{in},V_{out})$-sequence of concentric cycles. Then for every $(V_{in}\cup
V_{out})$-linkage $\mathcal{P}$ there exists a linkage $\mathcal{P}^{\prime}$
aligned with $\mathcal{P}$ such that

  1. 1.

every inclusion-minimal $(V_{in}\cup V_{out})$-subpath of a path in
$\mathcal{P}^{\prime}$, that is a $(V_{in},V_{in})$-path, intersects at most
$t$ first cycles in $C_{1},\dots,C_{m}$, and

  2. 2.

every inclusion-minimal $(V_{in}\cup V_{out})$-subpath of a path in
$\mathcal{P}^{\prime}$, that is a $(V_{out},V_{out})$-path, intersects at most
$t$ last cycles in $C_{1},\dots,C_{m}$.

###### Proof.

Let $\mathcal{P}^{\prime}$ be a linkage aligned with $\mathcal{P}$ that
minimizes the number of edges in $\bigcup_{P\in\mathcal{P}^{\prime}}V(P)$ that
do not belong to any cycle $C_{i}$. Let $\widehat{}\mathcal{P}$ be the family
of the inclusion-minimal $(V_{in}\cup V_{out})$-subpaths of paths in
$\mathcal{P}^{\prime}$. Then $\widehat{}\mathcal{P}$ is a family of internally
disjoint paths and each endpoint can be shared by at most two paths. For a
$(V_{in},V_{in})$-path $P\in\widehat{}\mathcal{P}$ we define $R(P)$ as the
bounded region of $\mathbb{R}^{2}\setminus(P\cup I_{in})$ incident to $P$. Let
$h(P)$ be the number of paths from $\widehat{}\mathcal{P}$, different from
$P$, which are contained in $R(P)$. We have $h(P)\leq t-1$ and for every path
$P^{\prime}\neq P$ contained in $R(P)$ it holds that $h(P^{\prime})<h(P)$.

We show inductively that when $h(P)=\ell$ then $P$ intersects at most $\ell+1$
first cycles in $C_{1},\dots,C_{m}$. First consider $\ell=0$ and suppose that
$P$ intersect $C_{2}$. Let $P^{\prime}$ be a $(C_{1},C_{1})$-subpath of $P$
with internal vertices disjoint from $\mathsf{Disc}(C_{1})$. Then there exists
a path $P^{\prime\prime}\subset C_{1}\cap R(P)$ with the same endpoints as
$P^{\prime}$. We can replace $P^{\prime}$ with $P^{\prime\prime}$ in $P$ and,
as a result, obtain a linkage aligned with $\mathcal{P}^{\prime}$ which uses
less edges not belonging to any cycle $C_{i}$. This gives a contradiction.

Assume now that the claim holds for $h(P)<\ell$ and consider
$P\in\widehat{}\mathcal{P}$ with $h(P)=\ell$ with intersects $C_{\ell+2}$. Let
$P^{\prime}$ be a $(C_{\ell+1},C_{\ell+1})$-subpath of $P$ with internal
vertices disjoint from $\mathsf{Disc}(C_{\ell+1})$. Then there exists a path
$P^{\prime\prime}\subset C_{\ell+1}\cap R(P)$ with the same endpoints as
$P^{\prime}$. By the assumption, this path is disjoint from all paths in
$R(P)$ different than $P$. Again, by a replacement argument we obtain a
linkage aligned with $\mathcal{P}^{\prime}$ with a smaller cost.

This concludes the proof of the first part. The second part, concerning
$(V_{out},V_{out})$-paths in $\widehat{}\mathcal{P}$, is symmetric. ∎

###  4.2 Radial diameter reduction

As outlined in Section 2, we will reduce the radial diameter of the graph $G$
by repeatedly removing irrelevant edges. We focus on the scenario where a
subgraph of $G$, devoid of terminals, can be properly embedded in
$\mathsf{Ring}(I_{in},I_{out})$ and $\mathsf{rdist}(V_{in},V_{out})$ is large.
We inspect two cases, first analyzing non-maximal linkages, in which the
number of $(V_{in},V_{out})$-paths is less than $\mu(V_{in},V_{out})$. Later
on we will be armed with two strategies for detecting an irrelevant edge, each
applicable in a different setting.

####  4.2.1 Rerouting a non-maximal linkage

We are going to show that when $\mathcal{T}\subseteq V_{in}\times V_{out}$,
$|\mathcal{T}|<\mu(V_{in},V_{out})$, and $\mathsf{rdist}(V_{in},V_{out})$ is
large, then the cut-condition $|\mathcal{T}|\leq\mu(V_{\mathcal{T}}\cap
V_{in},V_{\mathcal{T}}\cap V_{out})$ is sufficient for a $\mathcal{T}$-linkage
to exist. We begin with an argument for cylindrical grids.

######  Lemma 4.12.

Consider the cylindrical grid $C_{k}^{m}$ with $m\geq k^{2}$, $k\geq 3$. Let
vertices $s_{1},\dots,s_{k-1}$ lie in this cyclic order on $C^{1}$ and
vertices $t_{1},\dots,t_{k-1}$ lie in this cyclic order on $C^{m}$ (both
counted clockwise). Then $\\{(s_{1},t_{1}),\dots,(s_{k-1},t_{k-1})\\}$ is
realizable in $C_{k}^{m}$.

###### Proof.

For two vertices $u,v\in V(C_{k}^{m})$ we define $\mathsf{Shift}(u,v)$ as
follows. Let $i,j\in[k]$ be such that $u\in V(C_{i})$ and $v\in V(C_{j})$.
Then $\mathsf{Shift}(u,v)$ is the minimum non-negative integer $\ell$
satisfying $(i+\ell)\mod k=j\mod k$. In other words, it is the number of
clockwise jumps needed to reach $C_{j}$ from $C_{i}$. We will show the
following claim by induction on $j$.

######  Claim 4.13.

Consider the cylindrical grid $C_{k}^{m}$ where $k\geq 3$, $m=(j+1)k$, for
some $j\geq 0$. Let vertices $s_{1},\dots,s_{k-1}$ lie in this cyclic order on
$C^{1}$ and vertices $t_{1},\dots,t_{k-1}$ lie in this cyclic order on $C^{m}$
(both counted clockwise). If $\mathsf{Shift}(s_{1},t_{1})=j$ then
$\\{(s_{1},t_{1}),\dots,(s_{k},t_{k})\\}$ is realizable in $C_{k}^{m}$.

###### Proof.

First consider the basic case $j=0$ in which $m=k$. Since
$\mathsf{Shift}(s_{1},t_{1})=0$ we can assume w.l.o.g. that $s_{1},t_{1}$ both
lie on $C_{1}$, that is, $s_{1}=c^{1}_{1}$, $t_{1}=c^{k}_{1}$. Let $s^{*}$ be
the unique vertex in $C^{1}\setminus\\{s_{1},\dots,s_{k-1}\\}$ and $t^{*}$ be
the unique vertex in $C^{k}\setminus\\{t_{1},\dots,t_{k-1}\\}$. For the
clarity of presentation we examine only the extremal case $s^{*}=c^{1}_{k}$,
$t^{*}=c^{k}_{2}$ in detail; the other cases are analogous. The pair
$(s_{1},t_{1})$ can be connected directly via the path $P_{1}=C_{1}$. By the
assumption on the cyclic order we have that for each $i\in[2,k-1]$ the vertex
$s_{i}$ lies on $C_{i}$ and $t_{i}$ lies on $C_{i+1}$. For $i\in[2,k-1]$ we
define the path $P_{i}$ as a concatenation of

  1. 1.

the subpath of $C_{i}$ from $s_{i}=c^{1}_{i}$ to $c^{k-i+1}_{i}$,

  2. 2.

the edge $c^{k-i+1}_{i}c^{k-i+1}_{i+1}$,

  3. 3.

the subpath of $C_{i+1}$ from $c^{k-i+1}_{i+1}$ to $c^{k}_{i+1}=t_{i}$.

See Figure 8. Note that none of these paths intersect $P_{1}=C_{1}$.
Furthermore, $P_{i+1}\cap C_{i+1}$ is contained in the disc enclosed by
$C^{k-i-1}$ (inclusively) while $P_{i}\cap C_{i+1}$ is disjoint from the
interior of the disc enclosed by $C^{k-i}$. Hence, the paths
$P_{1},\dots,P_{k-1}$ are vertex-disjoint. The construction for different
$s^{*},t^{*}$ is analogous. This concludes the analysis for the case $j=0$.

Figure 8: A visualization of the cylindrical grid $C_{4}^{8}$ and the proof of
Lemma 4.12. Here $\mathsf{Shift}(s_{1},t_{1})=j=1$ so we need at least $2\cdot
4=8$ concentric cycles in 4.13. The three $(s_{i},t_{i})$-paths are drawn in
colors. The four inner cycles illustrate the inductive argument for $j>0$
where each path gets shifted once clockwise. The four outer cycles show the
argument for $j=0$ where the origin of the path ending at $t_{1}$ is already
correctly positioned and we might only need to shift the remaining ones.

Suppose that that $j>0$. Let $\pi(i)\in[k]$ be that $s_{i}=c^{1}_{\pi(i)}$ for
$i\in[k]$. Let $s^{\prime}_{i}$ be the vertex $c^{k}_{j}$ where $j=\pi(i)+1$
modulo $k$. Then $\mathsf{Shift}(s^{\prime}_{1},t_{1})=j-1$. By the inductive
assumption, the $(k,jk)$-cylindrical grid induced by the cycles
$C^{k+1},C^{k+2},\dots,C^{m}$ contains a linkage connecting pairs
$(s^{\prime}_{1},t_{1}),\dots,(s^{\prime}_{k-1},t_{k-1})$. Therefore, it
suffices to construct a linkage $(P_{1},\dots,P_{k-1})$ in $C_{k}^{k}$
connecting pairs $(s_{1},s^{\prime}_{1}),\dots,(s_{k-1},s^{\prime}_{k-1})$.
Due to the assumption on the cyclic order we can assume w.l.o.g. that
$\pi(i)=i$ for each $i\in[k-1]$. Then the path $P_{i}$ for $i\in[k-1]$ is
given by the same concatenation formula as in the case $j=0$. Again, these
paths are vertex-disjoint, which yields the claim. ∎

The lemma follows from the observation that $\mathsf{Shift}(s_{1},t_{1})<k$ so
the claim can be applied. ∎

Now we generalize the argument from a cylindrical grid to the general case.

######  Lemma 4.14.

Let $G$ be a graph properly embedded in $\mathsf{Ring}(I_{in},I_{out})$ and
$r<p$ be integers. Suppose that $\mu_{G}(V_{in},V_{out})\geq p$ and
$\mathsf{rdist}_{G}(V_{in},V_{out})\geq p^{2}+1$. Let vertices
$s_{1},\dots,s_{r}$ lie in this cyclic order on $I_{in}$ and vertices
$t_{1},\dots,t_{r}$ lie in this cyclic order on $I_{out}$ (both counted
clockwise). Then $\mathcal{T}=\\{(s_{1},t_{1}),\dots,(s_{r},t_{r})\\}$ is
realizable in $G$ if and only if
$\mu_{G}(\\{s_{1},\dots,s_{r}\\},\\{t_{1},\dots,t_{r}\\})\geq r$.

###### Proof.

The lemma is trivial for $r=1$ so we will assume $r\geq 2$. The condition
$\mu_{G}(V_{\mathcal{T}}\cap V_{in},V_{\mathcal{T}}\cap V_{out})\geq r$ is
clearly necessary for a $\mathcal{T}$-linkage to exist. Suppose that this
condition holds and let $\mathcal{P}$ be some $(V_{\mathcal{T}}\cap
V_{in},V_{\mathcal{T}}\cap V_{out})$-linkage of size $r$. Since
$r<\mu_{G}(V_{in},V_{out})$, by Lemma 3.2 there exist vertices $s^{*}\in
V_{in}\setminus V_{\mathcal{T}}$, $t^{*}\in V_{out}\setminus V_{\mathcal{T}}$,
and a linkage $\mathcal{P}^{\prime}$ connecting sets
$S=\\{s_{1},\dots,s_{r},s^{*}\\}$ and $T=\\{t_{1},\dots,t_{r},t^{*}\\}$. Note
that $3\leq r+1=|S|=|T|\leq p$. By Lemma 4.8 the graph $G$ contains a minor
model of $C_{r+1}^{m}$, where $m=p^{2}\geq(r+1)^{2}$, and there are bijections
$\pi_{S}\colon S\to C^{1}$, $\pi_{T}\colon T\to C^{m}$ that preserve the
cyclic ordering, such that $s\in S$ belongs to the branch set of $\pi_{S}(s)$
and $t\in T$ belongs to the branch set of $\pi_{T}(t)$. We can thus assume
w.l.o.g. that $\pi_{S}(s_{1}),\dots,\pi_{S}(s_{r})$ lie in this cyclic order
on $C^{1}$ and $\pi_{T}(t_{1}),\dots,\pi_{T}(t_{r})$ lie in this cyclic order
on $C^{m}$, counted clockwise. By Lemma 4.12 the set of pairs
$\\{(\pi_{S}(s_{1}),\pi_{T}(t_{1})),\dots,(\pi_{S}(s_{r}),\pi_{T}(t_{r})\\}$
is realizable in $C_{r+1}^{m}$. Then the lemma follows from 4.9. ∎

Our goal is to detect an edge that can be safely removed without modifying the
family of possible non-maximal linkages. We can assume that the
$(V_{in},V_{in})$-paths and the $(V_{out},V_{out})$-paths intersect only few
cycles in the concentric family, so the main challenge is to preserve the non-
maximal $(V_{in},V_{out})$-linkages. As we know that the cut-condition is
sufficient for a such a linkage to exist, it remains to find an edge $e$ whose
removal does not affect any cut-condition. We show that this can be guaranteed
by two requirements: (a) removing $e$ does not decrease $\mu(V_{in},V_{out})$
and, (b) $e$ has sufficiently large radial distance from both $V_{in}$ and
$V_{out}$.

######  Proposition 4.15.

Let $G$ be a graph properly embedded in $\mathsf{Ring}(I_{in},I_{out})$,
$t=\max(|V_{in}|,|V_{out}|)$, and $s=\mu_{G}(V_{in},V_{out})$. Let
$C_{1},\dots,C_{m}$ be a $(V_{in},V_{out})$-sequence of concentric cycles in
$G$ and $m\geq(t+2)^{2}$.

Consider $i\in[2t+1,m-2t]$ and edge $e\in E(C_{i})$ such that $\mu_{G\setminus
e}(V_{in}V_{out})=\mu_{G}(V_{in},V_{out})=s$. Let
$\mathcal{T}\subseteq(V_{in}\cup V_{out})^{2}$. Suppose that $\mathcal{T}$
contains less than $s$ pairs with one element in $V_{in}$ and one in
$V_{out}$. Then $\mathcal{T}$ is realizable in $G$ if and only if
$\mathcal{T}$ is realizable in $G\setminus e$.

Furthermore, there exists at least one edge $e$ satisfying the requirements
above and it can be found in polynomial time.

###### Proof.

When $\mathcal{T}$ is realizable in $G$ then, by Lemma 4.11, there exists a
$\mathcal{T}$-linkage $\mathcal{P}$ in $G$ such that every
$(V_{in},V_{in})$-path in $\mathcal{P}$ intersects at most $t$ of the first
cycles in the sequence $C_{1},\dots,C_{m}$, while every
$(V_{out},V_{out})$-path in $\mathcal{P}$ intersects at most $t$ of the last
cycles in $C_{1},\dots,C_{m}$. Let
$\mathcal{P}_{\textrm{long}}\subseteq\mathcal{P}$ be the subfamily of paths
from $\mathcal{P}$ with one endpoint in $V_{in}$ and one in $V_{out}$. By the
assumption $|\mathcal{P}_{\textrm{long}}|<s$. If
$\mathcal{P}_{\textrm{long}}=\emptyset$ then we are done; suppose that this is
not the case.

The graph obtained from $G$ by removing the paths from
$\mathcal{P}\setminus\mathcal{P}_{\textrm{long}}$ has exactly one connected
component containing the paths from $\mathcal{P}_{\textrm{long}}$; let
$G^{\prime}$ indicate this component. Let $V^{\prime}_{in}\subseteq
V(G^{\prime})$ be the set of vertices lying on the inner face of $G^{\prime}$
containing $I_{in}$ and $V^{\prime}_{out}\subseteq V(G^{\prime})$ be the set
of vertices lying on the outer face of $G^{\prime}$.

Figure 9: An illustration for Proposition 4.15. The nooses $I_{in},I_{out}$
are dotted and the $(V_{in},V_{out})$-sequence of concentric cycles
$C_{1},\dots,C_{m}$ is gray. The cycles $C_{t+1},C_{m-t}$ are highlighted. To
obtain graph $G^{\prime}$, we remove from $G$ the paths in
$\mathcal{P}\setminus\mathcal{P}_{\textrm{long}}$ (which do not intersect
$C_{t+1},C_{m-t}$) together with the shaded area. The edge $e$ is drawn solid
red. The proposition relies on the observation that any inclusion-minimal
separator $S$ in $G^{\prime}\setminus e$ between a vertex inside $C_{t+1}$ and
a vertex outside $C_{m-t}$, such that $S$ is not present in $G^{\prime}$, is
represented by a noose (dashed) intersecting $e$. Since $e\in C_{i}$, where
$i$ is sufficiently far for $t+1$ and $m-t$, this noose cannot intersect
$C_{t+1},C_{m-t}$ so it must be a $(C_{t+1},C_{m-t})$-separator as well.

######  Claim 4.16.

It holds that $\mu_{G^{\prime}}(V^{\prime}_{in},V^{\prime}_{out})\geq s$.

###### Proof.

Let $\mathcal{P}_{max}$ be a $(V_{in},V_{out})$-linkage of size $s$ in $G$.
Then each path $P$ from $\mathcal{P}_{max}$ has a non-empty intersection with
$V(G^{\prime})$. In particular, $P$ contains a subpath being a
$(V^{\prime}_{in},V^{\prime}_{out})$-path in $G^{\prime}$. This gives a
$(V^{\prime}_{in},V^{\prime}_{out})$-linkage in $G^{\prime}$ of size $s$. ∎

All the cycles $C_{t+1},\dots,C_{m-t}$ are contained in $G^{\prime}$ and so is
$e$. Hence $\mathsf{rdist}_{G^{\prime}}(V^{\prime}_{in},V^{\prime}_{out})\geq
m-2t\geq t^{2}+2$ and $\mathsf{rdist}_{G^{\prime}\setminus
e}(V^{\prime}_{in},V^{\prime}_{out})\geq t^{2}+1\geq s^{2}+1$. Let
$e=v_{1}v_{2}$. Then each of $v_{1},v_{2}$ is separated from each of
$V^{\prime}_{in},V^{\prime}_{out}$ with at least $t$ cycles from
$C_{t+1},\dots,C_{m-t}$.

######  Claim 4.17.

It holds that $\mu_{G^{\prime}\setminus
e}(V^{\prime}_{in},V^{\prime}_{out})\geq s$.

###### Proof.

Suppose otherwise. Then there exists a $(G^{\prime}\setminus e)$-noose
$\gamma$ in the plane which separates $V^{\prime}_{in}$ from
$V^{\prime}_{out}$ and intersects $G^{\prime}\setminus e$ on at most $s-1$
vertices; let $S=\gamma\cap V(G^{\prime}\setminus e)$. By 4.16 there are no
such small $(V^{\prime}_{in},V^{\prime}_{out})$-separators in $G^{\prime}$.
Therefore $\gamma$ must intersect the image of $e$ and so $S$ contains a
vertex $u$ that lies on a common face with $e$ in $G^{\prime}$. Suppose that
$\gamma$ intersects $C_{t+1}$; then it must also intersect $C_{i-1}$. Lemma
4.5 implies that $|(i-1)-(t-1)|=|i-t-2|\leq s-2\leq t-2$ but this contradicts
the assumption that $i\geq 2t+1$. By the symmetric argument, $\gamma$ cannot
intersect $C_{m-t}$. Therefore, the curve $\gamma$ must be contained in the
interior of $\mathsf{Ring}(C_{t+1},C_{m-t})$ and so $S$ is a
$(C_{t+1},C_{m-t})$-separator in $G^{\prime}\setminus e$: see Figure 9. As a
consequence, $S$ is also a $(V_{in},V_{out})$-separator in $G\setminus e$.
This implies that $\mu_{G\setminus e}(V_{in},V_{out})\leq s-1$ and contradicts
the assumption that $\mu_{G\setminus
e}(V_{in},V_{out})=\mu_{G}(V_{in},V_{out})$. ∎

Note that $\mathcal{P}_{\textrm{long}}$ is a
$(V^{\prime}_{in},V^{\prime}_{out})$-linkage in $G^{\prime}$. Let
$T_{in}\subseteq V^{\prime}_{in},T_{out}\subseteq V^{\prime}_{out}$ be the
sets of endpoints of paths from $\mathcal{P}_{\textrm{long}}$.

######  Claim 4.18.

It holds that $\mu_{G^{\prime}\setminus
e}(T_{in},T_{out})\geq|\mathcal{P}_{\textrm{long}}|$.

###### Proof.

Clearly, $\mu_{G^{\prime}}(T_{in},T_{out})\geq|\mathcal{P}_{\textrm{long}}|$.
Suppose that such an inequality does not hold in $G^{\prime}\setminus e$.
Similarly as in 4.17, there exists a $(G^{\prime}\setminus e)$-noose $\gamma$
in the plane which separates $T_{in}$ from $T_{out}$ and intersects
$G^{\prime}\setminus e$ on at most $|\mathcal{P}_{\textrm{long}}|-1$ vertices;
let $S=\gamma\cap V(G^{\prime}\setminus e)$. By the same argument as before we
obtain that $\gamma$ is contained in the interior of
$\mathsf{Ring}(C_{t+1},C_{m-t})$ and $S$ is a $(V_{in},V_{out})$-separator in
$G\setminus e$. Recall that $e=v_{1}v_{2}$. Observe that any
$(V_{in},V_{out})$-path in $G-S$ must go through $e$ so $S\cup\\{v_{1}\\}$ is
a $(V_{in},V_{out})$-separator in $G$. Hence,
$\mu_{G}(V_{in},V_{out})\leq|S|+1\leq|\mathcal{P}_{\textrm{long}}|$. This
contradicts the assumption that
$|\mathcal{P}_{\textrm{long}}|<s=\mu_{G}(V_{in},V_{out})$. ∎

The two claims above allows us to apply the criterion from Lemma 4.14 to
$G^{\prime}\setminus e,V^{\prime}_{in},V^{\prime}_{out}$,
$\mathcal{P}_{\textrm{long}}$ with $p=s$, $r=|\mathcal{P}_{\textrm{long}}|<p$,
and $\mathsf{rdist}_{G^{\prime}\setminus
e}(V^{\prime}_{in},V^{\prime}_{out})\geq p^{2}+1$. We derive that there exists
a linkage in $G^{\prime}\setminus e$ aligned with
$\mathcal{P}_{\textrm{long}}$. By the construction of $G^{\prime}$ this
implies that there exists a linkage in $G\setminus e$ aligned with
$\mathcal{P}$.

It remains to justify that $e$ can be efficiently found. First,
$(t+2)^{2}-4t>0$ so the interval $[2t+1,m-2t]$ is non-empty. A
$(V_{in},V_{out})$-linkage $\mathcal{P}_{max}$ of size $s$ can be found in
polynomial time. Then $e$ can be chosen as any edge on $C_{i}$ that is not
used by $\mathcal{P}_{max}$. ∎

####  4.2.2 Rerouting a maximal linkage

We move on to the scenario in which the number of $(V_{in},V_{out})$-paths in
a linkage equals $\mu(V_{in},V_{out})$. The crucial special case occurs when
$|V_{in}|=|V_{out}|=\mu(V_{in},V_{out})$. This is the same setting that has
been studied by Robertson and Seymour [87] as a subroutine in their FPT
algorithm for Planar Disjoint Paths. We shall adopt the same perspective for
analyzing this case, based on the following convenient plane embedding.

######  Definition 4.19.

A plane graph $G$ is called $k$-cylindrical if:

  1. 1.

It is properly embedded in $\mathsf{Ring}(I_{in},I_{out})$ where
$I_{in}=\\{(x,y)\in\mathbb{R}^{2}\mid x^{2}+y^{2}=1\\}$ and
$I_{out}=\\{(x,y)\in\mathbb{R}^{2}\mid x^{2}+y^{2}=4\\}$;

  2. 2.

The sets $V_{in}=V(G)\cap I_{in}$ and $V_{out}=V(G)\cap I_{out}$ have size $k$
each;

  3. 3.

$V_{in}=\\{(1,\frac{2j}{k}\pi)\\}_{0\leq j<k}$ and
$V_{out}=\\{(2,\frac{2j}{k}\pi)\\}_{0\leq j<k}$ in polar coordinates, and

  4. 4.

$\mu_{G}(V_{in},V_{out})=k$.

We refer to the elements of $V_{in}$ as $s_{0},s_{1},\dots,s_{k-1}$ so that
$s_{j}$ has polar coordinates $(1,\frac{-2\pi}{k}j)$. Similarly,
$t_{0},t_{1},\dots,t_{k-1}$ are the elements of $V_{out}$ and
$t_{j}=(2,\frac{-2\pi}{k}j)$.

######  Definition 4.20.

For a path $P$ connecting $s\in V_{in}$ and $t\in V_{out}$ we define its
winding number $\theta(P)\in\mathbb{Z}$ as $\frac{k}{2\pi}$ times the total
angle traversed by the curve corresponding to $P$ (measured clockwise).

See Figure 2 on page 2 for an example. Intuitively, the winding number
measures how many times a path winds around the ring (and in which direction)
and what is the difference in the angles of its endpoints.

######  Definition 4.21.

A cylindrical linkage in $G$ is a $(V_{in},V_{out})$-linkage of size $k$. When
$\mathcal{P}$ is cylindrical then every path $P\in\mathcal{P}$ has the same
winding number and we refer to it as $\theta(\mathcal{P})$. We say that
$\theta$ is feasible in $G$ if there is a cylindrical linkage in $G$ with the
winding number $\theta$.

We remark that Robertson and Seymour [87] defined the winding number of $P$ as
$-\theta(P)/k$ but we choose this convention so we could work with integers
and the more intuitive clockwise ordering.

######  Lemma 4.22 ([87, Lem. 5.9]).

Let $G$ be a $k$-cylindrical graph. If $\theta_{1}<\theta_{2}<\theta_{3}$ and
$\theta_{1},\theta_{3}$ are feasible in $G$, then so is $\theta_{2}$.

For a $k$-cylindrical graph $G$ let $\Theta^{G}$ be the set of all feasible
values of $\theta$. By Lemma 4.22 the set $\Theta^{G}$ forms an interval of
integers and it is non-empty because $\mu_{G}(V_{in},V_{out})=k$. The set
$\Theta^{G}$ is always finite and it can enumerated efficiently.

######  Lemma 4.23 ([87, Lem. 5.11]).

There is a polynomial-time algorithm that, given a $k$-cylindrical graph $G$,
enumerates the set $\Theta^{G}$.

We define $\theta^{G}_{1},\theta^{G}_{2}$ as follows. If $|\Theta^{G}|<k$ then
$\theta^{G}_{1}=\min\Theta^{G}$ and $\theta^{G}_{2}=\max\Theta^{G}$.
Otherwise, we set $\theta^{G}_{1}=\min\Theta^{G}$ and
$\theta^{G}_{2}=\theta^{G}_{1}+k-1$.

######  Observation 4.24.

Let $G$ be a $k$-cylindrical graph. Then
$[\theta^{G}_{1},\theta^{G}_{2}]\subseteq\Theta^{G}$. Furthermore, if
$\theta\in\Theta^{G}$ then there exists
$\theta^{\prime}\in[\theta^{G}_{1},\theta^{G}_{2}]$ such that
$\theta^{\prime}\equiv\theta\mod k$.

For $j\in[0,k-1]$ let $\mathcal{T}_{j}\subseteq V_{in}\times V_{out}$ be the
set of pairs $(s_{i},t_{i+j\mod k})_{i\in[0,k-1]}$. Clearly, $\mathcal{T}_{j}$
is realizable in $G$ if and only if there exists $\theta\in\Theta^{G}$ such
that $(\theta\mod k)=j$. This is equivalent to the existence of
$\theta\in[\theta^{G}_{1},\theta^{G}_{2}]$ with $(\theta\mod k)=j$. Combining
all these observations with the strategy for coping with non-maximal linkages
yields a criterion for an edge to be irrelevant in a $k$-cylindrical graph.

######  Lemma 4.25.

Let $G$ be a $k$-cylindrical graph and $C_{1},\dots,C_{m}$ be a
$(V_{in},V_{out})$-sequence of concentric cycles in $G$ with $m\geq(k+2)^{2}$.
Consider $i\in[2k+1,m-2k]$ and edge $e\in E(C_{i})$ such that
$\theta^{G}_{1},\theta^{G}_{2}$ are feasible in $G\setminus e$. Then
$G\setminus e$ is $(V_{in}\cup V_{out})$-linkage-equivalent to $G$.

###### Proof.

The assumptions imply that $\mu_{G\setminus
e}(V_{in},V_{out})=\mu_{G}(V_{in},V_{out})=k$. Consider some
$\mathcal{T}\subseteq(V_{in}\cup V_{out})^{2}$ that is realizable in $G$. Let
$\ell$ be the number of pairs in $\mathcal{T}$ with one endpoint in $V_{in}$
and one in $V_{out}$. If $\ell<k$ then $\mathcal{T}$ is realizable in
$G\setminus e$ due to Proposition 4.15. Suppose that $\ell=k$. Then
$\mathcal{T}=\mathcal{T}_{j}$ for some $j\in[0,k-1]$ for which there exists
$\theta\in\Theta^{G}$ such that $(\theta\mod k)=j$. By 4.24 we can assume that
$\theta\in[\theta^{G}_{1},\theta^{G}_{2}]$. As both
$\theta^{G}_{1},\theta^{G}_{2}$ are feasible in $G\setminus e$, it follows
from Lemma 4.22 that so is $\theta$. ∎

##### Disentangling cylindrical linkages.

While finding an edge not required by a single linkage is simple, finding a
single edge that is not needed by two linkages is more challenging. A priori,
it could be the case then the union of any linkages $\mathcal{P}_{1}$ with
$\theta(\mathcal{P}_{1})=\theta_{1}^{G}$ and $\mathcal{P}_{2}$ with
$\theta(\mathcal{P}_{2})=\theta_{2}^{G}$ is the entire graph. We show that
this is not the case by constructing linkages
$\mathcal{P}_{1},\mathcal{P}_{2}$ whose intersection pattern is relatively
simple.

We need two additional tools to achieve this goal. We begin with ordering
$(u,v)$-paths in a $k$-cylindrical graph in a clockwise fashion.

######  Definition 4.26.

Let $G$ be a $k$-cylindrical graph, $u\in V_{in}$, and $v\in V_{out}$.
Consider two distinct $(u,v)$ paths $P_{1},P_{2}$ oriented from $u$ to $v$;
let $w$ be the last vertex on their longest common prefix.

When $w=u$, let $e_{1},\dots,e_{d}$ be the clockwise ordering of $E_{G}(u)$
such that $e_{1},e_{d}$ are incident with the face containing $I_{in}$. We
write $P_{1}\sqsubset P_{2}$ when the first edge of $P_{1}$ appears earlier in
$e_{1},\dots,e_{d}$ than the first edge of $P_{2}$.

When $w\neq u$, let $e$ be the edge preceding $w$ in both $P_{1},P_{2}$ and
$e_{1},\dots,e_{d}$ be the clockwise ordering of $E(w)\setminus e$ such that
$e$ lies between $e_{d},e_{1}$. We write $P_{1}\sqsubset P_{2}$ when the edge
following $w$ in $P_{1}$ appears earlier in $e_{1},\dots,e_{d}$ than the edge
following $w$ in $P_{2}$.

See Figure 10 for an example. The relation $\sqsubset$ is transitive and it
yields a linear order on the family of $(u,v)$-paths in $G$.

Figure 10: Three $(u,v)$-paths satisfying $P_{1}\sqsubset P_{2}\sqsubset
P_{3}$. The ring has been deformed for a better presentation. The dashed path
$Q$ is a clockwise handle of $P_{3}$.

######  Definition 4.27 (Handle, clockwise-tightness).

Let $G$ be a $k$-cylindrical graph, $u\in V_{in}$, and $v\in V_{out}$. A path
$Q$ is called a handle of $P$ is the endpoints of $Q$ lie on $P$ and $Q$ is
internally disjoint from $P$. Let $P^{Q}$ be the $(u,v)$-path obtained from
$P$ by replacing the subpath between the endpoints of $Q$ with the path $Q$.
We say that $Q$ is a clockwise handle when $P\sqsubset P^{Q}$.

We say that a cylindrical linkage $\mathcal{P}$ is clockwise-tight if no
$P\in\mathcal{P}$ contains a clockwise handle internally disjoint from all the
paths in $\mathcal{P}$.

Intuitively, being clockwise-tight means that internal points of the paths in
the linkage are maximally “bent” in the clockwise direction while maintaining
disjointedness. We show that every cylindrical linkage can be modified to be
clockwise-tight.

######  Lemma 4.28.

Let $k\geq 2$ and $G$ be a $k$-cylindrical graph and $\theta\in\Theta^{G}$.
There exists a clockwise-tight cylindrical linkage $\mathcal{P}$ in $G$ with
the winding number $\theta$.

###### Proof.

Let $\mathcal{P}$ be any cylindrical linkage in $G$ with the winding number
$\theta$. We exhaustively apply the following modification to $\mathcal{P}$:
while there exists a path $P\in\mathcal{P}$ with a clockwise handle $Q$
internally disjoint from $\mathcal{P}$, replace $P$ with $P^{Q}$. After such a
replacement, we obtain a new cylindrical linkage in $G$ with the same winding
number $\theta$ (here we use the assumption that $k\geq 2)$. We claim that
this process must terminate in a finite number of steps. If not, an infinite
number of replacements happens to a single path $P\in\mathcal{P}$. Hence,
there exists an infinite sequence of $(u,v)$-paths $P^{1}\sqsubset
P^{2}\sqsubset\dots$. This is impossible because the relation $\sqsubset$ is a
linear order and there are only finitely many different $(u,v)$-paths in $G$.
∎

The second tool is based on the following concept from topology, used in the
analysis of topological spaces with “holes”, like a torus. We only provide
simple definitions, tailored for our applications.

######  Definition 4.29 (Covering).

The covering of $\mathsf{Ring}(I_{in},I_{out})$ is a function
$\tau\colon[1,2]\times\mathbb{R}\to\mathbb{C}$ defined as
$\tau((x,y))=y\cdot\exp\left(\frac{-2i\pi}{k}\cdot x\right)$. We identify the
image of $\tau$ with $\mathsf{Ring}(I_{in},I_{out})$.

######  Observation 4.30 (Lifting).

Let $G$ be a $k$-cylindrical graph, $u=(1,\frac{-2\pi}{k}\cdot p)$,
$v=(2,\frac{-2\pi}{k}\cdot q)$ (in polar coordinates), and $P$ be a
$(u,v)$-path. Then for every $\ell\in\mathbb{Z}$ there is a unique curve
$P^{\prime}$ in $[1,2]\times\mathbb{R}$, called a lifting of $P$, that starts
at $(1,\,\ell\cdot k+p)$, ends at $(2,\,\ell\cdot k+p+\theta(P))$, and
$\tau(P^{\prime})=P$. It holds that $p+\theta(P)\equiv q\mod k$. Moreover, any
liftings of two vertex-disjoint paths are disjoint.

These notions are depicted in Figure 12. Now we can analyze two linkages with
different winding numbers through their liftings in $[1,2]\times\mathbb{R}$.
Here, we can take advantage of the fact that when two disjoint curves connect
points on a boundary of a topological disc, then these points cannot be
intrinsically crossing.

Figure 11: An illustration of 4.31. The interior of the set $D$ is
highlighted. The curves $Q_{0},Q_{1}$ are disjoint so their endpoints on the
boundary of $D$ cannot cross.

######  Observation 4.31.

Consider a curve $P$ in $[1,2]\times\mathbb{R}$ which starts at $(1,x)$, ends
at $(2,y)$, and is internally contained in $(1,2)\times\mathbb{R}$. Let $D$ be
the closure of the connected component of $([1,2]\times\mathbb{R})\setminus P$
containing the point $(1,x-1)$. Next, let $x_{0}<x_{1}\leq x$ and
$p_{0},p_{1}\in P$. Suppose that there exist disjoint curves $Q_{0},Q_{1}$ in
$D$ such that $Q_{0}$ connects $(1,x_{0})$ to $p_{0}$ and $Q_{1}$ connects
$(1,x_{1})$ to $p_{1}$. Then $p_{0}$ occurs later than $p_{1}$ on $P$ when
considered oriented from $(1,x)$ to $(2,y)$.

This observation is illustrated in Figure 11. We are ready to prove the main
technical lemma about cylindrical graphs, showing that any two cylindrical
linkages can be “disentagled”.

Figure 12: An illustration for the proof of Lemma 4.32 with $k=4$, $\ell=2$.
—- Top left: Two cylindrical linkages in a 4-cylindrical graph. For simplicity
the linkage $\mathcal{P}$ is drawn as straight dashed lines and the linkage
$\mathcal{Q}$ is drawn in colors.
—- Top right: The covering of $\mathsf{Ring}(I_{in},I_{out})$ and the liftings
of the paths. The curves
$Q^{\prime}_{0},Q^{\prime}_{1},Q^{\prime}_{2},Q^{\prime}_{3}$ are drawn in
colors matching their images on the left. Note that the curve
$Q^{\prime}_{-1}$ coincides with $Q^{\prime}_{3}$ modulo a shift. The same
applies to $Q^{\prime}_{0}$ and $Q^{\prime}_{4}$. Since $\mathcal{P}$ is
clockwise-tight, none path $P\in\mathcal{P}$ can have a clockwise handle;
hence there cannot be any curve like the red dotted one.
—- Middle right: The curves $Q_{0}^{2}$, $Q_{1}^{1}$ (red), and $Q_{2}^{3}$,
$Q_{3}^{2}$ (blue). The third one is an example of a curve $Q_{i}^{\ell+1}$
which is not necessarily contained in $Q^{\prime}_{i}$ due to the last
straight segment. This forms a special case for property (P5) but this choice
of definition guarantees property (P3). The relative position of the black
disks located on $P^{\prime}_{1}$ and $P^{\prime}_{3}$ is the subject of 4.33.
—- Bottom right: The curves $\widehat{Q}_{i}^{1}$ are drawn in red, while the
curves $\widehat{Q}_{i}^{2}$ are blue. Together with the green segments they
form the paths $R^{\prime}_{0},R^{\prime}_{1},R^{\prime}_{2},R^{\prime}_{3}$.
—- Bottom left: The images of paths $R^{\prime}_{i}$ form the sought family
$\mathcal{R}$.

######  Lemma 4.32.

Let $G$ be a $k$-cylindrical graph and
$\theta_{1}\leq\theta_{2}=\theta_{1}+\ell$, where $\ell<k$. If
$\theta_{1},\theta_{2}$ are feasible in $G$ then there exist cylindrical
linkages $\mathcal{P},\mathcal{R}$ in $G$ such that
$\theta(\mathcal{P})=\theta_{1}$, $\theta(\mathcal{R})=\theta_{2}$, and and
for each $P\in\mathcal{P},R\in\mathcal{R}$ the intersection of $P$ and $R$
comprises at most one path.

###### Proof.

If $k=1$ or $\theta_{1}=\theta_{2}$, then the claim is trivial so we can
assume $k\geq 2,\ell\geq 1$. Let $\mathcal{P},\mathcal{Q}$ be cylindrical
linkages with the winding numbers $\theta_{1},\theta_{2}$. By Lemma 4.28 we
can assume that $\mathcal{P}$ is clockwise-tight. We order the linkages in a
clockwise manner: $\mathcal{P}=P_{0},\dots P_{k-1},\mathcal{Q}=Q_{0},\dots
Q_{k-1}$, so that $P_{i}$ and $Q_{i}$ start at $(1,\frac{-2\pi}{k}i)$.
Consider the covering
$\tau\colon[1,2]\times\mathbb{R}\to\mathsf{Ring}(I_{in},I_{out})$ and the
liftings of $\mathcal{P},\mathcal{Q}$. More precisely, we consider a unique
infinite family $(P^{\prime}_{i})_{i\in\mathbb{Z}}$ of disjoint curves in
$[1,2]\times\mathbb{R}$ such that $P^{\prime}_{i}$ is a path from $(1,i)$ to
$(2,i+\theta_{1})$ and $\tau(P^{\prime}_{i})=P_{(i\mod k)}$. Similarly we
define the lifting $(Q^{\prime}_{i})_{i\in\mathbb{Z}}$ of $\mathcal{Q}$. Note
that each curve $P^{\prime}_{i},Q^{\prime}_{i}$ is internally contained in
$(1,2)\times\mathbb{R}$.

Each curve $Q^{\prime}_{i}$ must intersect
$P^{\prime}_{i},\dots,P^{\prime}_{i+\ell}$. For $i\in\mathbb{Z}$ and
$j\in[1,\ell]$ we define $Q_{i}^{j}$ as the minimal prefix of $Q^{\prime}_{i}$
which ends at $P^{\prime}_{i+j}$. Furthermore, let $\widehat{Q}_{i}^{j}$ be
the minimal suffix of $Q_{i}^{j}$ which starts at $P^{\prime}_{i+j-1}$. In
order to cover the corner cases, we define both $Q^{0}_{i}$ and
$\widehat{Q}^{0}_{i}$ to be the trivial path from $(1,i)$ to $(1,i)$,
$\widehat{Q}^{\ell+1}_{i}$ as the trivial path from $(2,i+\theta_{2})$ to
$(2,i+\theta_{2})$ (the last point on $Q^{\prime}_{i}$), and $Q^{\ell+1}_{i}$
as the concatenation of $Q^{\ell}_{i}$ with the subpath of
$P^{\prime}_{i+\ell}$ from the endpoint of $Q^{\ell}_{i}$ to
$(2,i+\theta_{2})$. We make note of the following properties that hold for
each $i\in\mathbb{Z}$ and $j\in[0,\ell+1]$:

  1. (P1)

$\widehat{Q}_{i}^{j}\subseteq Q_{i}^{j}$,

  2. (P2)

$\widehat{Q}_{i}^{j}\subseteq Q^{\prime}_{i}$,

  3. (P3)

$Q_{i}^{j}$ is internally disjoint from $P^{\prime}_{i+j}$,

  4. (P4)

$\tau(Q_{i}^{j})$ is a walk in $G$,

  5. (P5)

if $j\leq\ell$ then $Q_{i}^{j}\subseteq Q^{\prime}_{i}$.

For $i\in\mathbb{Z}$ we define $R^{\prime}_{i}$ as the unique path from
$(1,i)$ to $(2,i+\theta_{2})$ which is contained in
$P^{\prime}_{i}\cup\widehat{Q}^{1}_{i}\cup
P^{\prime}_{i+1}\cup\widehat{Q}^{2}_{i}\cup\dots\cup\widehat{Q}^{\ell}_{i}\cup
P^{\prime}_{i+\ell}$ (see Figure 12, bottom right). The intersection of
$R^{\prime}_{i}$ with $P^{\prime}_{i+j}$, for $j\in[0,\ell]$, is then a
subpath of $P^{\prime}_{i+j}$ between the endpoints of $\widehat{Q}_{i}^{j}$
and $\widehat{Q}_{i}^{j+1}$. It holds that
$\theta(\tau(R^{\prime}_{i}))=\theta_{2}$.

######  Claim 4.33.

Let $i\in\mathbb{Z}$ and $j\in[1,\ell]$. Consider points
$p_{0},p_{1}\in[1,2]\times\mathbb{R}$ such that $p_{0}\in Q^{j+1}_{i}\cap
P^{\prime}_{i+j}$ and $p_{1}\in Q^{j}_{i+1}\cap P^{\prime}_{i+j}$. Then
$p_{0}$ occurs later than $p_{1}$ on $P^{\prime}_{i+j}$, when considered
oriented from $(1,i+j)$ to $(2,i+j+\theta_{1})$.

###### Proof.

Here we exploit the fact that $\mathcal{P}$ is clockwise-tight. First consider
the case $j<\ell$ as then, by property (P5), the paths $Q^{j+1}_{i}$ and
$Q^{j}_{i+1}$ are disjoint as subpaths of $Q^{\prime}_{i},Q^{\prime}_{i+1}$.
By property (P3) both $Q^{j+1}_{i}$ and $Q^{j}_{i+1}$ are internally disjoint
from $P^{\prime}_{i+j+1}$. Let $\tilde{Q}^{\prime}_{i}$ be the prefix of
$Q^{j+1}_{i}$ ending at $p_{0}$ and $\tilde{Q}^{\prime}_{i+1}$ be the prefix
of $Q^{j}_{i+1}$ ending at $p_{1}$. Next, let $D$ be the closure of the
connected component of $([1,2]\times\mathbb{R})\setminus P^{\prime}_{i+j}$
containing the point $(1,i+j-1)$. Suppose that $\tilde{Q}^{\prime}_{i}$ or
$\tilde{Q}^{\prime}_{i+1}$ contains a point $y\not\in D$. Then
$\tilde{Q}^{\prime}_{i}$ or $\tilde{Q}^{\prime}_{i+1}$ has a subpath
$Q^{\prime\prime}$ with both endpoints on $P^{\prime}_{i+j}$ and internally
contained in the region of $[1,2]\times\mathbb{R}$ between $P^{\prime}_{i+j}$
and $P^{\prime}_{i+j+1}$. By property (P4) the image $\tau(Q^{\prime\prime})$
is a walk in $G$ and it contains a clockwise handle of
$\tau(P^{\prime}_{i+j})$ which is disjoint from $\mathcal{P}$; this
contradicts $\mathcal{P}$ being clockwise-tight. We obtain that
$\tilde{Q}^{\prime}_{i}$, $\tilde{Q}^{\prime}_{i+1}$ lie entirely within $D$.
The claim follows from 4.31.

Finally, consider the case $j=\ell$ where $Q^{\ell+1}_{i}$ is not necessarily
a subpath of of $Q^{\prime}_{i}$. However, for $p_{0}\in Q^{\ell+1}_{i}$
chosen as the unique point on $Q^{\ell}_{i}\cap P^{\prime}_{i+\ell}$ the path
$\tilde{Q}^{\prime}_{i}$, defined as above, is a subpath of $Q^{\prime}_{i}$
due to property (P5). See Figure 12, middle right. In this case
$Q^{\prime}_{i},Q^{\prime}_{i+1}$ are again disjoint and the same argument
applies. The general claim follows from the observation that any other point
$p\in Q^{\ell+1}_{i}\cap P^{\prime}_{i+\ell}$ occurs later than $p_{0}$ on
$P^{\prime}_{i+j}$. ∎

######  Claim 4.34.

The paths $(R^{\prime}_{i})_{i\in\mathbb{Z}}$ are pairwise disjoint.

###### Proof.

It suffices to show that for every $i\in\mathbb{Z}$ the paths
$R^{\prime}_{i},R^{\prime}_{i+1}$ are disjoint. By property (P2) the paths of
the form $\widehat{Q}^{j}_{i}$, $\widehat{Q}^{j^{\prime}}_{i+1}$ belong to the
disjoint paths $Q^{\prime}_{i},Q^{\prime}_{i+1}$ so they cannot intersect each
other. If $R^{\prime}_{i},R^{\prime}_{i+1}$ intersect then there must be
$j\in[1,\ell]$ so that $R^{\prime}_{i}\cap P^{\prime}_{i+j}$ and
$R^{\prime}_{i+1}\cap P^{\prime}_{i+j}$ intersect. This may happen only if the
subpath of $P^{\prime}_{i+j}$ between the endpoints of
$\widehat{Q}_{i}^{j},\widehat{Q}_{i}^{j+1}$ and the subpath of
$P^{\prime}_{i+j}$ between the endpoints of
$\widehat{Q}_{i+1}^{j-1},\widehat{Q}_{i+1}^{j}$ have a non-empty intersection.
This is impossible due to property (P1) and 4.33. ∎

It follows from the construction that
$\tau(R^{\prime}_{i})=\tau(R^{\prime}_{j})$ whenever $i\equiv j\mod k$. We can
thus define $R_{0},\dots,R_{k-1}$ as the path family in $G$ such that
$\tau(R^{\prime}_{j})=R_{(j\mod k)}$ for each $j\in\mathbb{Z}$. Since
$\ell<k$, no path $R^{\prime}_{i}$ intersects both $P^{\prime}_{j}$ and
$P^{\prime}_{j+k}$ for any $j\in\mathbb{Z}$. As each intersection
$R^{\prime}_{i}\cap P^{\prime}_{j}$ is either empty or a single path, we infer
that also each intersection $R_{i}\cap P_{j}$ is either empty or a single
path.

Consider $0\leq i<j<k$: from 4.34 we know that $R^{\prime}_{i}$,
$R^{\prime}_{j}$ are disjoint. Moreover, the path $R^{\prime}_{j}$ is
contained in the region $D$ of $[1,2]\times\mathbb{R}$ between
$R^{\prime}_{i}$ and $R^{\prime}_{i+k}$, exclusively. Because
$\tau(R^{\prime}_{i})=\tau(R^{\prime}_{i+k})=R_{i}$ and $\tau(D)\cap
R_{i}=\emptyset$, we obtain that $R_{i}$ and $R_{j}$ form disjoint subsets of
$\mathsf{Ring}(I_{in},I_{out})$; hence they are vertex-disoint paths. We
conclude that $\mathcal{R}=R_{0}\dots,R_{k-1}$ is the desired linkage with the
winding number $\theta_{2}$ and single-path intersections with $\mathcal{P}$.
∎

Since the union of two disentangled linkages cannot contain too many
concentric cycles, we can now find an edge to which the criterion from Lemma
4.25 applies.

######  Proposition 4.35.

Let $G$ be a $k$-cylindrical graph with
$\mathsf{rdist}_{G}(V_{in},V_{out})\geq(k+2)^{2}$. Then there exists an edge
$e\in E(G)$ such that $G\setminus e$ is $(V_{in}\cup V_{out})$-linkage-
equivalent to $G$. Furthermore, such an edge can be found in polynomial time.

###### Proof.

Let $C_{1},\dots,C_{m}$ be a $(V_{in},V_{out})$-sequence of concentric cycles