We present the graph modification as a recursive process in which we are given
a tuple $(G,X,T,\chi,k)$ where $X$ is a planar modulator in $G$ of size at
most $\lambda$ and $(T,\chi)$ is a tree decomposition of $G-X$ of width at
most $t$. We either conclude that $(G,X,k)$ satisfies the claim or recurse on
some tuple $(G^{\prime},X^{\prime},k-1,T^{\prime},\chi^{\prime})$ so that
$|X^{\prime}|\leq|X|$. In order to prove the forward safeness we will show
that when $\mathrm{mvp}(G)\leq k$ then
$\mathrm{mvp}(G^{\prime})\leq\mathrm{mvp}(G)-1$. To prove the backward
safeness we show that when given a planar modulator $S^{\prime}$ in
$G^{\prime}$ we can turn in into a planar modulator in $G$ of size at most
$|S^{\prime}|+3$.

Given a tuple $(G,X,T,\chi,k)$, we apply Lemma 5.6. If we get the outcome (2),
we obtain a set $X_{0}\subseteq V(G)$ of size at most 3 such that
$\mathrm{mvp}(G)\leq k$ implies $\mathrm{mvp}(G-X_{0})\leq\mathrm{mvp}(G)-1$:
this yields the forward safeness. The backward safeness follow from the fact
that when $S$ is a planar modulator in $G-X_{0}$ then $S\cup X_{0}$ is a
planar modulator in $G$. Since $G-(X\cup X_{0})$ is a subgraph of $G-X$, we
can turn $(T,\chi)$ into a tree decomposition of $G-(X\cup X_{0})$ of no
greater width.

If we get the outcome (1) from Lemma 5.6, we obtain a $(2t+2)$-strong planar
modulator $Z\supseteq X$. We have $|Z|\leq 2^{13}\cdot|X|^{6}\cdot k^{10}\cdot
t^{10}\leq 2^{13}\cdot k^{16}\cdot t^{16}$. We stop the recursion at this
point.

In order to bound the fragmentation of $Z$, let us consider another recursive
process, in which we process a triple $(G,Z,k)$ where $Z$ is a $(2t+2)$-strong
planar modulator in $G$. Whenever we recurse on $(G^{\prime},Z^{\prime},k-1)$
we demand $|Z^{\prime}|\leq|Z|$ and consider the same safeness conditions as
before: (a) $\mathrm{mvp}(G)\leq k$ implies
$\mathrm{mvp}(G^{\prime})\leq\mathrm{mvp}(G)-1$, and (b) when given a planar
modulator $S^{\prime}$ in $G^{\prime}$ we can turn in into a planar modulator
in $G$ of size at most $|S^{\prime}|+3$.

Given a triple $(G,Z,k)$ we enumerate all size-3 subsets of $Z$ and look for a
subset $Z_{0}:=\\{v_{1},v_{2},v_{3}\\}\subseteq Z$, such that for at least
$k+3$ connected components $(C_{i})_{i=1}^{k+3}$ in
$\mathcal{C}\mathcal{C}(G-Z)$ we have $Z_{0}\subseteq N_{G}(C_{i})$. Consider
any planar modulator $S$ in $G$ of size $\ell\leq k$. Analogously as in Lemma
5.3, we observe that for some $\\{i_{1},i_{2},i_{3}\\}\in[k+3]$ it must hold
that $C_{i_{j}}\cap S=\emptyset$ for each $j\in[3]$. If $Z_{0}\cap
S=\emptyset$, then $\\{v_{1},v_{2},v_{3},C_{i_{1}},C_{i_{2}},C_{i_{3}}\\}$
would form branch sets of a $K_{3,3}$ minor in $G-S$, which is not possible.
Hence, $Z_{0}\cap S\neq\emptyset$ and $S\setminus Z_{0}$ is a planar modulator
in $G-Z_{0}$ of size at most $\ell-1$. In such a scenario, we recurse on
$(G-Z_{0},Z\setminus Z_{0},k-1)$. We have $\mathrm{mvp}(G)\leq k$ implies
$\mathrm{mvp}(G-Z-0)\leq\mathrm{mvp}(G)-1$. Again, when $S$ is a planar
modulator in $G-Z_{0}$ then $S\cup Z_{0}$ is a planar modulator in $G$.
Furthermore, $Z\setminus Z_{0}$ is a $(2t+2)$-strong planar modulator in
$G-Z_{0}$.

When we can no longer find such a set $Z_{0}\subseteq Z$, we stop the
recursion and return $G$ and $X^{\prime}=Z$. By a counting argument, the
number of connected components in $G-Z$ with at least 3 neighbors cannot be
larger than $|Z|^{3}\cdot(k+2)=\mathcal{O}(k^{49}t^{48})$, which gives a bound
on the fragmentation of $Z$. ∎

##  6 Reducing the radial diameter

From now on we work with an extended modulator so that $G\langle C\rangle$ is
planar for each connected component $C$ of $G-X$. We will consider a
boundaried plane graph $H$ given by a plane embedding of $G\langle C\rangle$;
we begin with an arbitrary embedding. We can describe modifications to the
graph $G$ by modifications to $H$ as every vertex or edge in $H$ represents a
vertex or edge in $G$. To make the arguments clear, we avoid modifying
vertices from $\partial(H)$ or edges incident to $\partial(H)$, so no such
modification to $H$ affects other parts of the graph $G$ outside $C$.

In order to replace $H$ with a smaller boundaried graph $H^{\prime}$, which
approximately preserves its structure, we are going to reduce the task to the
case where the vertices of $\partial(H)$ are embedded in a convenient way. In
particular, we are interested in the case there $\partial(H)$ is located on a
single face of $H$. As a step in this direction, we first reduce the radial
diameter of $H$ to $k^{\mathcal{O}(1)}$. One obstacle towards this is given by
the existence of a large subset $X\subseteq V(H)\setminus\partial(H)$, with a
small (constant) boundary, that separates some vertices from $\partial(H)$ in
$H$. We are going to compress such subsets using the technique of protrusion
replacement. This technique will also come in useful in the final part of the
proof.

###  6.1 Protrusion replacement

An $r$-protrusion in a graph $G$ is a vertex set $X\subseteq V(G)$, such that
$|\partial_{G}(X)|\leq r$ and $\text{tw}(G[X])\leq r$. For a vertex set
$X\subseteq V(G)$ with $|\partial_{G}(X)|=r$, a bijection
$\lambda\colon[r]\to\partial_{G}(X)$, and a labeled $r$-boundaried graph $H$,
the act of replacing $X$ by $H$ through $\lambda$ means (1) creating labeled
$r$-boundaried graphs $H^{X}=(G[X],\partial_{G}(X),\lambda)$,
$H^{V(G)\setminus X}=(G[(V(G)\setminus
X)\cup\partial_{G}(X)],\partial_{G}(X),\lambda)$, and (2) replacing
$G=H^{V(G)\setminus X}\oplus H^{X}$ by $G^{\prime}=H^{V(G)\setminus X}\oplus
H$. The graph $H^{X}$ is introduced above only for the sake of giving a more
detailed view on the process. We say that $G^{\prime}$ is obtained from $G$ by
replacing a set $X\subseteq V(G)$ if there exist $H,\lambda$ so that $X$ is
replaced by $H$ through $\lambda$.

The standard protrusion replacement technique [BFL+16, FLMS12] is aimed at
reducing large $r$-protrusions, where $r=\mathcal{O}(1)$, while preserving the
optimum value of the instance for the considered optimization problem. Since
we want to perform lifting of a potentially non-optimal solution, we use the
lossless variant of the technique which provides us with such a mechanism. The
definition below can be instantiated for any min-CMSO (or max-CMSO) vertex
subset problem $\Pi$. In such a problem we are given a graph $G$ and the
objective is to find a set $S\subseteq V(G)$ minimizing $|S|$ such that the
predicate $P_{\Pi}(G,S)$, expressible in Counting Monadic Second-Order (CMSO)
logic, is satisfied. For our purposes it is only relevant that this definition
captures the Vertex planarization problem. We specify the labeling $\lambda$
directly in the definition whereas the formulation in [FLMS20] assumes an
implicit labeling on the boundary of $X$.

######  Definition 6.1 (Lossless Protrusion Replacer [FLMS12, FLMS20]).

A lossless protrusion replacer for a min-CMSO vertex subset problem $\Pi$ is a
family of algorithms, with one algorithm for every constant $r$. The $r$-th
algorithm has the following specifications. There exists a constant
$\gamma(r)$ such that given an instance $G$ and an $r$-protrusion $X$ in $G$
containing at least $\gamma(r)$ vertices, $|\partial_{G}(X)|=r^{\prime}\leq
r$, the algorithm runs in polynomial time and outputs an instance $G^{\prime}$
with the following properties.

  * •

$G^{\prime}$ is obtained from $G$ by replacing $(G[X],\partial_{G}(X))$ by a
labeled $r^{\prime}$-boundaried graph $H$ with less than $\gamma(r)$ vertices,
through some labeling $\lambda\colon[r^{\prime}]\to\partial_{G}(X)$, and thus
$V(G^{\prime})<V(G)$.

  * •

$\mathsf{OPT}(G^{\prime})\leq\mathsf{OPT}(G)$.

  * •

There is an algorithm that runs in polynomial time and, given a feasible
solution $S^{\prime}$ to $G^{\prime}$, outputs a set $X^{*}\subseteq X$ such
that $S=(S^{\prime}\setminus V(H))\cup X^{*}$ is a feasible solution to $G$
and $|S|\leq|S^{\prime}|+\mathsf{OPT}(G)-\mathsf{OPT}(G^{\prime})$.

In the original statement, the lossless protrusion replacer is defined to run
in time $O(|X|)$. This is important if we aim at optimizing the running time
of the algorithm but requires some care with specifying the data structures
for maintaining the decomposition into $r$-protrusion. For the sake of keeping
the presentation simple, we have chosen a weaker specification with just a
polynomial running time guarantee.

######  Lemma 6.2.

The Vertex planarization problem admits a lossless protrusion replacer.
Moreover, the choice of the replacement $H$ and the transposition value
$\mathrm{mvp}(G)-\mathrm{mvp}(G^{\prime})$ depends only on the labeled
boundaried graph $(G[X],\partial_{G}(X),\lambda)$.

###### Proof.

The Vertex planarization problem is a special case of $\mathcal{F}$-Minor
Deletion for the family of forbidden minors $\mathcal{F}=\\{K_{5},K_{3,3}\\}$.
Fomin et al. [FLMS12, FLMS20] have shown that every min-CMSO vertex subset
problem $\Pi$ that is strongly monotone admits a lossless protrusion replacer.
Without going into details, both conditions hold for $\mathcal{F}$-Minor
Deletion for every family $\mathcal{F}$ composed of connected graphs [BFL+16,
Lem. 8.4]. We remark that the proof of the strong monotonicity property in
[BFL+16] is formulated for the case where the family $\mathcal{F}$ contains at
least one planar graph, but this condition is not used in this particular
proof. Finally, by examining the proof of [FLMS20, Thm. 9] it follows that the
choice of the replacement $H$ and the transposition value
$\mathsf{OPT}(G)-\mathsf{OPT}(G^{\prime})=\mathrm{mvp}(G)-\mathrm{mvp}(G^{\prime})$
depends only on the labeled boundaried graph $(G[X],\partial_{G}(X),\lambda)$
and is indifferent to the structure of $G-X$. ∎

In our applications, we need to replace a vertex set $X\subseteq V(G)$, such
that $G[X]$ is planar and $|\partial_{G}(X)|\leq r$ for constant $r$, but the
treewidth of $G[X]$ is not necessarily bounded. It is easy to show that for
any minimum planar modulator $S$ it holds that $|S\cap X|\leq r$, as otherwise
the solution $(S\setminus X)\cup\partial_{G}(X)$ would be smaller. By an
argument based on grid minors, if $\mathrm{tw}(G[X])$ is larger than some
function of $r$, then $X$ contains a vertex irrelevant for minimum solutions.
As we work with solutions which are not necessarily optimal, we need an
additional argument that allows us to assume that $|S\cap X|\leq r$.

######  Definition 6.3.

We say that a planar modulator $S$ in $G$ is $r$-locally optimal if there are
no sets $S^{\prime}\subseteq S$ and $S^{*}\subseteq V(G)\setminus S$ such that
$|S^{\prime}|>r$, $|S^{*}|\leq r$, and $(S\setminus S^{\prime})\cup S^{*}$ is
also a planar modulator.

######  Lemma 6.4.

Given an $n$-vertex graph $G$ with a planar modulator $S\subseteq V(G)$, and
an integer $r$, one can find, in time $n^{\mathcal{O}(r)}$, an $r$-locally
optimal planar modulator $\widehat{S}$ of size at most $|S|$.

###### Proof.

Suppose that $S$ is not $r$-locally optimal, so there are sets
$S^{\prime}\subseteq S$ and $S^{*}\subseteq V(G)\setminus S$ such that
$|S^{\prime}|>r$, $|S^{*}|\leq r$, and $(S\setminus S^{\prime})\cup S^{*}$ is
also a planar modulator. Let $S^{\prime\prime}$ be an arbitrary subset of
$S^{\prime}$ of size $r+1$. Then $(S\setminus S^{\prime\prime})\cup S^{*}$ is
a superset of $(S\setminus S^{\prime})\cup S^{*}$, so it is also a planar
modulator, and it is smaller than $S$. The algorithm checks all
$\mathcal{O}(n^{r+1})$ candidates for $S^{\prime\prime}$, and all
$\mathcal{O}(rn^{r})$ candidates for $S^{*}$. If for any pair
$(S^{\prime\prime},S^{*})$, the set $(S\setminus S^{\prime\prime})\cup S^{*}$
is also a planar modulator (this can be checked in time $\mathcal{O}(n+m)$
[HT74]), we set $S\leftarrow(S\setminus S^{\prime\prime})\cup S^{*}$ and
repeat the algorithm. In every step we decrease the size of $S$, so after at
most $n$ steps the process must terminate. Since at this moment we cannot find
any pair $(S^{\prime\prime},S^{*})$ that would provide further refinement, the
obtained planar modulator must be $r$-locally optimal. ∎

Consider a set $X=G\langle A\rangle$ for some $A$, for which $|N_{G}(A)|\leq
r$. The lifting algorithm can use Lemma 6.4 to find a solution $S$ satisfying
$|S\cap X|\leq r$. Therefore any vertex $v\in X$ which can be surrounded by
$r+3$ connected $(v,\partial_{G}(X))$ separators is irrelevant for $S$. We
follow the standard argument based on a grid contraction to find such a vertex
whenever $\mathrm{tw}(G[X])$ is large.

######  Lemma 6.5.

Let $G$ be a graph, $A\subseteq V(G)$, and $G\langle A\rangle$ be a $(\leq
r)$-boundaried connected planar graph. If $\text{tw}(G\langle
A\rangle)>27(2r+7)(r+1)$, then there exists a vertex $v\in A$ and a sequence
of $r+3$ connected pairwise-disjoint $(v,N_{G}(A))$-separators in $G\langle
A\rangle$. Such a vertex $v$ can be found in polynomial time, when given $G$
and $A$. Furthermore, given $G,A,v$, and a planar modulator $S$ in $G-v$, one
can find, in time $n^{\mathcal{O}(r)}$, a planar modulator in $G$ of size at
most $|S|$.

###### Proof.

We apply Proposition 4.10 for $t=(2r+7)(r+1)$. As the treewidth of $G\langle
A\rangle$ is larger than $27\cdot t$, we can find, in polynomial time, a
contraction model of $\Gamma_{t}$ in $G\langle A\rangle$. We have
$(r+1)^{2}>r$ trivially, so this contraction model contains a
$(2r+7)\times(2r+7)$-subgrid without vertices from $N_{G}(A)$. A
$(2r+7)\times(2r+7)$-subgrid contains $r+3$ nested connected separators
$S^{\prime}_{1},\dots,S^{\prime}_{r+3}$ between the central branch set and the
rest of the grid. Let $v$ be any vertex from the central branch set of this
subgrid and $S_{i}$ be the union of vertices contracted into $S^{\prime}_{i}$
for $i\in[r+3]$. By 4.2, the sets $S_{1},\dots,S_{r+3}$ are nested connected
$(v,N_{G}(A))$-separators. Therefore each set $S_{i}$, $i\in[r+3]$, is
$v$-planarizing.

Suppose now that one is given a planar modulator $S$ in $G-v$. By Lemma 6.4,
one can find, in time $n^{\mathcal{O}(r)}$, an $r$-locally optimal planar
modulator $S^{\prime}$ in $G-v$ of size at most $|S|$. Observe that
$|S^{\prime}\cap A|\leq r$ because otherwise $(S^{\prime}\setminus A)\cup
N_{G}(A)$ would be a smaller planar modulator, contradicting $S^{\prime}$
being $r$-locally optimal. Therefore there exists distinct indices
$i_{1},i_{2},i_{3}\in[r+3]$ such that $S_{i_{1}},S_{i_{2}},S_{i_{3}}$ are
disjoint from $S^{\prime}$. For each $j\in[3]$ we have that
$R_{G-S^{\prime}}[v,S_{i_{j}}]\subseteq A$ induces a planar subgraph of
$G-S^{\prime}$. By the assumption $G-S^{\prime}-v$ is planar, so together, by
Lemma 3.17, $G-S^{\prime}$ is planar. We have thus shown how to efficiently
turn a planar modulator in $G-v$ into a planar modulator in $G$. ∎

Once we are able to reduce the treewidth of a planar subgraph with a small
(constant) boundary, we can use protrusion replacement to reduce its size. The
setting in which we work implies some convenient corollaries about the result
of the replacement act, of which we make note in the following lemma.

######  Lemma 6.6.

Let $\gamma$ be the function from Definition 6.1 for the Vertex planarization
problem, $r$ be a constant and $r^{\prime}=27(2r+7)(r+1)$. There is a
polynomial-time algorithm that, given an $n$-vertex graph $G$, a vertex set
$A\subseteq V(G)$, such that $G\langle A\rangle$ is planar and connected,
$N_{G}(A)=r$ and $|A|\geq\gamma(r^{\prime})$, outputs a graph $G^{\prime}$ so
the following hold.

  1. 1.

$G^{\prime}$ is obtained from $G$ by replacing $N_{G}[A]$ with some labeled
$r$-boundaried graph $H$ through some bijection $\lambda\colon[r]\to
N_{G}(A)$.

  2. 2.

$H$ has less than $\gamma(r^{\prime})$ vertices.

  3. 3.

$\mathrm{mvp}(G^{\prime})=\mathrm{mvp}(G)$.

  4. 4.

For any vertex set $X\subseteq V(G)\setminus N_{G}[A]$, if $G-X$ is planar and
connected then $G^{\prime}-X$ is planar and connected.

  5. 5.

Given $G,G^{\prime}$ and a planar modulator $S^{\prime}$ in $G^{\prime}$ one
can, in time $n^{\mathcal{O}(r)}$, turn it into a planar modulator in $G$ of
size at most $|S^{\prime}|$.

###### Proof.

First, we reduce the treewidth of $G\langle A\rangle$ to be at most
$r^{\prime}$ using Lemma 6.5. While $\mathrm{tw}(G\langle
A\rangle)>r^{\prime}$, we can find a vertex $v\in A$ such that any planar
modulator $S$ in $G-v$ can be turned, in time $n^{\mathcal{O}(r)}$, into a
planar modulator in $G$ of size at most $|S|$. Hence, removing $v$ is safe and
we can continue the process on the graph $G-v$. Furthermore, there is at least
one connected restricted $(v,N_{G}(A))$-separator in $G\langle A\rangle$ so
removal of $v$ does not disconnect any vertices from $N_{G}(A)$ within
$G\langle A\rangle$. If some vertices get disconnected from $N_{G}(A)$ then
they form a planar connected component in $G$, which can be discarded.
Therefore, we maintain connectivity of the graph $G\langle A\rangle$. Let
$G_{0}$ be obtained from $G$ after the exhaustive application of Lemma 6.5 and
$A_{0}\subseteq A$ be obtained from $A$ by removing the irrelevant vertices.
Then the set $N_{G_{0}}[A_{0}]$ forms an $r^{\prime}$-protrusion. We can treat
$G_{0}$ as obtained from $G$ by replacing $A$. Note that
$\mathrm{mvp}(G_{0})=\mathrm{mvp}(G)$ because the lifting algorithm can lift
any solution losslessly. If $|N_{G_{0}}[A_{0}]|<\gamma(r^{\prime})$, then we
are done.

Suppose that $|N_{G_{0}}[A_{0}]|\geq\gamma(r^{\prime})$. By Lemma 6.2, the
Vertex planarization problem admits a lossless protrusion replacer, so we can
replace $N_{G_{0}}[A_{0}]$ with a labeled $r$-boundaried graph $H$, with at
most $\gamma(r^{\prime})$ vertices, through some labeling $\lambda$, obtaining
a graph $G^{\prime}$. From the definition of a lossless protrusion replacer we
have that $\mathrm{mvp}(G^{\prime})\leq\mathrm{mvp}(G_{0})=\mathrm{mvp}(G)$
and any planar modulator $S^{\prime}$ in $G^{\prime}$ can be turned, in
polynomial time, into a planar modulator $S_{0}$ in $G_{0}$ of size at most
$|S^{\prime}|+\mathrm{mvp}(G_{0})-\mathrm{mvp}(G^{\prime})$. Thanks to Lemma
6.5, we can compute a planar modulator $S$ in $G$ of size at most $|S_{0}|$,
in time $n^{\mathcal{O}(r)}$.

We argue that actually $\mathrm{mvp}(G^{\prime})=\mathrm{mvp}(G_{0})$. From
Lemma 6.2 we know that the choice of the replacement $H$ and the transposition
value $\mathrm{mvp}(G_{0})-\mathrm{mvp}(G^{\prime})$ depends only on the
boundaried graph
$G_{0}^{A_{0},\lambda}=(G_{0}[N_{G_{0}}[A_{0}]],N_{G_{0}}(A_{0}),\lambda)$.
Let $I_{r}$ be a labeled $r$-boundaried graph with only the boundary vertices
and no edges. Consider graphs $J_{0},J^{\prime}$ obtained by gluing $I_{r}$ to
respectively $G_{0}^{A_{0},\lambda}$ and $H$ (equivalently, one can regard
this operation as taking the underlying non-boundaried graphs). The graph
$J_{0}$ is planar so $\mathrm{mvp}(J_{0})=0$. Because
$\mathrm{mvp}(J^{\prime})\leq\mathrm{mvp}(J_{0})$ we get that
$\mathrm{mvp}(J^{\prime})=\mathrm{mvp}(J_{0})$. Since the transposition value
depends only on $G_{0}^{A_{0},\lambda}$ we infer that
$\mathrm{mvp}(G_{0})-\mathrm{mvp}(G^{\prime})=\mathrm{mvp}(J_{0})-\mathrm{mvp}(J^{\prime})=0$.
If the graph $H$ contains a connected component disconnected from
$\partial(H)$ then the argument above implies that this component must be
planar. Therefore if such a component appears, it can be safely removed as a
planar component in $G_{0}$.

Finally we show that for any vertex set $X\subseteq V(G)\setminus N_{G}[A]$,
if $G-X$ is planar and connected then $G^{\prime}-X$ is planar and connected.
The first modification step does not affect these conditions so $G_{0}-X$ is
planar and connected. Let $J_{0}^{X}$ be the labeled boundaried graph for
which it holds $G_{0}-X=J_{0}^{X}\oplus G_{0}^{A_{0},\lambda}$ and
$G^{\prime}-X=J_{0}^{X}\oplus H$. Similarly as before, we use the fact that
the relation between $G_{0}^{A_{0},\lambda}$ and $H$ is indifferent to the
boundaried graph being glued to them. Therefore
$\mathrm{mvp}(G^{\prime}-X)=\mathrm{mvp}(G_{0}-X)=0$, so $G^{\prime}-X$ is
planar. Now suppose that $G^{\prime}-X$ is not connected. Because we have
removed all the connected components of $H$ with empty intersection with
$\partial(H)$, this means that there exist $u,v\in
N_{G_{0}}(A_{0})=\partial(H)$ which are connected in $G_{0}\langle
A_{0}\rangle$ but not in $H$. Let $\widehat{K_{5}}$ denote the graph $K_{5}$
with one edge removed. Consider graphs $R_{0},R^{\prime}$ obtained by gluing
$\widehat{K_{5}}$ to respectively $G_{0}^{A_{0},\lambda}$ and $H$ so that the
vertices $u,v$ are glued to the non-adjacent pair in $\widehat{K_{5}}$. Since
there is a $(u,v)$-path in $G\langle A\rangle$, the graph $R_{0}$ contains
$K_{5}$ as a minor. On the other hand, $u,v$ belong to different connected
components of $H$, so every biconnected component of $R^{\prime}$ is planar
and so $R^{\prime}$ is planar. We get that
$\mathrm{mvp}(R_{0})>\mathrm{mvp}(R^{\prime})=0$, which contradicts the
assumption that such vertices $u,v$ exist. The claim follows. ∎

###  6.2 Outerplanar decomposition

In order to conveniently analyze plane graphs with large radial diameter we
take advantage of the concept of a decomposition into outerplanarity layers
used by Jansen et al. [JPvL19] in their work on kernelization for Multiway cut
on planar graphs. We refer to the definitions from the full version [JPvL18]
of this article.

######  Definition 6.7 ([JPvL18, Definition 5.1]).

Let $G$ be a plane graph. The outerplanarity layers of $G$ form a partition of
$V(G)$ into $L_{1},\ldots,L_{m}$ defined recursively. The vertices incident
with the outer face of $G$ belong to layer $L_{1}$. If $v\in V(G)$ lies on the
outer face of the plane subgraph obtained from $G$ by removing
$L_{1},\ldots,L_{i}$, then $v$ belongs to layer $L_{i+1}$. For a vertex $v\in
V(G)$, the unique index $i\in[m]$ for which $v\in L_{i}$ is the
_outerplanarity index_ of $v$ and denoted $\mathrm{\textsc{idx}}_{G}(v)$.

A plane graph is $k$-outerplanar if this process partitions it into exactly
$k$ non-empty layers. A graph is $k$-outerplanar if it admits a
$k$-outerplanar embedding.

######  Definition 6.8 ([JPvL18, Definition 5.2]).

For a plane graph $G$, let $T$ be the simple graph obtained by simultaneously
contracting all edges $uv$ whose endpoints belong to the same outerplanarity
layer, discarding loops and parallel edges. For a node $u\in V(T)$, let
$\kappa(u)\subseteq V(G)$ denote the vertex set of $G$ whose contraction
resulted in $u$. Let $\mathrm{\textsc{idx}}_{G}(u)$ denote the outerplanarity
index that is shared by all nodes in $\kappa(u)$.

We make note of several properties of this definition.

######  Lemma 6.9 ([JPvL18, Lemma 5.3]).

For a connected plane graph $G$ and its outerplanar decomposition $(T,\kappa)$
based on the outerplanarity layers $L_{1},\ldots,L_{m}$, the following holds:

  1. 1.

$T$ is a tree.

  2. 2.

For any node $u\in V(T)$, the graph $G[\kappa(u)]$ is connected.

  3. 3.

If $x,y$ are distinct vertices of $T$, then for any internal node $z$ of the
unique $(x,y)$-path in $T$, the set $\kappa(z)$ is a restricted
$(\kappa(x),\kappa(y))$-separator in $G$.

  4. 4.

There is a unique node $x_{1}\in V(T)$ such that $\kappa(x_{1})=L_{1}$.

  5. 5.

Root $T$ at vertex $x_{1}$. If $u\in V(T)$ is a child of $p\in V(T)$, then
$\mathrm{\textsc{idx}}_{G}(u)=1+\mathrm{\textsc{idx}}_{G}(p)$.

We call the pair $(T,\kappa)$, where $T$ is the tree rooted at $x_{1}$
accordingly to Lemma 6.9, the _outerplanar decomposition_ of $G$. Note that it
is uniquely defined for a given connected plane graph $G$. Let $\delta_{T}$
denote the shortest path distance on the tree $T$. For distinct $x,y\in V(T)$
we define $T^{P}_{x,y}$ to be the unique $(x,y)$-path in $T$ and for non-
adjacent $x,y\in V(T)$ we define $T_{x,y}$ to be the connected component of
$T-\\{x,y\\}$ containing the internal vertices of $T^{P}_{x,y}$. For a subtree
$T^{\prime}$ of $T$ we use the notation $\kappa(T^{\prime})$ to denote the
union of $\\{\kappa(t)\mid t\in V(T^{\prime})\\}$. Note that
$N_{G}(\kappa(T_{x,y}))\subseteq\kappa(x)\cup\kappa(y)$.

######  Observation 6.10 ([JPvL18, Observation 5.4]).

Let $G$ be a connected plane graph and $(T,\kappa)$ be its outerplanar
decomposition. If $u,v\in V(G)$ share a face, then either there is $x\in V(T)$
such that $u,v\in\kappa(x)$ or there are $x,y\in V(T)$ which are adjacent in
$T$ and $u\in\kappa(x),v\in\kappa(y)$. Conversely, if $x$ is a child of $y$ in
$T$ and $v\in\kappa(x)$, then there exists $u\in\kappa(y)$, so that $u,v$
share a face.

This observation allows us to make a link between the depth of the outerplanar
decomposition and the radial diameter of the graph. We define the depth of a
rooted tree as the longest root-leaf distance plus 1 (so a singleton tree has
depth 1).

######  Lemma 6.11.

Let $G$ be a connected plane graph and $(T,\kappa)$ be its outerplanar
decomposition. If the maximal depth in $T$ is $d$, then the radial diameter of
$G$ is at most $2d-1$.

###### Proof.

By 6.10 any vertex in $L_{i+1}$ shares a face with a vertex from $L_{i}$. Let
$u,v\in V(G)$ be any pair of vertices. We have
$\mathrm{\textsc{idx}}_{G}(u),\mathrm{\textsc{idx}}_{G}(v)\leq d$ so they are
at radial distance at most $d-1$ from some vertices from $L_{1}$ which are at
radial distance 1, hence $d_{G}(u,v)\leq 2d-1$. ∎

Since $T$ is a contraction of $G$, when a set $S\subseteq V(G)$ separates
$\kappa(x)$ from $\kappa(y)$, it also separates $\kappa(x)$ from the image of
the entire subtree behind $y$. We make note of this observation for the case
where we separate $\kappa(x)$ from two directions at once.

######  Observation 6.12.

Let $G$ be a connected plane graph and $(T,\kappa)$ be its outerplanar
decomposition. Let $x,y,z\in V(T)$ be distinct pairwise non-adjacent vertices
such that $z$ lies on the unique $(x,y)$-path in $T$. Suppose that $S\subseteq
V(G)$ is a restricted $(\kappa(z),\kappa(x)\cup\kappa(y))$-separator. Then the
connected component of $G-S$ containing $\kappa(z)$ is contained in
$\kappa(T_{x,y})$.

We also state a strengthening of Lemma 6.9(3) which says that the separators
within outerplanarity layers are in fact cycles.

######  Observation 6.13.

Let $G$ be a connected plane graph, $(T,\kappa)$ be its outerplanar
decomposition, and $x,y,z\in V(T)$ be distinct. If $z$ lies on the unique
$(x,y)$-path in $T$, then there is a cycle $C$ in $G$ such that
$V(C)\subseteq\kappa(z)$ and one of $\kappa(x),\kappa(y)$ lies entirely in the
interior of $C$ and the other one in the exterior of $C$.

###  6.3 Outerplanarity layers and vertex-disjoint paths

We will be working with an outerplanar decomposition $(T,\kappa)$ of a plane
graph $G$ and families of internally vertex-disjoint paths connecting two
outerplanarity layers, so that one is drawn inside the other one. First we
show that paths in such a family can be assumed to cross each intermediate
outerplanarity layer only once.

######  Lemma 6.14.

Let $G$ be a connected plane graph, $L_{1}$ be the set of vertices lying on
the outer face of $G$, and $F\subseteq V(G)\setminus L_{1}$ induce a connected
subgraph of $G$. Suppose that $u,v\in L_{1}$ are non-adjacent and connected by
a path $P$ with all its internal vertices disjoint from $(L_{1}\cup F)$. Then
there exists a $(u,v)$-path $P^{\prime}$ such that $V(P^{\prime})\subseteq
L_{1}$ and the internal vertices of $P^{\prime}$ belong to a connected
component of $G-V(P)$ which is disjoint from $F$.

###### Proof.

As $u,v$ are non-adjacent, the interior of $P$ is non-empty. Since $G[L_{1}]$
is connected, there is a $(u,v)$-path within $L_{1}$, which is internally
disjoint from $P$. Therefore $u,v$ belong to a common biconnected component
$B$ of $G$ and the subgraph $B$ contains a cycle $C_{1}$ such that
$V(C_{1})=L_{1}\cap V(B)$. Removing non-adjacent $u,v$ from $C_{1}$ separates
$V(C_{1})$ into two non-empty sets $S^{1},S^{2}$, which end up in different
connected components of $G-V(P)$ since $u$ and $v$ lie on the outer face.
Since $G[F]$ is connected, it is fully contained in one such component. We can
thus use either $S^{1}$ or $S^{2}$ to make the desired path $P^{\prime}$. ∎

For a path $P$ and a vertex set $X$, a segment of $P$ in $X$ is an inclusion-
wise maximal subpath $P^{\prime}$ of $P$ such that $V(P^{\prime})\subseteq X$.
We define $S(P,X)$ to be the set of segments of $P$ in $X$.

######  Lemma 6.15.

Consider a connected plane graph $G$, its outerplanar decomposition
$(T,\kappa)$, and non-adjacent $x,y\in V(T)$ such that $x$ is an ancestor of
$y$. Suppose we are given a family of internally vertex-disjoint
$(\kappa(x),\kappa(y))$-paths $\mathcal{P}$. Then we can compute, in
polynomial time, a family $\mathcal{P}^{\prime}$ of internally vertex-disjoint
$(\kappa(x),\kappa(y))$-paths such that $|\mathcal{P}^{\prime}|=|\mathcal{P}|$
and for each $P\in\mathcal{P}^{\prime}$ and $z\in T^{P}_{x,y}$ it holds that
$|S(P,\kappa(z))|=1$.

###### Proof.

By replacing each $P\in\mathcal{P}$ by the $(\kappa(x),\kappa(y))$-subpath
between the last visit to $\kappa(x)$ and the first visit to $\kappa(y)$, we
can assume that the internal vertices of the paths in $\mathcal{P}$ belong to
$\kappa(T_{x,y})$. For a family of internally vertex-disjoint
$\kappa(x),\kappa(y)$-paths $\mathcal{P}$ we define the measure
$\mu(\mathcal{P})=\sum_{P\in\mathcal{P}}\sum_{z\in
T^{P}_{x,y}}|S(P,\kappa(z))|$. While $\mathcal{P}$ does not satisfy the claim,
we are going to refine some path from $\mathcal{P}$ to decrease the measure
$\mu(\mathcal{P})$.

Let $x^{\prime}\in V(T)$ be the vertex on $T^{P}_{x,y}$ which is closest to
$x$ among those for which there exists a path $P\in\mathcal{P}$ so that
$|S(P,\kappa(x^{\prime}))|>1$. Note that $x^{\prime}$ is an ancestor of $y$.
Let us consider a plane graph $G^{\prime}$ obtained by removing from $G$ all
the vertices from $\kappa(z)$ over all $z\in V(T)$ outside the subtree of $T$
rooted at $x^{\prime}$. Note that $G^{\prime}$ is connected and
$\kappa(x^{\prime})$ is the set of vertices lying on the outer face of
$G^{\prime}$. By the choice of $x^{\prime}$, for each $P\in\mathcal{P}$ there
is exactly one segment of $P$ in $V(G^{\prime})$: otherwise some path would
have multiple segments in $\kappa(x^{\prime\prime})$, for $x^{\prime\prime}$
being a parent of $x^{\prime}$, which is a superset of $N_{G}(V(G^{\prime}))$.
Let $P^{\prime}$ denote this segment of $P$.

Let $P\in\mathcal{P}$ be a path for which $|S(P,\kappa(x^{\prime})|>1$. Then
there exist vertices $u,v\in V(P^{\prime})\cap\kappa(x^{\prime})$ and a
$(u,v)$-subpath $P_{u,v}$ of $P^{\prime}$ whose internal vertices do not
belong to $\kappa(x^{\prime})$. If $u,v$ are adjacent, then we can shortcut
$P$ by replacing $P_{u,v}$ with the edge $(u,v)$ thus decreasing
$\mu(\mathcal{P})$. Suppose that $u,v$ are non-adjacent. We apply Lemma 6.14
to the graph $G^{\prime}$ with the outer face lying on $\kappa(x^{\prime})$,
vertices $u,v$, path $P_{u,v}$, and $F=\kappa(y)$, which induces a connected
subgraph of $G^{\prime}$. We obtain a $(u,v)$-path $P^{\prime}_{u,v}$ such
that $V(P^{\prime}_{u,v})\subseteq\kappa(x^{\prime})$ and the internal
vertices of $P^{\prime}_{u,v}$ belong to a connected component of
$G^{\prime}-V(P_{u,v})$ which is disjoint from $\kappa(y)$. Since all the
other paths from $\\{P^{\prime}\mid P\in\mathcal{P}\\}$ connect
$\kappa(x^{\prime})$ to $\kappa(y)$ in $G^{\prime}$, they cannot have any
vertices in this component of $G^{\prime}-V(P_{u,v})$. Therefore by replacing
$P_{u,v}$ with $P^{\prime}_{u,v}$ in $P$ we obtain a new family of internally
vertex-disjoint $(\kappa(x),\kappa(y))$-paths of the same size for which the
measure $\mu$ is lower than $\mu(\mathcal{P})$.

We apply this refinement exhaustively as long as there exist $P\in\mathcal{P}$
and $z\in T^{P}_{x,y}$ with $|S(P,\kappa(z))|>1$. It is clear that the
refinement step can be performed in polynomial time. At each step the value of
$\mu$ decreases so at some point the process terminates and gives the desired
path family. ∎

It is important that the sets considered in Lemma 6.15 are given by the
consecutive outerplanarity layers. For other choice of connected separators,
such a claim might not be true.

By inspecting the outerplanar decomposition $(T,\kappa)$ of an $r$-boundaried
plane graph $H$, we can find the set of nodes in $T$ whose images cover the
boundary $\partial(H)$, and then mark the LCA closure of this set (recall
Definition 3.8), thus marking at most $2r$ nodes. We consider the nodes which
were not marked and we want to compress the graph whenever there is a long
path of non-marked nodes. This translates to a situation where one group
$T_{1}$ of relevant vertices (that is, located in a marked bag) lies on one
outerplanarity layer, there is a deep well of nested outerplanarity layers,
and another group $T_{2}$ of relevant vertices is located inside the well. We
want to say that only the $\mathcal{O}(k)$ layers closest to $T_{1}$ and
$\mathcal{O}(k)$ layers closest to $T_{2}$ are important and the middle layers
can be compressed.

Let $S$ be some solution and suppose that there at least 4 internally vertex-
disjoint $(T_{1},T_{2})$-paths in $H-S$. We need an argument that in this
case, for any vertex $v$ in the middle layers that does not lie on any of
these four paths, we can draw two vertex-disjoint cycles around $v$ that
separate $v$ from all the relevant vertices, and in particular from
$\partial(H)$. We begin with a topological argument that such cycles exist. We
do not rely on Lemma 6.15 and give the argument in a general form.

######  Lemma 6.16.

Let $G$ be a plane graph, $C_{1},\dots,C_{6}$ be vertex-disjoint cycles in
$G$, so that $C_{i+1}$ is drawn inside $C_{i}$ for $i\in[5]$, and let
$P_{A},P_{B},P_{C},P_{D}$ be vertex-disjoint $(C_{1},C_{6})$-paths. Suppose
that a vertex $v\in V(G)$ with $v\not\in\bigcup_{i\in[4]}V(P_{i})$ lies in the
intersection of the proper interior of $C_{3}$ and the proper exterior of
$C_{4}$. Then there exist two vertex-disjoint cycles in $G$ which are nested
with respect to $v$ and separate $v$ from $V(C_{1})\cup V(C_{6})$.

###### Proof.

Without loss of generality, by shortcutting the paths if needed, we may assume
that the paths $P_{A},\ldots,P_{D}$ do not contain any vertex from
$V(C_{1})\cup V(C_{6})$ in their interior.

For subsets of indices $I\subseteq[6]$ and $J\subseteq\\{A,B,C,D\\}$, let
$G^{J}_{I}$ be the plane subgraph of $G$ obtained by restricting the drawing
of $G$ to only the vertices and edges which lie on a cycle $C_{i}$ with $i\in
I$ or a path $P_{X}$ with $X\in J$. For ease of presentation, we abbreviate
$\\{A,B,C,D\\}$ by $[D]$.

Since $v$ does not lie on any of the four paths, while it lies in the
intersection of the proper interior of $C_{3}$ and proper exterior of $C_{4}$,
it follows that the image of $v$ does not intersect the drawing of
$G_{3,4}^{[D]}$. Let $F_{3,4}^{[D]}$ denote the face of $G_{3,4}^{[D]}$
containing the image of $v$. The face $F_{3,4}^{[D]}$ is bounded since
$G_{3,4}^{[D]}$ contains $C_{3}$ which has $v$ in its proper interior, and due
to the nesting of the cycles no vertex on $F_{3,4}^{[D]}$ belongs to $C_{5}$
or $C_{6}$. Similarly, since $v$ lies in the proper exterior of $C_{4}$, face
$F_{3,4}^{[D]}$ does not contain any vertex of $C_{1}$ or $C_{2}$. Since
$G_{3,4}^{[D]}$ is a connected graph that does not have any articulation
points, the boundary of face $F_{3,4}^{[D]}$ is a simple cycle $C^{\prime}$
which contains $v$ in its proper interior. As observed above, $C^{\prime}$ is
disjoint from $C_{1}\cup C_{2}\cup C_{5}\cup C_{6}$. Note that since
$G_{3,4}^{[D]}$ contains cycles $C_{3}$ and $C_{4}$, the nesting of the cycles
and placement of $v$ in the interior of $C_{3}$ and exterior of $C_{4}$
ensures that $V(C^{\prime})$ separates $v$ from $V(C_{1})\cup V(C_{6})$.

Figure 3: Schematic representation of the graph $G^{[D]}_{[6]}$. In this
example, the face of $G_{3,4}^{[D]}$ containing $v$ is highlighted with dashed
white lines. Its boundary cycle forms $C^{\prime}$ when applying the lemma for
$v$. It contains segments of $C_{3}$, $C_{4}$, and the single path $P_{B}$.
Additionally, the face of $G_{2,5}^{[A,C]}$ containing $v$ is shaded. It is
bounded by segments of $C_{2}$, $C_{5}$, and the paths $P_{A}$ and $P_{C}$.
Its boundary cycle forms $C^{\prime\prime}$ when applying the lemma for $v$.

From the observations above, we get that $F_{3,4}^{[D]}$ is also a face in
$G_{[6]}^{[D]}$. Suppose that the boundary of $F_{3,4}^{[D]}$ intersects at
least three paths $P_{X},P_{Y},P_{Z}\in\\{P_{A},\ldots,P_{D}\\}$. Note that
one can always add a vertex to a drawing inside some face and make it adjacent
to all vertices on the boundary of this face. Consider a plane graph
$G^{\prime}$ obtained from $G_{[6]}^{[D]}$ by inserting three new vertices
$v_{1},v_{6},v_{F}$ adjacent respectively to all vertices of $C_{1}$, $C_{6}$
and $F_{3,4}^{[D]}$. The sets $V(P_{X}),V(P_{Y}),V(P_{Z})$, $\\{v_{1}\\}$,
$\\{v_{6}\\}$, $\\{v_{F}\\}$ would form a minor model of $K_{3,3}$ which gives
a contradiction. Therefore the boundary of $F_{3,4}^{[D]}$ intersects at most
two paths $P_{X},P_{Y}\in\\{P_{A},\ldots,P_{D}\\}$; see Figure 3 for an
illustration. Note that it is possible that the boundary intersects only a
single path. Let $P_{R},P_{S}$ be two paths not intersecting the boundary of
$F_{3,4}^{[D]}$.

In the graph $G_{2,5}^{R,S}$, the face $F_{2,5}^{R,S}$ containing the image of
$v$ is again bounded. Let $C^{\prime\prime}$ denote the cycle bounding
$F_{2,5}^{R,S}$, which is simple since $G_{2,5}^{R,S}$ is connected and has no
articulation points. By the nesting of the cycles, $C^{\prime\prime}$ is
disjoint from $C_{1}$ and $C_{6}$. By definition of the graph $G_{2,5}^{R,S}$,
the cycle $C^{\prime\prime}$ is disjoint from $V(C_{3})\cup V(C_{4})$, and
therefore $V(C^{\prime})\cap V(C^{\prime\prime})=\emptyset$. Since
$G_{2,5}^{R,S}$ contains cycles $C_{2}$ and $C_{5}$, while the nesting and
placement of $v$ ensures that $v$ is in the proper interior of $C_{2}$ and
proper exterior of $C_{5}$, it follows that $C^{\prime\prime}$ separates $v$
from $V(C_{1})\cup V(C_{6})$. Since both $C^{\prime}$ and $C^{\prime\prime}$
have $v$ in their interior and $C_{1}$ in they exterior, they are nested. This
concludes the proof. ∎

###  6.4 Compressing the outerplanarity layers

We focus on the case where $x,y\in V(T)$ are some marked vertices, $x$ is an
ancestor of $y$ and $T_{x,y}$ contains no marked vertices (and thus its image
contains no boundary vertices). If $\delta_{T}(x,y)$ is large, we want to
preserve just $\mathcal{O}(k)$ outerplanarity layers closest to $\kappa(x)$,
$\mathcal{O}(k)$ layers closest to $\kappa(y)$, and in the middle layers we
want to preserve only the maximal family internally of vertex-disjoint
$(\kappa(x),\kappa(y))$-paths, discarding the remaining vertices and edges.

We need to argue for the backward safeness of such a graph modification.
Consider a solution $S$ such that $|S\cap\kappa(T_{x,y})|\leq k$. If $H-S$
contains at least 4 internally vertex-disjoint $(\kappa(x),\kappa(y))$-paths,
we can surround the modified areas with two cycles using Lemma 6.16 and argue
that inserting them back does not affect planarity. Otherwise we want to say
that $S\cap\kappa(T_{x,y})$ is sufficiently large so we can charge these
vertices to “pay” for additional vertex removals which separate $\kappa(x)$
from $\kappa(y)$ in $H$. The following statement remains correct if we assume
the existence of just 4 internally vertex-disjoint
$(\kappa(x),\kappa(y))$-paths, instead of 6, but with a worse approximation
factor of the lifting algorithm. On the other hand, factor 2 can be improved
to $(1+\varepsilon)$ if we assume that even more paths exist but for the sake
of keeping the presentation clear we do not optimize this constant.

######  Lemma 6.17.

Let $G$ be a graph, $A\subseteq V(G)$, $H$ be a connected boundaried plane
graph given by some plane embedding of $G\langle A\rangle$, $(T,\kappa)$ be
the outerplanar decomposition of $H$, and $k$ be an integer. Consider vertices
$x,y\in V(T)$ such that $x$ is an ancestor of $y$, $\delta_{T}(x,y)>4k+11$,
$\kappa(T_{x,y})\cap\partial(H)=\emptyset$, and there are 6 internally vertex-
disjoint $(\kappa(x),\kappa(y))$-paths in the graph
$H\langle\kappa(T_{x,y})\rangle$. There is a polynomial-time algorithm that,
given all the above, returns a vertex set $V_{D}\subseteq\kappa(T_{x,y})$ and
an edge set $E_{D}\subseteq E_{G}(\kappa(T_{x,y}),\kappa(T_{x,y}))$ so that
the following hold.

  1. 1.

For each vertex $v\in\kappa(y)$ there exists a vertex $u\in\kappa(x)$ so that
the radial distance between $u$ and $v$ in $H^{\prime}=(H\setminus
E_{D})-V_{D}$ is at most $4k+11$.

  2. 2.

The boundaried graph $H^{\prime}=(H\setminus E_{D})-V_{D}$ is connected.

  3. 3.

Given a planar modulator $S^{\prime}$ in $G^{\prime}=(G\setminus
E_{D})-V_{D}$, such that $|S^{\prime}\cap\kappa(T_{x,y})|\leq k$, one can turn
it, in polynomial time, into a planar modulator $S$ in $G$ such that
$|S|\leq|S^{\prime}|+2\cdot|S^{\prime}\cap\kappa(T_{x,y})|$ and
$S\setminus\kappa(T_{x,y})=S^{\prime}\setminus\kappa(T_{x,y})$.

###### Proof.

We set $D=\kappa(T_{x,y})$, $T_{1}=\kappa(x)$, $T_{2}=\kappa(y)$, and $J$ be
the boundaried plane graph given by the subgraph of $H$ induced by $D\cup
T_{1}\cup T_{2}$ and the boundary $T_{1}\cup T_{2}$. Note that
$N_{G}(D)\subseteq T_{1}\cup T_{2}$ and $T_{1},T_{2}$ are non-adjacent. Let
$d$ be the minimum size of a restricted $(T_{1},T_{2})$-separator in $J$. By
Menger’s theorem there exist $d$ internally vertex-disjoint
$(T_{1},T_{2})$-paths in $J$: $P_{1},\dots P_{d}$. By the assumption $d\geq
6$. Furthermore, by Lemma 6.15 we can assume that each path $P_{i}$ has only
one segment in each $\kappa(z)$ for $z\in T^{P}_{x,y}$.

Let $q_{1}\in V(T)$ be the vertex on path $T^{P}_{x,y}$ with distance
$\delta_{T}(x,q_{1})$ exactly $2k+5$. Similarly, $q_{2}\in V(T)$ is the vertex
on path $T^{P}_{x,y}$ with distance $\delta_{T}(y,q_{2})$ exactly $2k+5$. We
define $Q=T_{q_{1},q_{2}}$. By the assumption $Q$ is non-empty. Let
$V_{Q}=\kappa(Q)$; then $V_{Q}$ is a restricted $(T_{1},T_{2})$-separator in
$H$ and also in $J$. We define $E_{D}$ to be the set of edges with at least
one endpoint in $V_{Q}$, which do not belong to any path $P_{i}$ for
$i\in[d]$. The set $V_{D}$ is the set of vertices in $V_{Q}$ which become
isolated in $H\setminus E_{D}$. See Figure 4 for an illustration. Let
$G^{\prime},H^{\prime},J^{\prime}$ denote the graphs obtained respectively
from $G,H,J$ after removing the edges from $E_{D}$ and vertices from $V_{D}$.
We have that $G^{\prime}=G_{\partial}[\overline{A}]\oplus H^{\prime}$. Note
that $H^{\prime}$ is connected and $J^{\prime}$ still admits $d$ internally
vertex-disjoint $(T_{1},T_{2})$-paths.

We will show that any planar modulator $S^{\prime}$ in $G^{\prime}$ with
bounded intersection with $D$ can be lifted to a planar modulator in $G$, by
possibly increasing its size slightly. We consider two cases. First, if
removing vertices from $S^{\prime}\cap D$ preserves at least 4 internally
vertex-disjoint $(T_{1},T_{2})$-paths in $J^{\prime}$, then we show that any
region in which the graph modifications occurred can be surrounded by 2 cycles
separating this region from the boundary of $H$. Then the planarity criterion
can be applied to argue that $S^{\prime}$ remains a planar modulator after
undoing the graph modifications. Otherwise, the set $S^{\prime}\cap D$ is
sufficiently large so we can charge it with adding to $S^{\prime}$ a
restricted $(T_{1},T_{2})$-separator in $J$. Then each leftover connected
component in $J$ is disconnected from either $T_{1}$ or $T_{2}$, which again
allows us to apply the planarity criterion to justify undoing the graph
modifications.

Figure 4: Schematic view of the proof of Lemma 6.17. The orange paths connect
vertices from $T_{1}$ (on the outside) with vertices from $T_{2}$ (inside).
The middle layer corresponds to the area between $\kappa(q_{1})$ and
$\kappa(q_{2})$. The paths can be assumed to cross the middle layer only once
due to Lemma 6.15. All the edges and vertices marked gray in the middle layer
are being removed; these are the sets $E_{D}$ and $V_{D}$.

######  Claim 6.18.

Let $S^{\prime}$ be a planar modulator in $G^{\prime}$ such that
$|S^{\prime}\cap D|\leq k$ and the minimum size of a restricted
$(T_{1},T_{2})$-separator in $J^{\prime}-(S^{\prime}\cap D)$ is at least 4.
Then $S^{\prime}$ is also a planar modulator in $G$.

###### Proof.

By Menger’s theorem, there exist 4 internally vertex-disjoint
$(T_{1},T_{2})$-paths in $J^{\prime}-(S^{\prime}\cap D)$:
$R_{1},R_{2},R_{3},R_{4}$. We will transform the graph $J^{\prime}-S^{\prime}$
back into $J-S^{\prime}$ by undoing the vertex and edge removals so that
$G^{\prime}-S^{\prime}$ is transformed into $G-S^{\prime}$, while maintaining
planarity of the graph. First, inserting an isolated vertex from $V_{D}$ does
not affect planarity of a graph. Now consider a single insertion of an edge
$e\in E_{D}$. If both endpoints of $e$ are disconnected from $(T_{1}\cup
T_{2})\setminus S^{\prime}$ in $J^{\prime\prime}-S^{\prime}$ then this
connected component of $G^{\prime\prime}$ after the modification is contained
in $D$, which induces a planar graph by the assumption (recall that we assumed
that $D\cap\partial(H)=\emptyset$).

Suppose otherwise. Let $v\in V_{Q}\setminus S^{\prime}$ be an endpoint of $e$.
Since $|S^{\prime}|\leq k$, there exist vertices
$q^{\prime}_{1},\dots,q^{\prime}_{6}\in V(T)$ lying on this order on the path
$T^{P}_{x,y}$ such that $q^{\prime}_{1},q^{\prime}_{2},q^{\prime}_{3}$ appear
before $Q$ (counting from $x$) and
$q^{\prime}_{4},q^{\prime}_{5},q^{\prime}_{6}$ appear after $Q$ such that
$\kappa(q^{\prime}_{j})\cap S^{\prime}=\emptyset$ for $j\in[6]$. By 6.13 for
each $j\in[6]$ there is a cycle
$C^{\prime}_{j}\subseteq\kappa(q^{\prime}_{j})$, so that $C^{\prime}_{j+1}$
lies in the interior of $C^{\prime}_{j}$ in $J^{\prime}-S^{\prime}$.
Furthermore, $v$ lies in the intersection of the proper interior of $C_{3}$
and the proper exterior of $C_{4}$ in $J^{\prime}-S^{\prime}$ and each of the
paths $R_{i}$, $i\in[4]$, contains a $(C^{\prime}_{1},C^{\prime}_{6})$-subpath
$R^{\prime}_{i}$ so that these subpaths are vertex-disjoint (not just
internally vertex-disjoint). This setting allows us to apply Lemma 6.16 to
obtain that there exist cycles $C_{1},C_{2}$ in $J^{\prime}-S^{\prime}$ which
are nested with respect to $v$ and separate $v$ from $C^{\prime}_{1}\cup
C^{\prime}_{6}$ and thus from $T_{1}\cup T_{2}$. Therefore
$R_{H^{\prime}-S^{\prime}}[v,C_{i}]\cap\partial(H)=\emptyset$ for $i\in[2]$
and these cycles are $v$-planarizing. By Lemma 3.16 we infer that if
$(G^{\prime}-S^{\prime})\setminus e$ is planar then also
$G^{\prime}-S^{\prime}$ is planar. This allows us to insert back all the edges
from $E_{D}$ into $G^{\prime}-S^{\prime}$ while maintaining the planarity of
the graph and show that $G-S^{\prime}$ is planar. The claim follows. ∎

######  Claim 6.19.

Let $S^{\prime}$ be a planar modulator in $G^{\prime}$ such that
$|S^{\prime}\cap D|\leq k$ and there exists a restricted
$(T_{1},T_{2})$-separator in $J^{\prime}-(S^{\prime}\cap D)$ of size at most
$3$. Let $R$ be a minimum-size restricted $(T_{1},T_{2})$-separator in $J$.
Then $S=S^{\prime}\cup R$ is also a planar modulator in $G$ and
$|S|\leq|S^{\prime}|+2\cdot|S^{\prime}\cap D|$.

###### Proof.

Recall that we have preserved the paths $P_{1},\dots,P_{d}$ during the graph
modification and $J^{\prime}$ still admits $d\geq 6$ internally vertex-
disjoint $(T_{1},T_{2})$-paths. The size of $S^{\prime}\cap D$ is at least
$d-3\geq 3$ because removing one vertex from $D$ can decrease the flow between
$T_{1}$ and $T_{2}$ (which are disjoint from $D$) by at most one. We have
$|R|=d\leq|S^{\prime}\cap D|+3\leq 2\cdot|S^{\prime}\cap D|$ and so
$|S|\leq|S^{\prime}|+|R|\leq|S^{\prime}|+2\cdot|S^{\prime}\cap D|$, as
intended. Also, $|S|\leq|S^{\prime}|+|R|\leq|S^{\prime}|+|S^{\prime}\cap
D|+3\leq 2k+3$. By the definition of $Q$, there exist vertices
$q^{\prime}_{1},q^{\prime}_{2},q^{\prime}_{3},q^{\prime}_{4}\in V(T)$ lying in
this order on the path $T^{P}_{x,y}$ such that $q^{\prime}_{1},q^{\prime}_{2}$
appear before $Q$ (counting from $x$) and $q^{\prime}_{3},q^{\prime}_{4}$
appear after the subpath $Q$ such that $\kappa(q^{\prime}_{j})\cap
S=\emptyset$ for $j\in[4]$.

We will transform the graph $J^{\prime}-S$ back into $J-S$ by undoing the
vertex and edge removals so that $G^{\prime}-S$ is transformed into $G-S$,
while maintaining planarity of the graph. First, inserting an isolated vertex
from $V_{D}$ does not affect planarity of a graph. Now consider a single
insertion of an edge $e\in E_{D}$ and let $J^{\prime\prime},G^{\prime\prime}$
denote the graph obtained respectively from $J^{\prime},G^{\prime}$ after the
insertions done so far, and assume inductively that $S$ is a planar modulator
in $G^{\prime\prime}\setminus e$. We are going to prove that $S$ is a planar
modulator in $G^{\prime\prime}$. If both endpoints of $e$ are disconnected
from $(T_{1}\cup T_{2})\setminus S$ in $J^{\prime\prime}-S$ then this
connected component of $G^{\prime\prime}$ being modified is contained in $D$,
which induces a planar graph by assumption.

Suppose otherwise. Let $v\in V_{Q}$ be an endpoint of $e$. Since $R$ is a
restricted $(T_{1},T_{2})$-separator in $J$ (and so in $J^{\prime\prime}$) and
$R\subseteq S$, $v$ can be connected to at most one of $T_{1},T_{2}$ in
$J^{\prime\prime}-S$. Suppose w.l.o.g. that $v$ is connected to some vertex
from $T_{1}$ in $J^{\prime\prime}-S$ but none from $T_{2}$. By the definition
of $V_{Q}$, every $(T_{1},v)$-path in $J$ must intersect
$\kappa(q^{\prime}_{1})$ and $\kappa(q^{\prime}_{2})$. These sets are disjoint
from $S$ and by 6.13 there are two cycles separating $v$ in $G^{\prime\prime}$
from any vertex from $T_{1}\setminus S$. By Lemma 3.16 we conclude that
$G^{\prime\prime}-S$ is planar. After undoing all the edge deletions we obtain
that $G-S$ is planar. The claim follows. ∎

In the first case we do not change the size of the planar modulator and in the
second case we have $|S|\leq|S^{\prime}|+2\cdot|S^{\prime}\cap D|$. Therefore
the lifting algorithm can turn any solution to $G^{\prime}$ into a solution to
$G$ within the guarantees of the lemma.

Finally, let us examine the radial distances in $H^{\prime}$. By 6.10 we have
that whenever $x_{1},x_{2}\in V(T)$ are such that $x_{1}$ is parent to $x_{2}$
and $v\in\kappa(x_{2})$ then there exists $u\in\kappa(x_{1})$ so that $u,v$
share a face. Let us fix a vertex $v_{y}\in\kappa(y)$. By the observation
above, there is a vertex $v_{2}\in\kappa(q_{2})$ so that
$d_{H^{\prime}}(v_{y},v_{2})=d_{H}(v_{y},v_{2})\leq 2k+5$. As each path
$P_{i}$, $i\in[d]$, has only one segment in $\kappa(q_{1})$ and one in
$\kappa(q_{2})$, it also has only one segment in $V_{Q}$. The region between
$\kappa(q_{1})$ and $\kappa(q_{2})$ in $H^{\prime}$ comprises $d$ subdivided
edges between $\kappa(q_{1})$ and $\kappa(q_{2})$. Hence, there is a vertex
$v_{1}\in\kappa(q_{1})$ which shares a face with $v_{2}$ in $H^{\prime}$. By
the same argument as before, there is a vertex $v_{x}\in\kappa(x)$ at radial
distance $2k+5$ from $v_{1}$ in $H^{\prime}$. This implies that
$d_{H^{\prime}}(v_{y},v_{x})\leq(2k+5)+1+(2k+5)=4k+11$ and concludes the
proof. ∎

Our strategy is to mark the set of nodes in $T$ whose images cover the
boundary $\partial(H)$ together with its LCA closure. Suppose that $x,y\in
V(T)$ were marked, $x$ is an ancestor of $y$, and $T_{x,y}$ contains no marked
vertices. If $\delta_{T}(x,y)$ is large and there are 6 internally vertex-
disjoint $(\kappa(x),\kappa(y))$-paths, we can use Lemma 6.17 to compress the
middle layers. If the $(\kappa(x),\kappa(y))$-flow is less than 6, there is a
restricted $(\kappa(x),\kappa(y))$-separator of size at most 5. If the number
of such separators is small, we could just mark some more nodes in $T$. We
cannot do this however if there is a long sequence of small
$(\kappa(x),\kappa(y))$-separators. But in this case the subgraph of $H$
between the first and the last separator is disjoint from $\partial(H)$ and
has boundary of size at most 10. Recall that the Vertex planarization problem
admits a lossless protrusion replacer (Lemma 6.2) which allows us to compress
planar subgraphs of small boundary (Lemma 6.6). We use this tool in a
preprocessing step to ensure that the distance between the first and last
small separator cannot be too large.

######  Lemma 6.20.

Let $\gamma$ be the function from Definition 6.1 for the Vertex planarization
problem. There is a polynomial-time algorithm that, given a graph $G$,
integers $k,r$, a set $A\subseteq V(G)$, such that $G\langle A\rangle$ is
planar, $G[A]$ is connected, and $r=|N_{G}(A)|$, returns an $r$-boundaried
plane graph $H^{\prime}$ so the following hold.

  1. 1.

The radial diameter of $H^{\prime}$ is at most
$2\cdot(4k+\gamma(8019)+12)\cdot(6r+5)$ and the graph
$H^{\prime}\setminus\partial(H^{\prime})$ is connected.

  2. 2.

$\mathrm{mvp}(G^{\prime})\leq\mathrm{mvp}(G)$, where $G^{\prime}$ is the graph
obtained from $G$ after replacing $N_{G}[A]$ with $H^{\prime}$.

  3. 3.

Let $A^{\prime}=V(H^{\prime})\setminus\partial(H^{\prime})$ denote the set of
the new vertices inserted in place of $A$. There is a polynomial-time
algorithm that, given a planar modulator $S^{\prime}$ in $G^{\prime}$ such
that $|S^{\prime}\cap A^{\prime}|\leq k$, outputs a planar modulator $S$ in
$G$ such that $|S|\leq|S^{\prime}|+2\cdot|S^{\prime}\cap A^{\prime}|$ and
$S\setminus A=S^{\prime}\setminus A^{\prime}$.

###### Proof.

Let $H$ denote a boundaried plane graph obtained by an arbitrary plane
embedding of $G\langle A\rangle$. We shall perform a series of modifications
of $H$ which does not affect the boundary set. First, we get rid of planar
subgraphs with small boundary. We iterate over all sets $X_{0}\subseteq
V(H)\setminus\partial(H)$ of size at most 10 and inspect whether there is a
connected component $C$ of $H-X_{0}$ which (a) does not contain any vertex
from $\partial(H)$, (b) has at least $\gamma(8019)$ vertices. If we detect
such a component $C$, we invoke Lemma 6.6 for $r=|N_{H}(C)|\leq 10$ and
replace $N_{G}[C]$ with a boundaried subgraph on less than $\gamma(27\cdot
27\cdot 11)=\gamma(8019)$ vertices. This does not affect the minimum vertex
planarization number and allows to perform lossless solution lifting in
polynomial time. We perform such a replacement exhaustively until we cannot
find a pair $(X_{0},C)$ satisfying the requirements. By Lemma 6.6(4) for
$X=V(G)\setminus A$ such a replacement does not affect planarity of the graph
$G\langle A\rangle$. By the same argument for $X=V(G)\setminus N_{G}[A]$ we
get that the replacement cannot disconnect the graph $G[A]$. In each step, the
size of the graph decreases, so at some point there are no more such pairs
$(X_{0},C)$. After this process terminates, we know that there is no separator
of size at most 10, which would disconnect a subgraph of $H$ which does not
touch the boundary and has at least $\gamma(8019)$ vertices. We keep the
variable $H$ to denote the graph after this modification.

Let us now consider the outerplanar decomposition $(T,\chi)$ of $H$. For each
$v\in\partial(H)$ we mark the node $x\in V(T)$ such that $v\in\kappa(x)$. Let
$Y_{0}$ denote the set of marked nodes plus the root node, $|Y_{0}|\leq r+1$,
and $Y_{1}=\overline{\mathsf{LCA}}(Y_{0})$ (recall Definition 3.8). By Lemma
3.9 we know that $|Y_{1}|\leq 2r+2$ and every connected component of $T-Y_{1}$
has at most 2 neighbors. Furthermore, there can be at most $2r+1$ such
components with exactly 2 neighbors because contracting them forms a tree on
$2r+2$ vertices. Consider such a component
$T_{C}\in\mathcal{C}\mathcal{C}(T-Y_{1})$, $N_{T}(T_{C})=\\{x,y\\}$. Then one
of the vertices $x,y$ is an ancestor of the other one. Note that the path
$T^{P}_{x,y}$ is contained in $N_{T}[T_{C}]$. Let $x^{\prime}\in T^{P}_{x,y}$
be the furthest (from $x$) vertex on the $(x,y)$-path for which there are 6
internally vertex-disjoint $(\kappa(x),\kappa(x^{\prime}))$-paths in the graph
$H\langle\kappa(T_{x,x^{\prime}})\rangle$. It might be the case that
$x^{\prime}=y$ or $x^{\prime}=x$. Next, let $y^{\prime}\in T^{P}_{x,y}$ be the
furthest (from $y$) vertex on the $(x^{\prime},y)$-path for which there are 6
internally vertex-disjoint $(\kappa(y),\kappa(y^{\prime}))$-paths in the graph
$H\langle\kappa(T_{y,y^{\prime}})\rangle$. If $x^{\prime}=y$ then
$y^{\prime}=y$.

If $x^{\prime},y^{\prime}$ are distinct, we want to show that their distance
$\delta_{T}(x^{\prime},y^{\prime})$ cannot be larger than some constant.
Suppose that $\delta_{T}(x^{\prime},y^{\prime})>3$. Let
$x^{\prime\prime},y^{\prime\prime}$ be the neighbors of $x,y$, respectively,
on the path $T^{P}_{x^{\prime},y^{\prime}}$. By the definition of
$x^{\prime},y^{\prime}$ there are no 6 internally vertex-disjoint
$(\kappa(x),\kappa(x^{\prime\prime}))$-paths in the graph
$H[\kappa(T_{x,x^{\prime\prime}})]$. The sets
$\kappa(x),\kappa(x^{\prime\prime})$ are non-adjacent in $H$ so by Menger’s
theorem there exists a restricted
$(\kappa(x),\kappa(x^{\prime\prime}))$-separator $S_{x}$ in $H$ of size at
most 5. Analogous observations hold for $y,y^{\prime\prime}$ and there exists
a restricted $(\kappa(y),\kappa(y^{\prime\prime}))$-separator $S_{y}$ in $H$
of size at most 5. Consider the set $X_{0}=S_{x}\cup S_{y}$ of size at most 10
and the connected component of $H-X_{0}$ containing the set
$\kappa(T_{x^{\prime\prime},y^{\prime\prime}})$. By 6.12, it is disjoint from
$\partial(H)$ (as $\partial(H)$ is contained in the $\kappa$-image of $Y_{0}$)
so thanks to the preprocessing procedure we can conclude that it has less than
$\gamma(8019)$ vertices. This implies that
$|T_{x^{\prime\prime},y^{\prime\prime}}|<\gamma(8019)$ and so
$\delta_{T}(x^{\prime},y^{\prime})=|T_{x^{\prime},y^{\prime}}|=|T_{x^{\prime\prime},y^{\prime\prime}}|+2\leq\gamma(8019)+1$.

Let $Y_{2}$ be the union of $Y_{1}$ and all vertices marked as
$x^{\prime},y^{\prime}$ in the previous step. We have
$|Y_{2}|\leq|Y_{1}|+2\cdot(2r+1)\leq 6r+4$. Each connected component
$T_{C}\in\mathcal{C}\mathcal{C}(T-Y_{2})$ with exactly two neighbors,
$N_{T}(T_{C})=\\{x,y\\}$, satisfies one of the following: (a)
$\delta_{T}(x,y)\leq\gamma(8019)+1$, or (b) there are 6 internally vertex-
disjoint $(\kappa(x),\kappa(y))$-paths in the graph
$H\langle\kappa(T_{x,y})\rangle$. Furthermore, one of the vertices $x,y$ is an
ancestor of the other one. In order to reduce the depth of $T$ we will apply
Lemma 6.17 to the components of type (b). Let
$T^{1}_{C},T^{2}_{C},\dots,T^{\ell}_{C}$,
$N_{T}(T^{i}_{C})=\\{x^{i},y^{i}\\}$, be some ordering of the type (b)
components of $T-Y_{2}$ for which $\delta_{T}(x^{i},y^{i})>4k+11$. We have
$T_{x^{i},y^{i}}=T^{i}_{C}$ and these sets are pairwise disjoint. By applying
Lemma 6.17 to $x^{i},y^{i},T^{i}_{C}$ we obtain a set of vertices
$V_{D}^{i}\subseteq\kappa(T^{i}_{C})$ and a set of edges $E_{D}^{i}\subseteq
E_{G}(\kappa(T^{i}_{C}),\kappa(T^{i}_{C}))$ to be removed. Let $G_{0},H_{0}$
be obtained from respectively $G,H$ by removing the edges from all $E_{D}^{i}$
and the vertices from all $V_{D}^{i}$. Furthermore, let $G_{i}$, $i\in[\ell]$,
be obtained from $G$ by performing only the removals from
$V^{j}_{D},E^{j}_{D}$ for $j>i$. Clearly
$\mathrm{mvp}(G_{0})\leq\mathrm{mvp}(G)$ as $G_{0}$ is a subgraph of $G$. Let
$A_{0}=V(H_{0})\setminus\partial(H_{0})$ be the set of vertices that form a
replacement for $A$.

First, we argue that a solution to $G_{0}$ can be lifted into a solution to
$G$ with moderate additional cost. Let $S_{0}\subseteq V(G_{0})$ be a planar
modulator in $G_{0}$ such that $|S_{0}\cap A_{0}|\leq k$. We construct a
series of sets $S_{1},\dots,S_{\ell}$ where $S_{i}$ is a refinement of
$S_{i-1}$ with respect to $T^{i}_{C}$ so that $S_{i}$ is a planar modulator in
$G_{i}$. This holds for $i=0$. Let us consider $i\geq 1$ and suppose that the
claim holds for $i-1$. By Lemma 6.17(3) we can compute a planar modulator
$S_{i}$ in $G_{i}$ of size at most
$|S_{i-1}|+2\cdot|S_{i-1}\cap\kappa(T^{i}_{C})|$ and
$S_{i}\setminus\kappa(T^{i}_{C})=S_{i-1}\kappa(T^{i}_{C})$. The latter
condition guarantees that
$S_{j}\cap\kappa(T^{i}_{C})=S_{0}\cap\kappa(T^{i}_{C})$ for $j<i$ because in
the $j$-step we only add new vertices from $\kappa(T^{j}_{C})$ and these sets
are disjoint. Therefore
$|S_{\ell}|\leq|S_{0}|+\sum_{i=1}^{\ell}2\cdot|S_{0}\cap\kappa(T^{i}_{C})|\leq|S_{0}|+2\cdot|S_{0}\cap
A_{0}|$ and $S_{\ell}\setminus A=S_{0}\setminus A_{0}$. As $S_{\ell}$ is a
planar modulator in $G_{\ell}=G$, the solution lifting algorithm works as
intended.

Now, we analyze the radial diameter of $H_{0}$. Let
$v\in\partial(H_{0})=\partial(H)$ and $y\in Y_{2}$ be such that
$v\in\kappa(y)$. Since the root node $x_{1}$ belongs to $Y_{2}$ and
$|Y_{2}|\leq 6r+4$, there a sequence $y=y_{1},\dots,y_{m}=r$ of at most $m\leq
6r+4$ vertices from $Y_{2}$ so that $y_{i+1}$ is an ancestor of $y_{i}$ and
$T_{y_{i},y_{i+1}}\cap Y_{2}=\emptyset$. If $T_{y_{i},y_{i+1}}$ is a component
of type (b) then by Lemma 6.17(1) we know that for each $u\in\kappa(y_{i})$
there is $u^{\prime}\in\kappa(y_{i+1})$ such that their radial distance in
$H_{0}$ is at most $4k+11$. If $T_{y_{i},y_{i+1}}$ is a component of type (a),
then by 6.10 we get the analogous property but with upper bound
$\gamma(8019)+1$. Therefore $v$ is at radial distance at most
$(4k+\gamma(8019)+12)\cdot(6r+4)$ from some vertex on the outer face.

To analyze the situation for vertices from $V(H_{0})\setminus\partial(H_{0})$
let us consider the outerplanar decomposition $(T_{0},\kappa_{0})$ of $H_{0}$.
By the estimation above, if $v\in\partial(H_{0})=\partial(H)$ then
$\mathrm{\textsc{idx}}_{H_{0}}(v)\leq(4k+\gamma(8019)+12)\cdot(6r+4)$. Suppose
there is a vertex $u\in V(H_{0})\setminus\partial(H_{0})$ for which
$\mathrm{\textsc{idx}}_{H_{0}}(u)>(4k+\gamma(8019)+12)\cdot(6r+4)+k+3$. Then
there are at least $k+3$ outerplanarity layers around $u$ whose interiors are
free of any boundary vertices. Consider the sequence
$u_{1},u_{2},\dots,u_{k+3}\in V(T_{0})$ of the first ancestors of $u$ in
$T_{0}$. By Lemma 6.9(2) each set $\kappa(u_{i})$ induces a connected subgraph
of $G_{0}$. If $v\in\partial(H_{0})$, then
$\mathrm{\textsc{idx}}_{H_{0}}(v)<\mathrm{\textsc{idx}}_{H_{0}}(q_{i})$ and by
Lemma 6.9(3) $\kappa(u_{i})$ is a restricted $(u,v)$-separator in $H_{0}$.
Hence, these sets form a nested sequence of $(u,\partial(H_{0}))$-separators
in $H_{0}$ and thus these are $(u,N_{G_{0}}(A))$-separators in $G_{0}$. We
infer that these sets are $u$-planarizing and by Lemma 3.17 the vertex $u$ is
$k$-irrelevant. While such a vertex $u$ exists we can safely remove it; let
$H^{\prime}$ be the graph obtained from $H_{0}$ after these removals. The
depth of the outerplanar decomposition tree of $H^{\prime}$ is bounded by
$(4k+\gamma(8019)+12)\cdot(6r+4)+k+3$ and the claim follows from Lemma 6.11. ∎

We will apply Lemma 6.20 to each connected component
$C\in\mathcal{C}\mathcal{C}(G-X)$ where $X$ is a strong planar modulator
supplied by Proposition 5.7. We obtain some replacement $H_{C}$ for the
boundaried graph $G\langle C\rangle$ equipped with a plane embedding of
moderate diameter. Because the lifting algorithm from Lemma 6.20 increases the
size of a solution only locally in $C$ and does not affect the solution
outside $C$, we can perform the lifting iteratively, increasing the size of
the solution only by a constant factor in the end.

######  Proposition 6.21.

There is a polynomial-time algorithm that, given a graph $G$ with an
$r$-strong planar modulator $X$ of fragmentation $s$, and integer $k$, outputs
a graph $G^{\prime}$ together with a $r$-strong planar modulator $X^{\prime}$
of fragmentation $s$ and a family of plane embeddings of $G^{\prime}\langle
C^{\prime}\rangle$ for each connected component
$C^{\prime}\in\mathcal{C}\mathcal{C}(G^{\prime}-X^{\prime})$, so that

  1. 1.

$\mathrm{mvp}(G^{\prime})\leq\mathrm{mvp}(G)$,

  2. 2.

for each connected component
$C^{\prime}\in\mathcal{C}\mathcal{C}(G^{\prime}-X^{\prime})$, the computed
plane embedding has radial diameter $\mathcal{O}(kr)$,

  3. 3.

given $G,G^{\prime}$, and a planar modulator $S^{\prime}$ in $G^{\prime}$ of
size at most $k$, one can find, in polynomial time, a planar modulator $S$ in
$G$ of size at most $3\cdot|S^{\prime}|$.

###### Proof.

Let $C_{1},C_{2},\dots,C_{\ell}$ be some ordering of the connected components
$C\in\mathcal{C}\mathcal{C}(G-X)$. We process each $G\langle C_{i}\rangle$
with Lemma 6.20 iteratively. Namely, let $G_{0}=G$ and $G_{i}$ be obtained
from $G_{i-1}$ by applying Lemma 6.20 to $G_{i-1}\langle C_{i}\rangle$, for
$i\in[\ell]$. We set $G^{\prime}=G_{\ell}$. Let $C^{\prime}_{i}$ be the set of
new vertices inserted in place of $C_{i}$ and $H^{\prime}_{i}$ denote the
plane graph given by the computed embedding of $G_{i}\langle
C^{\prime}_{i}\rangle$. We have $\mathrm{mvp}(G_{i})\leq\mathrm{mvp}(G_{i-1})$
so $\mathrm{mvp}(G_{\ell})\leq\mathrm{mvp}(G)$. Furthermore, the radial
diameter of $H^{\prime}_{i}$ is $\mathcal{O}(kr)$ and we are guaranteed that
the graphs
$G_{i}[C^{\prime}_{i}]=H^{\prime}_{i}\setminus\partial(H^{\prime}_{i})$ are
connected so we do not increase the fragmentation of the modulator. As
$|N_{G_{i}}(C^{\prime}_{i})|=|N_{G_{i-1}}(C_{i})|$ the modulator remains
$r$-strong.

It remains to prove the solution lifting property. Let $S_{\ell}\subseteq
V(G_{\ell})$ be a planar modulator in $G_{\ell}$ of size at most $k$. We
construct a series of sets $S_{0},\dots,S_{\ell-1}$ where $S_{i}$ is a
modification of $S_{i+1}$ so that $S_{i}$ is a planar modulator in $G_{i}$ of
size at most $|S_{\ell}|+\bigcup_{j>i}^{\ell}2\cdot|S_{\ell}\cap
C^{\prime}_{j}|$. Moreover, we show inductively that $S_{i}\cap
C^{\prime}_{j}=S_{\ell}\cap C^{\prime}_{j}$ for $j\leq i$, which holds for
$i=\ell$.

We use the lifting algorithm from Lemma 6.20 to turn $S_{i+1}$ into a planar
modulator $S_{i}$ in $G_{i}$ of size at most $|S_{i+1}|+2\cdot|S_{i+1}\cap
C^{\prime}_{i+1}|$ so that $S_{i}\setminus C_{i+1}=S_{i+1}\setminus
C^{\prime}_{i+1}$. The latter condition implies that we do not alter the
solution $j\neq i+1$ and shows the invariant $S_{i}\cap
C^{\prime}_{j}=S_{\ell}\cap C^{\prime}_{j}$ for $j\leq i$. Therefore
$|S_{i+1}\cap C^{\prime}_{i+1}|=|S_{\ell}\cap C^{\prime}_{i+1}|\leq k$ as
required by the lifting algorithm. We estimate the final size of the planar
modulator in $G_{0}$ as $|S_{\ell}|+\sum_{i=1}^{\ell}2\cdot|S_{i}\cap
C^{\prime}_{i}|=|S_{\ell}|+\sum_{i=1}^{\ell}2\cdot|S_{\ell}\cap
C^{\prime}_{i}|\leq 3\cdot|S_{\ell}|$. ∎

##  7 Solution preservers

After the application of Proposition 6.21, we can assume that the considered
graph $G$ has a strong planar modulator $X\subseteq V(G)$ of fragmentation
$k^{\mathcal{O}(1)}$ and for each $C\in\mathcal{C}\mathcal{C}(G-X)$ we are
given a plane embedding of $G\langle C\rangle$ with radial diameter
$k^{\mathcal{O}(1)}$. In order to further simplify $G\langle C\rangle$ we take
a two-step approach. First, we mark a vertex set $S_{C}\subseteq C$ so that
for any solution $S$ we can replace the set $S\cap C$ with a subset of
$S_{C}\cup N_{G}(C)$ by paying a constant cost for each replacement. In
particular, we get that there is an $\mathcal{O}(1)$-approximately optimal
planar modulator $S$ such that $S\cap C\subseteq S_{C}$. Afterwards, in
Section 8, we compress the subgraphs within $C\setminus S_{C}$ for which we
know that the approximately optimal solution does not remove any vertices
inside them. We begin with formalizing the concept of marking vertices to
cover an approximate solution.

######  Definition 7.1.

For a vertex set $A\subseteq V(G)$, we say that $S_{A}\subseteq A$ is an
$\alpha$-preserver for $A$, if for any planar modulator $S$ in $G$ there
exists a planar modulator $S^{\prime}\subseteq(S\setminus A)\cup N_{G}(A)\cup
S_{A}$ such that $S^{\prime}\setminus N_{G}[A]=S\setminus N_{G}[A]$ and
$|S^{\prime}|\leq|S|+\alpha\cdot|S\cap A|$.

We are going to construct these solution preservers recursively by reducing
the task to more structured boundaried graphs. We analyze this process by
decomposing a boundaried graph $H$ into a set $Y$ which can be regarded as an
augmentation of the boundary $\partial(H)$ and a family of smaller boundaried
graphs whose boundary lies on $\partial(H)\cup Y$.

######  Definition 7.2.

A boundaried decomposition of a boundaried graph $H$ is a pair
$(Y,\mathcal{C})$, where $Y\subseteq V(H)\setminus\partial(H)$ and
$\mathcal{C}$ is a partition of $V(H)\setminus(\partial(H)\cup Y)$, such that
for each $C\in\mathcal{C}$ it holds that $N_{H}(C)\subseteq\partial(H)\cup Y$.

For example, when $\mathcal{C}=\mathcal{C}\mathcal{C}(H-(\partial(H)\cup Y))$
is given by the connected components of $H-(\partial(H)\cup Y)$ then
$(Y,\mathcal{C})$ is a boundaried decomposition of $H$. For our convenience,
we will also consider cases when some elements of $\mathcal{C}$ are
disconnected. Usually, we begin with finding a set $Y$ that imposes some
properties on boundaried graphs $H\langle C\rangle$ for $C\in\mathcal{C}$. In
order to bound the number of subcases to recurse on, we would like to upper
bound the maximal size of $\mathcal{C}$ in terms of $Y$. This is not always
possible, but at least we can bound the number of sets $C\in\mathcal{C}$ with
more than two neighbors.

######  Lemma 7.3 ([FLSZ19, Lem. 13.3]).

Let $G$ be a planar graph, $X\subseteq V(G)$, and let $N_{3}$ be a set of
vertices from $V(G)\setminus X$ such that every vertex from $N_{3}$ has at
least three neighbors in $X$. Then, $|N_{3}|\leq 2\cdot|X|$.

For a vertex set $X\subseteq V(G)$ in a planar graph $G$, consider the graph
obtained from $G$ by contracting each connected component of $G-X$ into a
single vertex. Since contractions preserve planarity, we get the following
corollary using the definition of fragmentation (Definition 3.3).

######  Lemma 7.4.

For a planar graph $G$ and a vertex set $X\subseteq V(G)$, the fragmentation
of $X$ in $G$ is at most $2\cdot|X|$.

The following lemmas provide us with a framework to compute solution
preservers recursively using boundaried decompositions. The property
$S^{\prime}\setminus N_{G}[A]=S\setminus N_{G}[A]$ in Definition 7.1 plays a
role in the second lemma because by modifying a solution locally we do not
affect its intersection with other parts of the decomposition.

######  Lemma 7.5.

Consider a graph $G$ and vertex sets $A,Y\subseteq V(G)$. If $S_{A}\subseteq
A$ is an $\alpha$-preserver for $A$, for some $\alpha\geq 1$, then $S_{A}\cup
Y$ is an $\alpha$-preserver for $A\cup Y$.

###### Proof.

Let $S\subseteq V(G)$ by any planar modulator in $G$. By the definition of an
$\alpha$-preserver, there exists a planar modulator $S^{\prime}\subseteq V(G)$
such that $S^{\prime}\subseteq(S\setminus A)\cup N_{G}(A)\cup S_{A}$,
$S^{\prime}\setminus N_{G}[A]=S\setminus N_{G}[A]$, and
$|S^{\prime}|\leq|S|+\alpha\cdot|S\cap A|\leq|S|+\alpha\cdot|S\cap(A\cup Y)|$.
The first property can be restated as $S^{\prime}\subseteq(S\setminus(A\cup
Y))\cup N_{G}(A\cup Y)\cup(S_{A}\cup Y)$ because inserting $Y$ at the end
covers all the modifications to the first two terms. Since $N_{G}[A]\subseteq
N_{G}[A\cup Y]$ we get $S^{\prime}\setminus N_{G}[A\cup Y]=S\setminus
N_{G}[A\cup Y]$. This satisfies all the three conditions of an
$\alpha$-preserver for $A\cup Y$. ∎

######  Lemma 7.6.

Consider a graph $G$ and vertex sets $A,B\subseteq V(G)$, such that
$N_{G}[A]\cap B=\emptyset$. If $S_{A}\subseteq A,S_{B}\subseteq B$ are
$\alpha$-preservers for respectively $A,B$, for some $\alpha\geq 1$, then
$S_{A}\cup S_{B}$ is an $\alpha$-preserver for $A\cup B$.

###### Proof.

Let $S\subseteq V(G)$ by any planar modulator in $G$. By the definition of an
$\alpha$-preserver, there exists a planar modulator $S_{1}\subseteq V(G)$ such
that $S_{1}\subseteq(S\setminus A)\cup N_{G}(A)\cup S_{A}$, $S_{1}\setminus
N_{G}[A]=S\setminus N_{G}[A]$, and $|S_{1}|\leq|S|+\alpha\cdot|S\cap A|$. The
second property implies that $S_{1}\cap B=S\cap B$. Next, we apply the
definition for the set $B$ and solution $S_{1}$. We obtain a planar modulator
$S_{2}\subseteq V(G)$ such that $S_{2}\subseteq(S_{1}\setminus B)\cup
N_{G}(B)\cup S_{B}$, $S_{2}\setminus N_{G}[B]=S_{1}\setminus N_{G}[B]$, and
$|S_{2}|\leq|S_{1}|+\alpha\cdot|S_{1}\cap B|\leq|S|+\alpha\cdot|S\cap
A|+\alpha\cdot|S\cap B|=|S|+\alpha\cdot|S\cap(A\cup B)|$.

We check that $S_{1}\setminus B\subseteq S\setminus(A\cup B)\cup N_{G}(A)\cup
S_{A}$ and $N_{G}(B)\cap A=N_{G}(A)\cap B=\emptyset$ so $S_{2}\subseteq
S\setminus(A\cup B)\cup N_{G}(A\cup B)\cup(S_{A}\cup S_{B})$.

Finally, both $N_{G}[A],N_{G}[B]$ are subsets of $N_{G}[A\cup B]$ so we
trivially obtain $S_{2}\setminus N_{G}[A\cup B]=S_{1}\setminus N_{G}[A\cup
B]=S\setminus N_{G}[A\cup B]$. ∎

From these two observations, we can easily obtain the following useful lemma.

######  Lemma 7.7.

Consider a graph $G$, vertex set $A\subseteq V(G)$, and a boundaried
decomposition $(Y,\mathcal{C})$ of $G\langle A\rangle$. Suppose that for each
set $C\in\mathcal{C}$ we are given an $\alpha$-preserver $S_{C}\subseteq C$
for $C$. Then the set $Y\cup\bigcup_{C\in\mathcal{C}}S_{C}$ is an
$\alpha$-preserver for $A$.

###### Proof.

We fix any ordering $C_{1},\dots,C_{m}$ of $\mathcal{C}$. For any distinct
$i,j\in[m]$ we have $N_{G}[C_{i}]\cap C_{j}=\emptyset$. From Lemma 7.6 we
obtain that $S_{C_{1}}\cup S_{C_{2}}$ is an $\alpha$-preserver for $C_{1}\cup
C_{2}$ and, by repeating this argument, that $\bigcup_{i=1}^{\ell}S_{C_{i}}$
is an $\alpha$-preserver for $\bigcup_{i=1}^{\ell}C_{i}$, for each
$\ell\in[m]$. Next, we apply Lemma 7.5 to $\bigcup_{i=1}^{\ell}C_{i}$ and $Y$,
to get that $\bigcup_{C\in\mathcal{C}}S_{C}\cup Y$ is an $\alpha$-preserver
for their union, that is $A$. ∎

Suppose that $G$ is a graph, $X\subseteq V(G)$ is a planar modulator in $G$,
and for each component $C\in\mathcal{C}\mathcal{C}(G-X)$ we have computed an
$\alpha$-preserver $S_{C}\subseteq C$. We can apply Lemma 7.7 to the
boundaried graph $(G,\emptyset)$ (with the empty boundary) and the boundaried
decomposition $(X,\mathcal{C}\mathcal{C}(G-X))$ to get that
$X^{\prime}=X\cup\bigcup_{C\in\mathcal{C}\mathcal{C}(G-X)}S_{C}$ is an
$\alpha$-preserver for $V(G)$. In other words, for every planar modulator
$S\subseteq V(G)$ in $G$, including the optimal one, there exists a planar
modulator $S^{\prime}$ in $G$ such that $S^{\prime}\subseteq X^{\prime}$ and
$|S^{\prime}|\leq\alpha\cdot|S|$. This will allow us to restrict our attention
only to the approximate solutions contained in $X^{\prime}$.

###  7.1 Reduction to single-faced boundaried graphs

In this section, we show how to reduce the task of constructing a solution
preserver for $G\langle A\rangle$ with a given embedding of bounded diameter
to the case where in the embedding of $G\langle A\rangle$ all the boundary
vertices lie on the outer face. As an intermediate step, we shall consider
circumscribed boundaried plane graphs, which are slightly more general than
single-faced plane graphs. This reduction will also come in useful in Section
8.

As we work with boundaried plane graphs of bounded radial diameter, we can
mark a bounded-size set of faces covering the boundary and forming a connected
area on the plane. Then the remaining parts of the graph interact with their
boundaries only through the outer faces. Recall the definition of a radial
graph from Section 3.

######  Definition 7.8.

Let $G$ be a plane graph and let $\mathsf{Rad}(G)=(V(G)\cup F,E)$ be the
radial graph of $G$. We say that $S\subseteq V(G)$ is radially connected if
there exists $F^{\prime}\subseteq F$ such that $\mathsf{Rad}(G)[S\cup
F^{\prime}]$ is connected.

Given a set of vertices in a plane graph of moderate radial diameter we want
to find its superset that is radially connected. A bound on the radial
diameter translates to a bound on the diameter of the radial graph. We will
take advantage of the following simple observation about bounded-diameter
graphs.

######  Lemma 7.9.

Let $G$ be a connected graph of diameter bounded by $d$. Then for any non-
empty vertex set $S\subseteq V(G)$ there exists $S^{\prime}\supseteq S$ such
that $G[S^{\prime}]$ is connected and $|S^{\prime}|\leq d\cdot|S|$.
Furthermore, such a set $S^{\prime}$ can be found in polynomial time when $G$
and $S$ are given.

###### Proof.

We prove by induction on $\ell$ that if $G[S]$ has $\ell$ connected
components, there is a connected superset $S^{\prime}\supseteq S$ of size at
most $|S|+\ell(d-1)$. This proves that any set $S$ has a connected superset of
size at most $d\cdot|S|$ since $G[S]$ has at most $\ell\leq|S|$ connected
components, and therefore gives the lemma.

If $\ell=1$ then $S^{\prime}=S$ suffices. Otherwise, let $C_{1},C_{2}$ be
distinct connected components of $G[S]$ and let $v_{1}\in C_{1},v_{2}\in
C_{2}$. Since the diameter of $G$ is at most $d$, there is a
$(v_{1},v_{2})$-path $P$ in $G$ of length at most $d$, which has at most $d-1$
internal vertices $I$. Then $S\cup I$ has at most $\ell-1$ connected
components. By induction, there is a connected superset $S^{\prime}$ of $S\cup
I$ on at most $|S\cup I|+(\ell-1)\cdot(d-1)\leq|S|+\ell(d-1)$ vertices, which
concludes the proof. The inductive argument easily turns into a recursive
polynomial-time algorithm. ∎

######  Lemma 7.10.

Let $G$ be a plane graph of radial diameter bounded by $d$. Then for any
vertex set $S\subseteq V(G)$ there exists $S^{\prime}\supseteq S$ such that
$S^{\prime}$ is radially connected in $G$ and
$|S^{\prime}|\leq|S|\cdot(2d+2)$. Furthermore, the set $S^{\prime}$ can be
found in polynomial time when $G$ and $S$ are given.

###### Proof.

Let $\mathsf{Rad}(G)=(V(G)\cup F,E)$ be the radial graph of $G$. Note that
$\mathsf{Rad}(G)$ is always connected, even if $G$ is not. Consider some pair
$u,v\in V(G)$. By assumption $d_{G}(u,v)\leq d$ and so there exists a
$(u,v)$-path in $\mathsf{Rad}(G)$ of length at most $2d$, as any jump between
vertices that share a face $f$ can be emulated in $\mathsf{Rad}(G)$ by
visiting the vertex representing $f$. Furthermore, each vertex from $F$ is
adjacent in $\mathsf{Rad}(G)$ to some vertex from $V(G)$, so $\mathsf{Rad}(G)$
has diameter at most $2d+2$. By Lemma 7.9, there exists a set $S_{R}\supseteq
S$, $S_{R}\subseteq V(\mathsf{Rad}(G))$, so that $\mathsf{Rad}(G)[S_{R}]$ is
connected and $|S_{R}|\leq|S|\cdot(2d+2)$, and this set can be efficiently
computed. The claim follows by taking $S^{\prime}=S_{R}\cap V(G)$. ∎

We proceed with decomposing a boundaried plane graph of moderate diameter into
circumscribed boundaried plane graphs by augmenting the boundary to be
radially connected. Recall Definition 3.11 of a circumscribed boundaried plane
graph $H$: all vertices of $\partial(H)$ must be embedded in the outer face of
$H-\partial(H)$.

######  Lemma 7.11.

There is a polynomial-time algorithm that, given a boundaried plane graph $H$
of radial diameter at most $d$ and a (possibly empty) vertex set $Y\subseteq
V(H)\setminus\partial(H)$, outputs a vertex set $Y^{\prime}\subseteq
V(H)\setminus\partial(H)$ of size at most $(2d+2)\cdot(|Y|+|\partial(H)|)$,
such that for each connected component $C$ of $H-(\partial(H)\cup Y^{\prime})$
the boundaried plane graph $H\langle C\rangle$ is circumscribed.

###### Proof.

We apply Lemma 7.10 for $S=\partial(H)\cup Y$, to find a set
$S^{\prime}\supseteq\partial(H)$ of size at most
$(2d+2)\cdot(|Y|+|\partial(H)|)$, which is radially connected in $H$. Consider
a connected component $C$ of $H-S^{\prime}$ and the plane embedding of $H$
truncated to the subgraph induced by $C$. Suppose there are at least two faces
of $H[C]$ containing vertices from $N_{H}(C)$ (which is a subset of
$S^{\prime}$). Then there exists a cycle in $H-S^{\prime}$ with at least one
vertex of $S^{\prime}$ in the interior and at least one vertex of $S^{\prime}$
in the exterior. This contradicts the fact that $S^{\prime}$ is radially
connected in $H$. We infer that there is only one face of $H[C]$ which
contains vertices from $N_{H}(C)$, hence the graph $H\langle C\rangle$ is
circumscribed. Note that we can always modify the embedding by swapping the
outer face with any other chosen face. The claim follows by taking
$Y^{\prime}=S^{\prime}\setminus\partial(H)$. ∎

We are already close to the case with the boundary lying on the outer face.
There is however a subtle difference between circumscribed and single-faced
boundaried plane graphs. If $H$ is circumscribed, then the edges incident to
the boundary of $H$ may separate some vertices of $\partial(H)$ from the outer
face of $H$.

We shall employ Lemma 3.7 to decompose $H$ into boundaried subgraphs adjacent
to at most two vertices from $\partial(H)$. We want to say that such a
boundaried subgraph $H\langle C\rangle$ becomes single-faced after discarding
these two special vertices. This is done by exploiting minimality of a
particular separator which guarantees that there exists a subgraph disjoint
from $N_{H}[C]$, that can be made connected without violating planarity,
adjacent to each vertex in $N_{H}(C)$. Contracting this subgraph gives the
closure graph of $H\langle C\rangle$ and allows us to use the criterion from
3.13.

In order to use Lemma 3.7 we need a tree decomposition of width
$k^{\mathcal{O}(1)}$. Such a decomposition is computed in Section 4 but later
we apply several graph modifications in Section 6, including protrusion
replacement. This might invalidate the tree decomposition and we need to
compute it anew.

######  Lemma 7.12.

There is a polynomial-time algorithm that, given an $r$-boundaried
circumscribed plane graph $H$ of radial diameter at most $d$, such that $r\geq
3$, outputs a vertex set $Y\subseteq V(H)\setminus\partial(H)$ of size at most
$18\cdot dr$, such that for each connected component $C$ of
$H-(\partial(H)\cup Y)$ it holds that

  1. 1.

$|N_{H}(C)\cap\partial(H)|\leq 2$, and

  2. 2.

the boundaried graph $H\langle C\rangle-(N_{H}(C)\cap\partial(H))$ is single-
faced.

###### Proof.

The graph $H$ has at most $d$ outerplanarity layers, so its treewidth is at
most $3d-1$ [Bod98]. We invoke the polynomial-time $\frac{3}{2}$-approximation
algorithm for treewidth on planar graphs [ST94]888The work [ST94] focuses on
computing branchwidth exactly on planar graphs and the
$\frac{3}{2}$-approximation for treewidth follows from the close relation
between treewidth and branchwidth. to compute a tree decomposition $(T,\chi)$
of $H$ of width at most $\eta=\frac{3}{2}(3d-1)$.

We supply the computed tree decomposition to Lemma 3.7 for $S=\partial(H)$ and
obtain a vertex set $Y\subseteq V(H)\setminus\partial(H)$ such that $|Y|\leq
4(\eta+1)\cdot r\leq 18\cdot dr$ and each connected component of
$H-(\partial(H)\cup Y)$ has at most 2 neighbors in $\partial(H)$ and at most
$2\eta$ neighbors in $Y$. The latter property is not used in this proof.

In order to ensure condition (2) of the lemma, we need to trim the set $Y$.
Consider the following reduction rule: while there exists a vertex $v\in Y$
such that $Y\setminus\\{v\\}$ still satisfies condition (1), remove $v$ from
$Y$. Let $Y^{\prime}\subseteq Y$ be the set obtained by exhaustive application
of the reduction rule. Observe that $Y^{\prime}\neq\emptyset$ because
otherwise the only connected component of $H-\partial(H)$ would have $r\geq 3$
neighbors in $\partial(H)$ which does not satisfy condition (1).

Consider a connected component $C$ of $H-(\partial(H)\cup Y^{\prime})$ and
$v\in N_{H}(C)\cap Y^{\prime}$. Since $v$ has not been removed in the
application of the reduction rule, there is a different connected component of
$H-(\partial(H)\cup Y^{\prime})$ which is adjacent to $v$ and to some
$t\in\partial(H)$. Let $H^{1}$ be obtained from $H$ by (1) removing
$N_{H}(C)\cap\partial(H)$, and (2) replacing $\partial(H)\setminus N_{H}(C)$
with a single vertex $u$ adjacent to entire set $N_{H}(\partial(H))$. This
operation can be seen as inserting a vertex adjacent to a subset of vertices
lying on the outer face of $H-\partial(H)$, so $H^{1}$ is planar. By the
observation above, the set $R_{H^{1}}(u,Y^{\prime})$ is adjacent to each $v\in
N_{H^{1}}(C)\cap Y^{\prime}$ and it is disjoint from $C$. Let $H^{2}$ be
obtained from $H^{1}$ by contracting the connected vertex set
$R_{H^{1}}(u,Y^{\prime})$ into $u$. This graph contains $H\langle
C\rangle-(N_{H}(C)\cap\partial(H))$ as a boundaried subgraph $H^{2}\langle
C\rangle$, together with $u\not\in C$ adjacent to each vertex in
$N_{H^{2}}(C)$. Therefore, $H^{2}$ is the closure graph of $H\langle
C\rangle-(N_{H}(C)\cap\partial(H))$ which, as $H^{2}$ is planar and connected,
implies that $H\langle C\rangle-(N_{H}(C)\cap\partial(H))$ is single-faced
(see 3.13). ∎

#### Retrieving solution preservers from boundaried decompositions

We have shown how to decompose the bounded-diameter case into the
circumscribed case, and the circumscribed case into the single-faced case. Now
we want to use Lemma 7.7 to “backpropagate” these reductions and retrieve the
solution preservers. We first state a crucial proposition which allows us to
construct a solution preserver for a single-faced boundaried graph.

######  Proposition 7.13.

Let $A\subseteq V(G)$ be such that $G\langle A\rangle$ is a single-faced
boundaried graph. Then there exists a set $S_{A}\subseteq A$ of size at most
$|N_{G}(A)|^{2}$ which is a 168-preserver for $A$. Furthermore, $S_{A}$ can be
computed in polynomial time.

In order to keep the focus of the current section, we postpone the proof of
Proposition 7.13 to the end of Section 7.3 and first discuss its implications.
As the case of a circumscribed boundaried graph can be reduced to the case
with a single-faced boundaried graph via Lemma 7.12, our framework yields a
construction of solution preservers for circumscribed boundaried graphs.

This construction may require removal of at most two vertices from the
obtained boundaried subgraph $G\langle A\rangle$ to make it single-faced. This
however does not impose much trouble: if $S$ is a solution and $S\cap A$ is
non-empty we can “charge” this part of the solution to pay for the removal of
the two vertices, turning an $\alpha$-preserver into an
$(\alpha+2)$-preserver. Similarly we argue that when $|N_{G}(A)|\leq 2$ then
if $S\cap A$ is non-empty then we may just remove $N_{G}(A)$ so in this case
the empty set is a 2-preserver for $A$.

######  Lemma 7.14.

Consider a graph $G$, a vertex set $A\subseteq V(G)$ such that
$|N_{G}(A)|=r\geq 3$, and a circumscribed embedding of $G\langle A\rangle$ of
radial diameter at most $d$. Then there exists a 170-preserver $S_{A}\subseteq
A$ for $A$ of size $\mathcal{O}(d^{3}r^{3})$. Furthermore, $S_{A}$ can be
computed in polynomial time when given $G,A$, and the embedding of $G\langle
A\rangle$.

###### Proof.

We apply Lemma 7.12 to compute a set $Y\subseteq A$ of size at most $18\cdot
dr$, such that for each connected component $C$ of $G\langle
A\rangle-(N_{G}(A)\cup Y)$ there exists a set $D_{C}=N_{G}(C)\cap N_{G}(A)$ of
size at most 2 so that the boundaried graph $G\langle C\rangle-D_{C}$ is
single-faced. Let $\mathcal{C}$ be the family of connected components of
$G\langle A\rangle-(N_{G}(A)\cup Y)$. Then $(Y,\mathcal{C})$ is a boundaried
decomposition of $G\langle A\rangle$. We partition $\mathcal{C}$ into families
$\mathcal{C}_{\leq 2}$, comprising those components that have at most 2
neighbors, and $\mathcal{C}_{\geq 3}$, which contains all the remaining
components.

For $C\in\mathcal{C}_{\leq 2}$ a 2-preserver is given by the empty set: for
any planar modulator $S\subseteq V(G)$ satisfying $|S\cap C|\geq 1$ we can
replace $S\cap C$ with $N_{G}(C)$. Consider now a component
$C\in\mathcal{C}_{\geq 3}$. Let $G^{\prime}=G-D_{C}$; we have that
$G^{\prime}\langle C\rangle=G\langle C\rangle-D_{C}$ is a single-faced
boundaried graph. We apply Proposition 7.13 to compute a 168-preserver
$S_{C}\subseteq C$ for $C$ in $G^{\prime}$ of size at most
$|N_{H}(C)|^{2}=\mathcal{O}(d^{2}r^{2})$. We claim that $S_{C}$ is a 170
preserver for $C$ in $G$. To see this, consider a planar modulator $S\subseteq
V(G)$ in $G$ satisfying $|S\cap C|\geq 1$. Then $S_{1}=S\setminus D_{C}$ is a
planar modulator in $G^{\prime}$. By the definition of an $\alpha$-preserver,
there exists a planar modulator $S_{2}$ in $G^{\prime}$, such that (1)
$S_{2}\subseteq(S_{1}\setminus C)\cup N_{G^{\prime}}(C)\cup S_{C}$, (2)
$S_{2}\setminus N_{G^{\prime}}[C]=S_{1}\setminus N_{G^{\prime}}[C]$, and (3)
$|S_{2}|\leq|S_{1}|+168\cdot|S_{1}\cap C|$. We set $S_{3}=S_{2}\cup D_{C}$, so
$|S_{3}|\leq|S|+170\cdot|S\cap C|$. It is a planar modulator in $G$ and, since
$D_{C}\subseteq N_{G}(C)$, it is a correct replacement for $S$.

By Lemma 7.7 we obtain that $S_{A}=Y\cup\bigcup_{C\in\mathcal{C}_{\geq
3}}S_{C}$ is a 170-preserver for $A$. We estimate $|\mathcal{C}_{\geq 3}|\leq
2\cdot|N_{G}(A)\cup Y|=\mathcal{O}(dr)$ with Lemma 7.4 so the total size of
$S_{A}$ is $\mathcal{O}(d^{3}r^{3})$. ∎

Finally, we employ the reduction from Lemma 7.11 to extend the construction
above to the case of boundaried plane graphs with bounded diameter. The
following proposition encapsulates all the results about solution preservers
into a statement to be used in the main proof.

######  Proposition 7.15.

Consider a graph $G$, a vertex set $A\subseteq V(G)$ such that $|N_{G}(A)|=r$,
and a plane embedding of $G\langle A\rangle$ of radial diameter at most $d$.
Then there exists a 170-preserver $S_{A}\subseteq A$ for $A$ of size
$\mathcal{O}(d^{7}r^{4})$. Furthermore, $S_{A}$ can be computed in polynomial
time when $G,A$, and the embedding of $G\langle A\rangle$ are given.

###### Proof.

Let $H$ be a boundaried plane graph of radial diameter at most $d$ given by
the embedding of $G\langle A\rangle$. We apply Lemma 7.11 to $H$ with
$Y=\emptyset$ to compute a set $Y^{\prime}$ of size at most $(2d+2)\cdot r$
such that for each connected component $C$ of $H-(\partial(H)\cup Y^{\prime})$
the boundaried plane graph $H\langle C\rangle$ is circumscribed. Let
$\mathcal{C}$ be the family of connected components of $H-(\partial(H)\cup
Y)$. We partition $\mathcal{C}$ into families $\mathcal{C}_{\leq 2}$,
comprising those components that have at most 2 neighbors, and
$\mathcal{C}_{\geq 3}$, which contains all the remaining components. We
proceed similarly as in Lemma 7.14.

For $C\in\mathcal{C}_{\leq 2}$ a 2-preserver is given by the empty set: for
any planar modulator $S\subseteq V(G)$ satisfying $|S\cap C|\geq 1$ we can
replace $S\cap C$ with $N_{G}(C)$. For each component $C\in\mathcal{C}_{\geq
3}$ we have that $|N_{H}(C)|\leq|Y\cup\partial(H)|=\mathcal{O}(dr)$.
Furthermore, the radial diameter bound from $G\langle A\rangle$ transfers to
$G\langle C\rangle$. We take advantage of Lemma 7.14 to compute a
170-preserver $S_{C}\subseteq C$ of size $\mathcal{O}(d^{6}r^{3})$.

By Lemma 7.7 we obtain that $S_{A}=Y\cup\bigcup_{C\in\mathcal{C}_{\geq
3}}S_{C}$ is a 170-preserver for $A$. We estimate $|\mathcal{C}_{\geq 3}|\leq
2\cdot|N_{G}(A)\cup Y|=\mathcal{O}(dr)$ with Lemma 7.4 so the total size of
$S_{A}$ is $\mathcal{O}(d^{7}r^{4})$. ∎

###  7.2 Inseparability in single-faced boundaried graphs

This section, together with the following one, are devoted to proving
Proposition 7.13. To this end, we first develop a framework of inseparability
in single-faced boundaried graphs and reduce computing a solution preserver to
the case where the given single-faced boundaried graph is inseparable. In the
next section, we will focus on the inseparable case.

Given a single-faced boundaried plane graph $H$ we can consider a natural
cyclic ordering of $\partial(H)$. Since the vertices of $\partial(H)$ lie on
the outer face, we can augment the embedding by inserting a special vertex
$u_{H}$ adjacent to all vertices in $\partial(H)$. This operation turns $H$
into its closure graph $\widehat{H}$ (see 3.13). After this operation we get a
unique cyclic ordering of the neighbors of the special vertex $u_{H}$, which
are the vertices from $\partial(H)$. When considering a single-faced
boundaried plane graph $H$, we always implicitly assume a fixed cylic ordering
of $\partial(H)$, given by some embedding of $\widehat{H}$. For such an
ordering, we define a _canonical division_ as a partition
$\partial(H)=T_{1}\uplus T_{2}$ such that $T_{1},T_{2}$ are non-empty
connected segments in the cyclic ordering of $\partial(H)$. We say that sets
$T_{1},T_{2}\subseteq T$ are _non-crossing_ if they are non-empty and there
exists a canonical division $(T^{\prime}_{1},T^{\prime}_{2})$ such that
$T^{\prime}_{1}\supseteq T_{1}$, $T^{\prime}_{2}\supseteq T_{2}$.

######  Observation 7.16.

Consider a single-faced boundaried plane graph $H$ and a canonical division
$(T_{1},T_{2})$ of $\partial(H)$. Let $H^{\prime\prime}$ be obtained by adding
two new vertices $t_{1},t_{2}$, adjacent to $T_{1}$ and $T_{2}$, respectively.
Then $H^{\prime\prime}$ is planar.

The following definition plays a key role in this section.

######  Definition 7.17.

A $c$-separation $(T_{1},T_{2},S)$ in a boundaried graph $H$ is given by an
unrestricted $(T_{1},T_{2})$-separator $S$, such that
$T_{1},T_{2}\subseteq\partial(H)$ are non-empty and disjoint, and
$c\cdot|S|\leq\min(|T_{1}|,|T_{2}|)$. We say that a boundaried graph $H$ is
$c$-inseparable if it does not admit a $c$-separation.

Given a single-faced boundaried plane graph $H$, we say that a $c$-separation
$(T_{1},T_{2},S)$ is canonical if $(T_{1},T_{2})$ is a canonical division of
$\partial(H)$ and $S$ is an inclusion-wise minimal unrestricted
$(T_{1},T_{2})$-separator.

Our current goal is to reduce the task of finding solution preservers into the
case when the given single-faced boundaried graph is $c$-inseparable for some
constant $c$. As long as some $c$-separation exists, ideally we would like to
find it and recurse on the both sides of the separator. It is however unclear
whether a $c$-separation can be detected in polynomial time or whether the
obtained boundaried subgraphs are always single-faced. First we show that when
we can separate some non-crossing subsets of the boundary with a small
separator, we can do the same for some canonical division.

######  Lemma 7.18.

Let $H$ be a single-faced boundaried plane graph and
$T_{1},T_{2}\subseteq\partial(H)$ be non-crossing. Suppose there exists an
unrestricted $(T_{1},T_{2})$-separator $S$, such that
$c\cdot|S|\leq\min(|T_{1}|,|T_{2}|)$. Then $H$ admits a canonical
$c$-separation.

###### Proof.

Let $T^{\prime}_{1}\supseteq T_{1},T^{\prime}_{2}\supseteq T_{2}$ be disjoint
segments of $\partial(H)$ witnessing the non-crossing property. Let
$H^{\prime\prime}$ be obtained from $H$ by adding a new vertex $t_{1}$
adjacent to all $v\in T_{1}$ and a new vertex $t_{2}$ adjacent to all $v\in
T_{2}$. Since $T_{1},T_{2}$ are non-crossing, $H^{\prime\prime}$ is planar by
7.16. We can assume that each vertex $v\in T^{\prime}_{1}$ either belongs to
$T_{1}$ or to $R=R_{H^{\prime\prime}}(t_{2},S)\setminus\\{t_{2}\\}$, since if
neither holds then we can add $v$ to $T_{1}$ while preserving the
preconditions to the lemma.

We introduce some terminology for the rest of the proof. Suppose
$V_{1},V_{2}\subseteq T_{1}$ are two disjoint segments of terminals. Then the
set $\partial(H)\setminus(V_{1}\cup V_{2})$ comprises of two segments
$U_{1},U_{2}$ ($U_{1}$ possibly empty) such that $T_{2}\subseteq U_{2}$. We
say that a vertex $v\in\partial(H)$ lies _between_ $V_{1}$ and $V_{2}$ when
$v\in U_{1}$.

We divide $T_{1}$ into a sequence of (maximal) segments $Q_{1},\dots,Q_{m}$,
ordered with respect to the embedding, such that the boundary vertices
_between_ $Q_{i}$ and $Q_{i+1}$ belong to $R$. Let $C_{i}$ be the set of
vertices reachable from any $v\in Q_{i}$ in $H^{\prime\prime}$ without going
through $R$ or $t_{1}$, that is,
$C_{i}=R_{H^{\prime\prime}}(Q_{i},R\cup\\{t_{1}\\})$.

We claim that the sets $(C_{i})_{i=1}^{m}$ are pairwise disjoint. Assume
otherwise that $C_{i}\cap C_{j}\neq\emptyset$ for some $i<j$. Then there exist
vertices $v_{1}\in Q_{i}$ and $v_{3}\in Q_{j}$ connected by a path $P_{1,3}$
in $V(H)-R$. Let $v_{2}\in T^{\prime}_{1}\cap R$ be some vertex lying between
$Q_{i}$ and $Q_{j}$. Since $v_{2}\in R$, there exists a path $P_{2,4}$
connecting $v_{2}$ to some vertex $v_{4}\in T^{\prime}_{2}$ such that
$V(P)\subseteq R$. Note that the numbering of vertices
$v_{1},v_{2},v_{3},v_{4}$ obeys the cyclic ordering of terminals given by the
single-faced embedding. Let $H_{0}$ be a graph obtained from $H$ by inserting
edges $v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{1}$ and a new vertex $v_{5}$
adjacent $\\{v_{1},v_{2},v_{3},v_{4}\\}$. By the choice of the ordering,
$H_{0}$ is planar. The path $P_{1,3}$ within $V(H)\setminus R$ connecting
$v_{1}$ and $v_{3}$ is disjoint from the path $P_{2,4}$ connecting $v_{2}$ and
$v_{4}$ within $R$. By contracting the paths $P_{1,3}$, $P_{2,4}$ to edges we
obtain a minor model of $K_{5}$ in $H_{0}$, which is a contradiction with the
assumption that $C_{i}\cap C_{j}\neq\emptyset$.

Using the disjointness property we finish the proof. Let $S_{i}=S\cap C_{i}$
for $i\in[m]$. The sets $(S_{i})_{i=1}^{m}$ are pairwise disjoint and the sets
$(Q_{i})_{i=1}^{m}$ sum up to $T_{1}$, hence the assumption
$c\cdot|S|\leq\min(|T_{1}|,|T_{2}|)$ implies that $c\cdot|S_{i}|\leq|Q_{i}|$
for some $i\in[m]$. The set $S_{i}$ is an unrestricted $(Q_{i},R)$-separator
in $H$ and an unrestricted $(Q_{i},Q_{j})$-separator in $H$ for each $j\neq i$
because $C_{i}\cap C_{j}=\emptyset$. Therefore, $S_{i}$ is an unrestricted
$(Q_{i},\partial(H)\setminus Q_{i})$ separator. Since $c\cdot|S_{i}|\leq
c\cdot|S|\leq|T_{2}|\leq|\partial(H)\setminus Q_{i}|$, we obtain a canonical
$c$-separation. ∎

We now show that the existence of a $(2c)$-separation implies the existence of
a $c$-separation of non-crossing subsets, which in turn implies the existence
of a canonical $c$-separation.

######  Lemma 7.19.

Let $H$ be a single-faced boundaried graph, $T_{1},T_{2}\subseteq\partial(H)$
be disjoint and non-empty, and $S$ be an unrestricted
$(T_{1},T_{2})$-separator, such that $2c\cdot|S|\leq\min(|T_{1}|,|T_{2}|)$.
Then $H$ admits a canonical $c$-separation with respect to any given single-
faced embedding.

###### Proof.

Let us fix a single-faced embedding of $H$. Due to Lemma 7.18, it suffices to
show that $S$ is an unrestricted $(Q_{1},Q_{2})$-separator for some non-
crossing $Q_{1},Q_{2}\subseteq\partial(H)$, such that
$c\cdot|S|\leq\min(|Q_{1}|,|Q_{2}|)$.

Since $|T_{2}|\geq 2c\cdot|S|$, we can find two segments of $\partial(H)$ that
each have at least $c\cdot|S|$ vertices from $T_{2}$. Hence there exists a
canonical division $(Q^{\prime}_{1},Q^{\prime}_{2})$ of $\partial(H)$, such
that $c\cdot|S|\leq\min(|Q^{\prime}_{1}\cap T_{2}|,|Q^{\prime}_{2}\cap
T_{2}|)$. As the segments $(Q^{\prime}_{1},Q^{\prime}_{2})$ partition
$T_{1}\subseteq\partial(H)$ and $|T_{1}|\geq 2c\cdot|S|$, we have
$c\cdot|S|\leq|Q^{\prime}_{1}\cap T_{1}|$ or $c\cdot|S|\leq|Q^{\prime}_{2}\cap
T_{1}|$. Suppose this inequality holds for $Q^{\prime}_{i}$, $i\in\\{1,2\\}$.
Let $Q_{1}=Q^{\prime}_{i}\cap T_{1}$ and $Q_{2}=T_{2}\setminus
Q^{\prime}_{i}$. Since $Q_{1}\subseteq T_{1}$ and $Q_{2}\subseteq T_{2}$, the
set $S$ is an unrestricted $(Q_{1},Q_{2})$-separator. ∎

As the number of canonical divisions is quadratic in the size of the boundary,
we can find a canonical $c$-separation in polynomial time. Together with Lemma
7.19, this yields a 2-approximation algorithm for finding separations.

######  Lemma 7.20.

There is a polynomial-time algorithm that, given a single-faced boundaried
graph $H$ and an integer $c>0$, either correctly concludes that $H$ is
$(2c)$-inseparable or finds a canonical $c$-separation with respect to some
single-faced embedding of $H$.

###### Proof.

Let us start with constructing a single-faced embedding of $H$: it can be done
in polynomial time since it suffices to construct any plane embedding of the
closure of $H$ (see 3.13). By Lemma 7.19, a single-faced boundaried graph
either is $(2c)$-inseparable or admits a canonical $c$-separation with respect
to any single-faced embedding. We enumerate all $|\partial(H)|^{2}$-many
canonical divisions with respect to the constructed embedding. For each
canonical division $(T_{1},T_{2})$ we check if there exists $S$ such that
$(T_{1},T_{2},S)$ is a canonical $c$-separation. This task reduces to adding
two new vertices $t_{1},t_{2}$, adjacent respectively to $T_{1}$ and $T_{2}$,
and finding a minimum $(t_{1},t_{2})$-separator. If for some canonical
division $(T_{1},T_{2})$ we find $S$ such that
$c\cdot|S|\leq\min(|T_{1}|,|T_{2}|)$, we can return it: it must be an
inclusion-wise minimal unrestricted $(T_{1},T_{2})$-separator. Otherwise we
report that $H$ is $(2c)$-inseparable. ∎

Whenever we find a canonical $c$-separation we want to augment the boundary by
marking the vertices in the separator to split the given single-faced
boundaried graphs into two smaller single-faced boundaried graphs. We will add
the marked vertices to the solution preserver and we proceed recursively. A
priori this construction may mark a large number of vertices so we need some
kind of a measure to ensure that the constructed solution preserver cannot be
too large. Let $t$ be the size of the original boundary, $s$ be the size of
the separator, and $t_{1},t_{2}$ be the boundary sizes of the two smaller
single-faced boundaried graphs on which we recurse. Because we work with a
canonical $c$-separation we have that $c\cdot s\leq\min(t_{1},t_{2})$. This
implies that even when $t_{1}+t_{2}>t$ these numbers are in some sense
balanced. It turns out that it suffices to take $c=4$ to ensure that
$t_{1}^{2}+t_{2}^{2}<t^{2}$ which provides us with a measure that decreases in
each step and governs the number of possible recursive splits.

######  Lemma 7.21.

Let $s\geq 0,\,t>0,\,t_{1}>0,\,t_{2}>0$ be integers satisfying $t_{1}\geq
4s,t_{2}\geq 4s,\,t+2s\geq t_{1}+t_{2}$. Then $t^{2}\geq
t_{1}^{2}+t_{2}^{2}+s+1$.

###### Proof.

First consider the case $s=0$. We have $t\geq t_{1}+t_{2}>0$ so
$t^{2}\geq(t_{1}+t_{2})^{2}=t_{1}^{2}+t_{2}^{2}+2t_{1}t_{2}\geq
t_{1}^{2}+t_{2}^{2}+1$ because $t_{1},t_{2}$ are positive.

Now consider the case $s\geq 1$. As $t_{1}+t_{2}-2s\geq 6s\geq 0$, the
inequality $t\geq t_{1}+t_{2}-2s$ is maintained with both sides squared. We
enroll the squared expression, rearrange the terms, and bound $4s^{2}\geq
s+1$.

$\displaystyle t^{2}$ $\displaystyle\geq$
$\displaystyle(t_{1}+t_{2}-2s)^{2}=t_{1}^{2}+t_{2}^{2}+4s^{2}+2t_{1}t_{2}-4st_{1}-4st_{2}$
$\displaystyle=$ $\displaystyle
t_{1}^{2}+t_{2}^{2}+4s^{2}+{t_{1}}(t_{2}-4s)+{t_{2}}(t_{1}-4s)\geq
t_{1}^{2}+t_{2}^{2}+s+1.$

This concludes the proof. ∎

Now we show that when splitting a single-faced boundaried graph along a
canonical separation, we indeed obtain two smaller single-faced boundaried
graphs. We do not construct their embeddings directly but rather refer to the
convenient criterion from 3.13. Note that the definition of a single-faced
boundaried graph does not require it to be connected although connectivity
will later follow from being $c$-inseparable.

######  Lemma 7.22.

Let $H$ be a single-faced boundaried plane graph and let $(T_{1},T_{2},S)$ be
a canonical 4-separation. Then there exist sets $V_{1},V_{2}\subseteq V(H)$,
so that

  1. 1.

$(V_{1},V_{2})$ is a partition of $V(H)\setminus(\partial(H)\cup S)$,

  2. 2.

$N_{H}(V_{1})\subseteq T_{1}\cup S$ and $N_{H}(V_{2})\subseteq T_{2}\cup S$,

  3. 3.

$H\langle V_{1}\rangle,H\langle V_{2}\rangle$ are single-faced boundaried
graphs,

  4. 4.

$|N_{H}(V_{1})|^{2}+|N_{H}(V_{2})|^{2}+|S|+1\leq|\partial(H)|^{2}$.

Furthermore, the sets $V_{1},V_{2}$ can be found in polynomial time, when $H$
and $(T_{1},T_{2},S)$ are given.

###### Proof.

If $|S|=0$, then $T_{1},T_{2}$ are disconnected in $H$. We can group the
vertices of $H-\partial(H)$ into two sets $V_{1},V_{2}$, where
$N_{H}(V_{i})\subseteq T_{i}$ for $i\in\\{1,2\\}$. Since $T_{1},T_{2}$ are
non-empty by Definition 7.17, the numbers $0,|\partial(H)|,|T_{1}|,|T_{2}|$,
satisfy the prerequisites of Lemma 7.21, and so
$|N_{H}(V_{1})|^{2}+|N_{H}(V_{2})|^{2}+|S|+1\leq|\partial(H)|^{2}$. Since $H$
is single-faced, the same is easily seen to hold for $H\langle V_{1}\rangle$
and $H\langle V_{2}\rangle$.

Let us assume $|S|\geq 1$ for the rest of the proof. Consider the connected
components of $H-(\partial(H)\cup S)$. None of them can have neighbors in both
$T_{1}$ and $T_{2}$. Therefore we can group the vertices of
$V(H)\setminus(\partial(H)\cup S)$ into two sets $V_{1},V_{2}$, where $V_{i}$
is the union of the components with neighbors in $T_{i}\cup S$. If a component
has neighbors only in $S$, we can choose its allocation arbitrarily.

We are going to show that $H\langle V_{1}\rangle$ is single-faced—the proof
for $H\langle V_{2}\rangle$ is symmetric. Note that $N_{H}(V_{1})\subseteq
T_{1}\cup S$. Let $H_{0}$ be obtained from $H$ by adding two new vertices
$t_{1},t_{2}$ adjacent to respectively $T_{1}$ and $T_{2}$. Then $H_{0}$ is
planar and by Definition 7.17 $S$ is an inclusion-wise minimal
$(t_{1},t_{2})$-separator in $H_{0}$. Therefore, each vertex from $S$ is
adjacent to both $R_{H_{0}}(t_{1},S)$ and $R_{H_{0}}(t_{2},S)$. Let $H_{1}$ be
obtained from $H_{0}$ by

  1. 1.

adding an edge $t_{1}t_{2}$—this preserves planarity,

  2. 2.

contracting $R_{H_{0}}(t_{2},S)$ into $t_{2}$,

  3. 3.

contracting the edge $t_{1}t_{2}$.

The graph $H_{1}$ is planar and contains $H\langle V_{1}\rangle$ as a
boundaried subgraph $H_{1}\langle V_{1}\rangle$, plus one additional vertex
adjacent to every vertex in $T_{1}\cup S\supseteq N_{H_{1}}(V_{1})$. Also,
$H_{1}$ is a contraction of the closure $\widehat{H}$ of $H$, hence it is
planar and connected. Finally, let us remove from $H_{1}$ all the vertices of
$(T_{1}\cup S)\setminus N_{H_{1}}(V_{1})$, which trivially preserves planarity
and preserves connectivity through $t_{1}$. The resulting graph is isomorphic
to the closure of $H\langle V_{1}\rangle$. We have thus obtained that the
closure of $H\langle V_{1}\rangle$ is planar and connected so by 3.13 the
boundaried graph $H$ is single-faced.

Finally, let us prove the inequality. Since $(T_{1},T_{2},S)$ is a
4-separation, it holds that $\min(|T_{1}|,|T_{2}|)\geq 4\cdot|S|$. As
$|T_{1}\cup S|+|T_{2}\cup S|\leq|\partial(H)|+2\cdot|S|$, the numbers
$|S|,|\partial(H)|,|T_{1}\cup S|,|T_{2}\cup S|$ satisfy the prerequisites of
Lemma 7.21, and so $|T_{1}\cup S|^{2}+|T_{2}\cup
S|^{2}+|S|+1\leq|\partial(H)|^{2}$. Since $N_{H}(V_{i})\subseteq T_{i}\cup S$
for $i\in\\{1,2\\}$, the claim follows. ∎

We are ready to decompose a single-faced boundaried graph $H$ into boundaried
subgraphs which are single-faced and 8-inseparable. We define a single-faced
decomposition of $H$ as a boundaried decomposition $(Y,\mathcal{C})$ of $H$
(recall Definition 7.2), such that for each $C\in\mathcal{C}$ it holds that
$H\langle C\rangle$ is single-faced.

######  Lemma 7.23.

There is a polynomial-time algorithm that, given a single-faced boundaried
graph $H$, returns its single-faced decomposition $(Y,\mathcal{C})$, so that
$|Y|\leq|\partial(H)|^{2}$ and for each $C\in\mathcal{C}$ it holds that
$H\langle C\rangle$ is 8-inseparable.

###### Proof.

We decompose $H$ recursively starting with a single-faced decomposition
$(Y_{0},\mathcal{C}_{0})=(\emptyset,\\{V(H)\setminus\partial(H)\\})$. Let us
define the measure
$\mu(Y,\mathcal{C})=|Y|+\sum_{C\in\mathcal{C}}|N_{H}(C)|^{2}$. We have
$\mu(Y_{0},\mathcal{C}_{0})=|\partial(H)|^{2}$. We are going to refine the
single-faced decomposition until all the boundaried graphs $H\langle
C\rangle$, for $C\in\mathcal{C}$, are 8-inseparable, in each step decreasing
the measure $\mu$.

Let $(Y_{i},\mathcal{C}_{i})$ be a single-faced decomposition of $H$. We use
Lemma 7.20 with $c=4$ to either conclude that all $H\langle C\rangle$, for
$C\in\mathcal{C}$, are 8-inseparable (then the procedure terminates) or to
find a canonical 4-separation $(T_{1},T_{2},S)$ with respect to some single-
faced embedding of $H\langle C\rangle$ for some $C\in\mathcal{C}$. Now we
apply Lemma 7.22 to $H\langle C\rangle$ and $(T_{1},T_{2},S)$. We obtain sets
$V_{1},V_{2}\subseteq C\setminus S$, which form a partition of $C\setminus S$
and satisfy $N_{H}(V_{i})\subseteq N_{H}(C)\cup S$. Furthermore, each
$H\langle V_{i}\rangle$ is single-faced. We define a new single-faced
decomposition $(Y_{i+1},\mathcal{C}_{i+1})$, where $Y_{i+1}=Y_{i}\cup S$ and
$\mathcal{C}_{i+1}$ is obtained from $\mathcal{C}_{i}$ by replacing $C$ with
$V_{1}$ and $V_{2}$. Lemma 7.22 guarantees that
$|N_{H}(V_{1})|^{2}+|N_{H}(V_{2})|^{2}+|S|+1\leq|N_{H}(C)|^{2}$, therefore
$\mu(Y_{i+1},\mathcal{C}_{i+1})\leq\mu(Y_{i},\mathcal{C}_{i})-1$.

In each step the measure $\mu(Y_{i},\mathcal{C}_{i})$ decreases, so the
algorithm terminates after at most
$\mu(Y_{0},\mathcal{C}_{0})=|\partial(H)|^{2}$ steps. Let
$(Y_{\ell},\mathcal{C}_{\ell})$ be the final single-faced decomposition. We
have
$|Y_{\ell}|\leq\mu(Y_{\ell},\mathcal{C}_{\ell})\leq\mu(Y_{0},\mathcal{C}_{0})=|\partial(H)|^{2}$.
For each $C\in\mathcal{C}_{\ell}$, the boundaried graph $H\langle C\rangle$ is
single-faced (by the invariant of a single-faced decomposition) and
8-inseparable (because the algorithm has terminated). ∎

###  7.3 From inseparability to a solution preserver

In this section we show when $G\langle A\rangle$ is single-faced and
$c$-inseparable then the empty set forms an $\mathcal{O}(1)$-preserver for
$A$. In other words, for any solution $S$ each vertex from $S\cap A$ can be
replaced by $\mathcal{O}(1)$ vertices in $N_{G}(A)$. First we need several
observation about balls in the metric given by the weak radial distance.
Recall that for a plane graph $G$ and $u,v\in V(G)$ the weak radial distance
$w_{G}(u,v)$ is 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
either share an edge or lie on a common _interior_ face. Recall also that
$\mathcal{W}^{\ell}_{G}(X)$ denotes the ball of weak radial distance at most
$\ell$ around vertex set $X$ (see Figure 5 for an illustration). The reason
why we consider the weak radial distance instead of just the radial distance
(allowing to make paths also through the outer face) becomes evident in the
following proof.

######  Lemma 7.24.

Let $H$ be a single-faced boundaried plane graph and let $X\subseteq V(H)$.
Suppose that $T_{1},T_{2}\subseteq\partial(H)$ are non-crossing. If
$\mathcal{W}^{\ell}_{H}(X)$ is an unrestricted $(T_{1},T_{2})$-separator, then
there exists $X^{\prime}\subseteq\mathcal{W}^{\ell}_{H}(X)$ such that
$X^{\prime}$ is an unrestricted $(T_{1},T_{2})$-separator and
$|X^{\prime}|\leq(2\ell+1)\cdot|X|$.

###### Proof.

Let $H^{\prime\prime}$ be obtained from $H$ by adding a new vertex $t_{1}$
adjacent to all $t$ in $T_{1}$ and a new vertex $t_{2}$ adjacent to all $t$ in
$T_{2}$. Since $T_{1},T_{2}$ are non-crossing, $t_{1},t_{2}$ can be inserted
without modifying the embedding of $H$, within the outer face. Let us
abbreviate $X^{i}=\mathcal{W}^{i}_{H}(X)$. By the assumption, $X^{\ell}$ is a
$(T_{1},T_{2})$-separator in $H^{\prime\prime}$.

Consider a directed graph $R$ with vertex set $X^{\ell}$ defined as follows.
For each $x\in X^{i}\setminus X^{i-1}$, $i\in[\ell]$, we add a single edge
from $x$ to any vertex $y\in X^{i-1}$ such that $x,y$ share an interior face
or $xy\in E(H)$. Such vertex $y$ always exists by the definition of the metric
$w_{H}$. Since any $x\in(X^{\ell}\setminus X)$ has out-degree 1 in $R$, we can
define a function $r\colon(X^{\ell}\setminus X)\to X^{\ell}$ given by the arcs
of $R$.

Let $X^{\prime}\subseteq X^{\ell}$ be defined by the following procedure.
Initialize $X^{\prime}=X^{\ell}$ and while there exists $x\in
X^{\prime}\setminus X$ of in-degree 0 in $R$, such that $X^{\prime}\setminus
x$ is still a $(T_{1},T_{2})$-separator in $H^{\prime\prime}$, remove $x$ from
$X^{\prime}$ and from $R$. Let $C_{1},C_{2}$ be the connected components in
$H^{\prime\prime}-X^{\prime}$ containing $T_{1}$ and $T_{2}$, respectively.

We shall prove that $|X^{\prime}|\leq(2\ell+1)\cdot|X|$. Let $R_{x}\subseteq
X^{\prime}$ be the set of vertices $y\in X^{\prime}$ admitting a path $y\to x$
in $R$, including $x$. Fix $x\in X$ and suppose that there are 3 vertices
$x_{1},x_{2},x_{3}\in R_{x}$, each of in-degree 0 in $R$. Since none of these
3 vertices were removed during construction of $X^{\prime}$, each of them is
connected to both $C_{1}$ and $C_{2}$ in $H^{\prime\prime}$. Let $H_{0}$ be
obtained from $H^{\prime\prime}$ be adding a new vertex $u_{f}$ for each
interior face of $H$ and connecting $u_{f}$ to all vertices lying on this
face. Recall that $H^{\prime\prime}$ was obtained by adding two vertices
inside the outer face, so they do not interfere with inserting vertices within
interior faces. Therefore, $H_{0}$ is still a planar graph. Let $Y\subseteq
V(H_{0})$ be obtained from $R_{x}\setminus\\{x_{1},x_{2},x_{2}\\}$ by adding
all the adjacent face-vertices. Since $x$ and $r(x)$ either share an edge or
an interior face, the graph $H_{0}[Y]$ is connected. The vertices
$x_{1},x_{2},x_{3}$ and the sets $Y,C_{1},C_{2}$ form branch sets of a
$K_{3,3}$ minor in $H_{0}$, which is a contradiction to the assumption that
such vertices $x_{1},x_{2},x_{3}$ exist.

We infer that $R_{x}$ can contain at most 2 vertices of in-degree 0 in $R$,
and because the out-degree in $R$ is at most 1, we obtain that $|R_{x}\cap
X^{i}|\leq 2$ for $i\in[\ell]$ and so $|R_{x}|\leq 2\ell+1$. Since the sets
$R_{x}$ sum up to $X^{\prime}$, it follows that
$|X^{\prime}|\leq(2\ell+1)\cdot|X|$. ∎

Lemma 7.24 implies that for a set $X$ and integer $\ell$, the set
$\mathcal{W}_{H}^{\ell}(X)$ behaves similarly as a set of size
$(2\ell+1)\cdot|X|$ with respect to separating non-crossing subsets of the
boundary. The following lemma deepens this analogy: we show that in a
$c$-inseparable boundaried plane graph $H$, if the number of boundary vertices
is large compared to the size of some set $X$ and integer $\ell$, then there
must be unique component of $H-\mathcal{W}_{H}^{\ell}(X)$ that contains almost
all boundary vertices and all the other components have at most
$\mathcal{O}(c\cdot\ell\cdot d)$ of them.

######  Lemma 7.25.

Let $H$ be a $c$-inseparable single-faced $r$-boundaried plane graph, $\ell$
be a positive integer, and let $X\subseteq V(H)$ be of size $d$. Suppose that
$3c\cdot(2\ell+1)\cdot d\leq r$. Then there is a single connected component in
$H-\mathcal{W}_{H}^{\ell}(X)$ containing at least $r-c\cdot(2\ell+1)\cdot d$
vertices from $\partial(H)$.

###### Proof.

Let $X^{\prime}=\mathcal{W}_{H}^{\ell}(X)$. We will consider two cases
depending on the maximal number of boundary vertices in a single component of
$H-X^{\prime}$. First let us assume that each such component contains at most
$c\cdot(2\ell+1)\cdot d$ elements from $\partial(H)$ or $\partial(H)\subseteq
X^{\prime}$. Consider the cyclic ordering of $\partial(H)$ given by the
single-faced embedding. Let us choose an arbitrary element
$t_{1}\in\partial(H)$ and fix the ordering $t_{1},\dots,t_{r}$ of
$\partial(H)$ to start at this element.

Let $S_{i}=\\{t_{i}\\}$ if $t_{i}\in X^{\prime}$ and otherwise let
$S_{i}=R_{H}(t_{i},X^{\prime})\cap\partial(H)$ be the subset of $\partial(H)$
reachable from $t_{i}$ in $H-X^{\prime}$. Let $j$ be the smallest index for
which $|\bigcup_{i=1}^{j}S_{i}|\geq c\cdot(2\ell+1)\cdot d$. By assumption it
holds that $|S_{j}|\leq c\cdot(2\ell+1)\cdot d$, so we have
$|\bigcup_{i=1}^{j}S_{i}|\leq 2c\cdot(2\ell+1)\cdot d$. We define
$T_{1}=\\{t_{i}\mid i\in[j]\\}$ and $T_{2}=T\setminus\bigcup_{i=1}^{j}S_{i}$.
Then $T_{1},T_{2}$ are disjoint, non-crossing, and $X^{\prime}$ is an
unrestricted $(T_{1},T_{2})$-separator. Lemma 7.24 guarantees that there
exists an unrestricted $(T_{1},T_{2})$-separator $X^{\prime\prime}\subseteq
X^{\prime}$ of size at most $(2\ell+1)\cdot d$. Note that for each $i\in[j]$
satisfying $t_{i}\not\in X^{\prime}$, the set $S_{i}$ is contained in a single
connected component of $H-X^{\prime}$, hence it is also contained in a single
connected component of $H-X^{\prime\prime}$ which is disjoint from $T_{2}$.
Therefore $X^{\prime\prime}$ is also an unrestricted
$(\bigcup_{i=1}^{j}S_{i},T_{2})$-separator. By the construction,
$|\bigcup_{i=1}^{j}S_{i}|\in[c\cdot(2\ell+1)\cdot d,\,2c\cdot(2\ell+1)\cdot
d]$. The lower bound $3c\cdot(2\ell+1)\cdot d\leq r$ implies that
$|T_{2}|=r-\bigcup_{i=1}^{j}S_{i}\geq c\cdot(2\ell+1)\cdot d$, which
contradicts the assumption that $H$ is $c$-inseparable.

Suppose now that there exists a connected component $C$ of $H-X^{\prime}$ so
that $|C\cap\partial(H)|>c\cdot(2\ell+1)\cdot d$. Let $T_{1}=\\{t\\}$ for an
arbitrary $t\in C\cap\partial(H)$ and $T_{2}=\partial(H)\setminus C$. Clearly
$X^{\prime}$ is an unrestricted $(T_{1},T_{2})$-separator and $T_{1},T_{2}$
are non-crossing. By Lemma 7.24 we obtain an unrestricted
$(T_{1},T_{2})$-separator $X^{\prime\prime}$ such that
$|X^{\prime\prime}|\leq(2\ell+1)\cdot d$ and $X^{\prime\prime}\subseteq
X^{\prime}$. The latter property implies that $X^{\prime\prime}$ is also an
unrestricted $(\partial(H)\cap C,T_{2})$-separator. Since $H$ is
$c$-inseparable, we have $|T_{2}|<c\cdot(2\ell+1)\cdot d$. Therefore
$|C\cap\partial(H)|=r-|T_{2}|>r-c\cdot(2\ell+1)\cdot d$, and so $C$ is the
desired component. ∎

When $G\langle A\rangle$ is single-faced and $c$-inseparable, then for a
solution $S$ in $G$ we consider the set $\mathcal{W}_{G\langle
A\rangle}^{3}(S\cap A)$ after fixing some single-faced embedding of $G\langle
A\rangle$. This will allow us to construct 3 connected separators between any
vertex $x\in S\cap A$ and the large component from Lemma 7.25 in order to
argue for their irrelevance in the solution. To construct such separators we
rely on the following proposition. A plane triangulation is a plane graph with
every face being incident to exactly three vertices. Recall that when using
the word _separator_ without any adjective, we refer to a _restricted_
separator that does not intersect the elements being separated.

######  Proposition 7.26 ([MT01, Prop. 8.2.3]).

Let $u$ and $v$ be distinct vertices in a plane triangulation $G$. If $S$ is a
minimal $(u,v)$-separator, then $G[S]$ is an induced, non-facial cycle.

We remark that this result has been originally formulated for sets whose
removal disconnect the graph but the same argument holds for minimal
$(u,v)$-separators.

######  Lemma 7.27.

Let $G$ be a connected plane graph, $x\in X\subseteq V(G)$, and $v\in
V(G)\setminus\mathcal{W}_{G}^{\ell}(X)$ for some $\ell\in\mathbb{N}$. Then
there exists either a vertex $y\in\mathcal{W}_{G}^{\ell}(X)\setminus X$ which
separates $v$ from $x$ or $\ell$ vertex-disjoint subsets of
$\mathcal{W}_{G}^{\ell}(X)\setminus X$ forming a sequence of nested
$(v,x)$-separators. In the latter case, each separator is inclusion-wise
minimal and either induces a cycle or a path with both endpoints on the outer
face.

###### Proof.

Consider the block-cut tree of $G$ and the sequence of vertices
$u_{1},u_{2},\dots,u_{m}$, where $u_{1}=x$, $u_{m}=v$, and
$u_{2},\dots,u_{m-1}$ are the articulation points between $x$ and $v$ in $G$.
If $x,v$ belong to the same biconnected component, then $m=2$. More precisely,
$\\{u_{i}\\}$ is a $(v,x)$-separator for $i\in[2,m-1]$ and there are no more
singleton $(v,x)$-separators in $G$ apart from those in the sequence. Let $j$
be the highest index such that $u_{j}\in X$. Note that $j$ is well defined, as
$u_{1}=x\in X$, and furthermore $j\leq m-1$. If
$u_{j+1}\in\mathcal{W}_{G}^{\ell}(X)$, then in particular $u_{j+1}\neq v$ and
we can set $y=u_{j+1}$ to satisfy the claim. Otherwise, let $B\subseteq V(G)$
be the biconnected component of $G$ containing $u_{j}$ and $u_{j+1}$. If
suffices to show that the claim holds for $x^{\prime}=u_{j}\in X$ and
$v^{\prime}=u_{j+1}\not\in\mathcal{W}_{G}^{\ell}(X)$, therefore we have
reduced the problem to the case when $x,v$ lie in a single biconnected
component $B$ of $G$. Let us focus on this case from now on.

Let the graph $G_{B}^{\prime}$ be obtained from $B$ by

  1. 1.

adding a new vertex $u_{f}$ in the center of each face $f$ in $B$,

  2. 2.

for each new vertex $u_{f}$, connecting it to all the vertices from $B$ lying
on the face $f$.

Let us note several properties of $G_{B}^{\prime}$. Let the set $U_{0}$
consist of the new single vertex put in place of the outer face of $G$, if
that vertex belongs to $V(G_{B}^{\prime})$, or be empty if the outer face is
not adjacent to any vertex of $B$.

  1. 1.

If $u,v\in V(B)$ and $uv\in E(G_{B}^{\prime})$, then $uv\in E(G)$.

  2. 2.

If $S\subseteq V(B)$ is a $(v,x)$-separator in $G_{B}^{\prime}-U_{0}$, then
$S$ is a $(v,x)$-separator in $G$.

  3. 3.

Since $B$ is a biconnected component of $G$, each face of $B$ forms a cycle
and thus $G_{B}^{\prime}$ is a plane triangulation.

  4. 4.

Let $S_{j}=\\{u\in V(B)\mid w_{G}(X,u)=j\\}$. Then $S_{j}\cup U_{0}$ is a
$(v,x)$-separator in $G_{B}^{\prime}$ for $j\in[\ell]$.

The last property requires a short justification. Suppose there exists a
$(v,x)$-path $P^{\prime}$ in $G_{B}^{\prime}-(S_{j}\cup U_{0}$) and let $P$ be
the sequence of vertices from $V(B)$ occurring on $P^{\prime}$. Since
$P^{\prime}$ does not use the vertex corresponding to the outer face, each
pair of consecutive vertices $y_{i},y_{j}$ from $P$ share an interior face,
thus $|w_{G}(X,y_{i})-w_{G}(X,y_{j})|\leq 1$. Since $w_{G}(X,x)=0$ and
$w_{G}(X,v)>\ell\geq j$, $P$ must contain a vertex from $S_{j}$; a
contradiction.

We shall now show that for each $j\in[\ell]$ there exists a set
$S^{\prime}_{j}\subseteq S_{j}$ such that $G[S^{\prime}_{j}]$ is connected and
$S^{\prime}_{j}\cup U_{0}$ is a $(v,x)$-separator in $G_{B}^{\prime}$ of one
of the two desired forms. Let $S^{0}_{j}$ be an inclusion-wise minimal subset
of $S^{\prime}_{j}\cup U_{0}$ which is still a $(v,x)$-separator in
$G_{B}^{\prime}$. Since $G_{B}^{\prime}$ is a plane triangulation, Proposition
7.26 applies and we get that $G_{B}^{\prime}[S^{0}_{j}]$ is an induced cycle.
If $S^{0}_{j}\cap U_{0}=\emptyset$, then $S^{0}_{j}$ induces a cycle in $G$.
Otherwise, recall that $U_{0}$ contains at most one element representing the
outer face. Removing a single vertex from a cycle turns it into a path, hence
$G_{B}^{\prime}[S^{0}_{j}\setminus U_{0}]=G[S^{0}_{j}\setminus U_{0}]$ induces
a path. Since the vertex in $U_{0}$ was placed in the outer face, the path has
both endpoints on the outer face of $G$. Note that
$S^{\prime}_{j}=S^{0}_{j}\setminus U_{0}$ is a $(v,x)$ separator in
$G_{B}^{\prime}-U_{0}$. Because $S^{\prime}_{j}\subseteq S_{j}\subseteq V(B)$,
we obtain that $S^{\prime}_{j}$ is the desired $(v,x)$-separator in $B$, and
thus in $G$.

These separators are clearly vertex-disjoint and contained in
$\mathcal{W}_{G}^{\ell}(X)\setminus X$. The fact that they can be ordered into
a nested sequence follows from their connectivity and minimality. For $i\neq
j$, the set $S^{\prime}_{i}$ must be fully contained in some component of
$G-S^{\prime}_{j}$, precisely either in $R_{G}(x,S^{\prime}_{j})$ or in
$R_{G}(v,S^{\prime}_{j})$. From minimality we get that each vertex of
$S^{\prime}_{j}$ is adjacent to both $R_{G}(x,S^{\prime}_{j})$ and
$R_{G}(v,S^{\prime}_{j})$. In the first case $S^{\prime}_{i}$ must separate
$x$ from $S^{\prime}_{j}$ and the second case it must separate $v$ from
$S^{\prime}_{j}$. Therefore, either $R_{G}(x,S^{\prime}_{i})\subseteq
R_{G}(x,S^{\prime}_{j})$ or $R_{G}(x,S^{\prime}_{j})\subseteq
R_{G}(x,S^{\prime}_{i})$. ∎

Note that even though the proof gives a natural order of separators
$(S^{\prime}_{i})_{i=1}^{\ell}$, they might be nested in a different order.
This is because we require $S^{\prime}_{i}\subseteq\\{u\in B\mid
w_{G}(X,u)=i\\}$, not $S^{\prime}_{i}\subseteq\\{u\in B\mid w_{G}(x,u)=i\\}$.
This is necessary to guarantee that $S^{\prime}_{i}\cap X=\emptyset$, which
will be an important property in the proof of Lemma 7.29.

When given a single-faced embedding of a $c$-inseparable graph $G\langle
A\rangle$ and a solution $S$ in $G$, we are going to remove $S\cap A$ from the
solution and replace it with some subset of $N_{G}(A)$, of size comparable to
$|S\cap A|$. As the new solution removes some vertices from $N_{G}(A)$ we need
to ensure that this cannot disconnect the separators constructed in Lemma
7.27.

######  Lemma 7.28.

Let $G$ be a connected plane graph, $u,v\in V(G)$, and $S\subseteq V(G)$ be a
minimal $(u,v)$-separator such that $G[S]$ either induces a cycle or a path
with both endpoints on the outer face. If $Y\subseteq V(G)\setminus\\{u,v\\}$
is a subset of vertices lying on the outer face of $G$ and $S\not\subseteq Y$,
then $S\setminus Y$ is a connected $(u,v)$-separator in $G-Y$.

###### Proof.

It is clear that $S\setminus Y$ is a $(u,v)$-separator in $G-Y$ and we only
need to show that it is connected. We will rely on the observation that, since
$S$ is minimal, each vertex $s\in S$ is adjacent to both $R_{G}(u,S)$ and
$R_{G}(v,S)$. Let $G^{\prime}$ be obtained from $G$ by adding a new vertex $f$
adjacent to all vertices in $Y$. Since they lie on the outer face of $G$, the
graph $G^{\prime}$ is planar.

Suppose that $S$ induces a cycle and that $S\setminus Y$ is not connected.
Then there exist vertices $y_{1},y_{2}\in Y\cap S$ and a partition of
$S\setminus\\{y_{1},y_{2}\\}$ into connected vertex sets $S_{1},S_{2}$ so that
each edge set $E_{G}(y_{i},S_{j})$ for $i,j\in\\{1,2\\}$ is non-empty. The
sets $R_{G}(u,S),S_{1}\cup R_{G}(v,S),S_{2},\\{y_{1},f\\},\\{y_{2}\\}$ form
branch sets of a $K_{5}$-minor model in $G^{\prime}$, which gives a
contradiction.

Now suppose that $S$ induces a path with both endpoints on the outer face and
that $S\setminus Y$ is not connected. Then there exists vertex $y\in Y\cap S$
and a partition of $S\setminus\\{y\\}$ into connected vertex sets
$S_{1},S_{2}$ so that each of them contains a vertex lying on the outer face.
The sets $R_{G}(u,S),R_{G}(v,S),\\{f\\},S_{1},S_{2},\\{y\\}$ form branch sets
of a $K_{3,3}$-minor model in $G^{\prime}$, which again leads to a
contradiction. ∎

We are ready to show that when $G\langle A\rangle$ is single-faced and
8-inseparable then $\emptyset$ is an $\alpha$-preserver for $A$, where
$\alpha=3\cdot 8\cdot 7=168$. We first fix a single-faced embedding of
$G\langle A\rangle$. When $S$ is a solution in $G$ and $X=S\cap A$, we
consider terminal pairs separated by $\mathcal{W}_{G\langle A\rangle}^{3}(X)$
and use Lemma 7.25 to identify a subset of $N_{G}(A)$ of size comparable to
$|X|$, which intersects all the separated terminal pairs. We can add it to
$S$, creating a larger solution $S^{\prime}$ (see Figure 5). We need to argue
that vertices from $X$ can be now removed from $S^{\prime}$ without
invalidating the solution. To this end, we use Lemma 7.27 to construct 3
nested connected separators between any $x\in X$ and $N_{G}(A)\setminus
S^{\prime}$ in $G-(S^{\prime}\setminus\\{x\\})$ which allows us to use the
planarity criterion from Lemma 3.17.

Figure 5: An illustration of the proof of Lemma 7.29. In the plane embedding
of $G\langle A\rangle$ the boundary vertices from $N_{G}(A)$ are drawn in
blue; they lie on the outer face. The red squares represent vertices
$X=\\{x,y,z\\}$ in the intersection of a solution $S$ and the set $A$. The
sets $\mathcal{W}_{G\langle A\rangle}^{1}(X)$, $\mathcal{W}_{G\langle
A\rangle}^{2}(X)$, $\mathcal{W}_{G\langle A\rangle}^{3}(X)$ are sketched with
shades of gray so, e.g., the vertices incident to the dark gray faces belong