# Simpler and faster algorithms for detours in planar digraphs ††thanks: This
work is a part of project BOBR (KM, MP, MS) that has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No. 948057). M. Hatzel was
supported by the Federal Ministry of Education and Research (BMBF) and by a
fellowship within the IFI programme of the German Academic Exchange Service
(DAAD).

Meike Hatzel National Institute of Informatics, Tokyo, Japan
<EMAIL_ADDRESS>Konrad Majewski Institute of Informatics, University
of Warsaw, Poland<EMAIL_ADDRESS>Michał Pilipczuk Institute of
Informatics, University of Warsaw, Poland<EMAIL_ADDRESS>Marek Sokołowski Institute of Informatics, University of Warsaw, Poland
<EMAIL_ADDRESS>
###### Abstract

In the Directed Detour problem one is given a digraph $G$ and a pair of
vertices $s$ and $t$, and the task is to decide whether there is a directed
simple path from $s$ to $t$ in $G$ whose length is larger than
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}$.
The more general parameterized variant, Directed Long Detour, asks for a
simple $s$-to-$t$ path of length at least
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+k$,
for a given parameter $k$. Surprisingly, it is still unknown whether Directed
Detour is polynomial-time solvable on general digraphs. However, for planar
digraphs, Wu and Wang [Networks, ’15] proposed an $\mathcal{O}(n^{3})$-time
algorithm for Directed Detour, while Fomin et al. [STACS 2022] gave a
$2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$-time fpt algorithm for Directed
Long Detour. The algorithm of Wu and Wang relies on a nontrivial analysis of
how short detours may look like in a plane embedding, while the algorithm of
Fomin et al. is based on a reduction to the $3$-Disjoint Paths problem on
planar digraphs. This latter problem is solvable in polynomial time using the
algebraic machinery of Schrijver [SIAM J. Comp., ’94], but the degree of the
obtained polynomial factor is huge.

In this paper we propose two simple algorithms: we show how to solve, in
planar digraphs, Directed Detour in time $\mathcal{O}(n^{2})$ and Directed
Long Detour in time $2^{\mathcal{O}(k)}\cdot n^{4}\log n$. In both cases, the
idea is to reduce to the $2$-Disjoint Paths problem in a planar digraph, and
to observe that the obtained instances of this problem have a certain
topological structure that makes them amenable to a direct greedy strategy.

20(-1.9, 3.1)  20(-2.15, 3.5)  20(-1.8, 4.8)

##  1 Introduction

The complexity status of Directed Detour is arguably one of the most
tantalizing open questions within the area of graph algorithms. The problem
asks to decide, for a given digraph $G$ and two terminals $s$ and $t$, whether
there is a simple path in $G$ from $s$ to $t$ that is not the shortest — has
length strictly larger than
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}$.
It is still unknown whether this problem is polynomial-time solvable on
general digraphs. See the work of Fomin et al. [3] for a discussion of
relevant literature.

Given this state of the affairs, it is interesting to study Directed Detour on
restricted classes of digraphs, in hope for finding more positive results or
useful insight. In this vein, a particularly well-motivated idea is to
consider the class of planar digraphs. The reason for this is that in planar
digraphs, the $k$-Disjoint Paths problem — decide the existence of disjoint
directed paths linking given $k$ pairs of terminals — is polynomial-time
solvable for every fixed $k$ [8], and even fixed-parameter tractable when
parameterized by $k$ [2]. This is not the case in general digraphs, where the
problem is NP-hard already for $k=2$ [5]. This can be used for Directed
Detour. Namely, Fomin et al. [3] showed that the more general parameterized
version of the problem — Directed Long Detour, where we look for a simple
$s$-to-$t$ path of length at least
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+k$,
for a given parameter $k$ — can be reduced (with a $2^{\mathcal{O}(k)}\cdot
n^{\mathcal{O}(1)}$ multiplicative overhead in the complexity) to $3$-Disjoint
Paths, which can be solved in polynomial time in planar digraph using the
algorithm of Schrijver [8]. This of course applies also to the basic Directed
Detour problem by setting $k=1$, but even earlier Wu and Wang [9] gave a
direct $\mathcal{O}(n^{3})$-time algorithm for this case.

While the reduction of Fomin et al. [3] is actually quite simple, the
algorithm of Schrijver [8] for $3$-Disjoint Paths in planar digraphs is not,
as it relies on an involved algebraic framework. In particular, the degree of
the polynomial bounding the running time is at least a two-digit number. On
the other hand, the cubic algorithm of Wu and Wang [9] is also quite
complicated and relies on an analysis of different planar configurations that
may occur.

In this work we propose two simple algorithms: one for Directed Detour and one
for Directed Long Detour, both in planar digraphs. These are summarized below.

######  Theorem 1.1.

Directed Detour in planar digraphs can be solved in time $\mathcal{O}(n^{2})$.

######  Theorem 1.2.

Directed Long Detour in planar digraphs can be solved in time
$2^{\mathcal{O}(k)}\cdot n^{4}$ by a Monte Carlo algorithm, or
deterministically in time $2^{\mathcal{O}(k)}\cdot n^{4}\log n$.

The main idea in the proof of Theorem 1.1 is to perform a reduction to the
$2$-Disjoint Paths problem, roughly similarly as in the work of Fomin et al.
[3]. However, we observe that if this reduction is performed carefully, then
one essentially obtains an instance of $2$-Disjoint Paths where three out of
four terminals lie on one face, say the outer face. Such instances can be
solved very easily: one of the paths — the one with both terminals on the
outer face — can be chosen greedily so that it leaves the maximum possible
space for the other path. Then the other path can be found by a simple
reachability check.

For Theorem 1.2, as in Fomin et al. [3], we use the result of Bezáková et al.
[1] that the Exact Directed Long Detour problem — finding a shortest
$s$-to-$t$ path of length exactly
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+k$
— can be solved in time $2^{\mathcal{O}(k)}\cdot n^{2}$, even on general
digraphs. This allows us to assume, when solving Directed Long Detour, that
there are no $s$-to-$t$ paths of length between
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+k$
and
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+3k$.
Having this assumption, the proof of Theorem 1.2 proceeds by expanding the
basic idea behind Theorem 1.1 with color coding.

We believe that compared to [3, 9], our algorithms provide a simpler
explanation for the tractability of Directed (Long) Detour in planar digraphs.
While we do not expect that the gained insight will be directly applicable to
the case of general digraphs, we hope that it might be a better starting point
for generalizations to less restrictive topological graph classes, for
instance to digraphs of bounded genus or digraphs whose underlying undirected
graphs exclude a fixed minor.

##  2 Preliminaries

### Graphs.

In this paper we consider planar directed graphs $G=(V(G),E(G))$. For the
purposes of our problem, we can assume that the input graphs are simple, that
is, they do not have self-loops or multiple arcs connecting two vertices in
the same direction. Moreover, we assume that $G$ is weakly connected, that is,
the underlying undirected graph is connected. For convenience, we set
$n=|V(G)|$ and $m=|E(G)|$. Since $G$ is planar and simple, we have that
$m\in\mathcal{O}(n)$.

Given an arc $e=uv\in E(G)$, we say that $u$ is the _tail_ of $e$ and $v$ is
the _head_ of $e$. Here, we consider $e$ incident to both $u$ and $v$. A
sequence $v_{1}v_{2}\dots v_{k}$ of vertices is called a  _walk_ in $G$ if for
each $i\in\\{1,\dots,k-1\\}$, $v_{i}v_{i+1}$ is an arc in $G$. The vertex
$v_{1}$ is called the _origin_ of the walk, while $v_{k}$ is its
_destination_. If the vertices of a walk are pairwise different, the walk is a
_path_. Given two walks $W_{1}$, $W_{2}$, if the destination of $W_{1}$
coincides with the origin of $W_{2}$, then we define $W_{1}\circ W_{2}$ as the
concatenation of both walks. The _length_ of a path $P$, denoted
$\mathchoice{\mathsf{length}\\!\left(P\right)}{\mathsf{length}\\!\left(P\right)}{\mathsf{length}\left(P\right)}{\mathsf{length}\left(P\right)}$,
is the number of arcs it contains. Given a path $P$ and two of its vertices
$x$ and $y$, we denote by $P[x\to y]$ the subpath of $P$ which starts at $x$,
goes along the arcs of $P$, and ends in $y$.

Given a pair of vertices $u,v\in V(G)$, the _distance_ from $u$ to $v$ in $G$
is the length of the shortest $u$-to-$v$-path in $G$ and is denoted by
$\mathchoice{\mathsf{dist}_{G}\\!\left(u,v\right)}{\mathsf{dist}_{G}\\!\left(u,v\right)}{\mathsf{dist}_{G}\left(u,v\right)}{\mathsf{dist}_{G}\left(u,v\right)}$.
If there is no directed path from $u$ to $v$ in $G$, we put
$\mathchoice{\mathsf{dist}_{G}\\!\left(u,v\right)}{\mathsf{dist}_{G}\\!\left(u,v\right)}{\mathsf{dist}_{G}\left(u,v\right)}{\mathsf{dist}_{G}\left(u,v\right)}=+\infty$.
If the graph $G$ is known from the context, we may omit $G$ from the notation
and simply write
$\mathchoice{\mathsf{dist}\\!\left(u,v\right)}{\mathsf{dist}\\!\left(u,v\right)}{\mathsf{dist}\left(u,v\right)}{\mathsf{dist}\left(u,v\right)}$.

### Plane embeddings.

Given a planar graph $G$, its embedding into the plane is a mapping of the
vertices of $G$ to pairwise distinct points in the plane and the arcs of $G$
to plane curves, so that:

  * •

each arc $uv\in E(G)$ is mapped to a plane curve whose endpoints coincide with
the images of $u$ and $v$, and such that no other vertex of $G$ is mapped to a
point on the curve; and

  * •

the images of the edges of $G$ are pairwise internally disjoint.

A  _plane graph_ is a planar graph together with a fixed embedding of the
graph into the plane. Such an embedding splits the plane in a number of
regions, called _faces_. One of the faces is unbounded and called the _outer
face_. Given a face $F$, its boundary $\partial F$ can be described as a
cyclic sequence of arcs bounding $F$ (assuming $G$ is connected). If $\partial
F$ is isomorphic to a simple polygon (ignoring the orientations of the arcs),
we say that $F$ is _simple_.

For algorithmic purposes, we represent planar embeddings combinatorially: each
vertex $v$ of the graph stores the anti-clockwise ordering of all arcs of $G$
incident to $v$. Given a planar graph $G$, its combinatorial embedding can be
computed in time linear with respect to the size of the graph [6]. Note that
the combinatorial embedding uniquely determines the faces of the planar graph,
however, it does not designate the outer face of the embedding. Hence, in our
algorithms, we may elect any face to be the outer face.

### Comparing paths in plane graphs.

Let $G$ be a plane graph and $F$ be its outer face. Assume that $F$ is simple.
We say that a path $P$ in $G$ is _$v$ -grounded (with respect to $F$)_ if its
origin $v$ is a vertex of $F$. Moreover, we say that $P$ is _$(v,w)$ -grounded
(with respect to $F$)_ if both its origin $v$ and its destination $w$ are
vertices of $F$. We now present two ways to compare (doubly) grounded paths in
$G$. We note that the following definitions are standard.

######  Definition 2.1.

Assume that $P_{1}$ and $P_{2}$ are two different $v$-grounded paths with
respect to a face $F$ in a plane graph $G$. We say that $P_{1}$ is
_lexicographically left of_ $P_{2}$ (denoted $P_{1}\prec_{\mathrm{lex}}P_{2}$)
if one of the following conditions holds:

  * •

$P_{1}$ is a prefix of $P_{2}$; or

  * •

consider a plane graph $G_{v}$ created by taking $G$, together with its planar
embedding, and adding a fresh vertex $v^{\prime}$ and a fresh arc
$v^{\prime}v$, mapped to the plane so that the image of $v^{\prime}$ is placed
outside of $F$ (i.e., so that $v^{\prime}$ is not enclosed by the boundary of
$F$). Let $P^{\prime}_{1}$ and $P^{\prime}_{2}$ be paths in $G_{v}$,
constructed by prepending $v^{\prime}$ to $P_{1}$ and $P_{2}$, respectively.
Let $q$ be the last vertex of the longest common prefix of $P^{\prime}_{1}$
and $P^{\prime}_{2}$, $p$ be the vertex preceding $q$ on the common prefix,
and $r_{1}\neq r_{2}$ be the vertices succeeding $q$ on $P^{\prime}_{1}$ and
$P^{\prime}_{2}$, respectively. Then, the arcs $pq$, $qr_{1}$ and $qr_{2}$ are
embedded clockwise in this order around $q$.

$F$$v$$w$$P_{1}$$P_{2}$$P_{3}$ (a)

$F$$v$$w$$P$ (b)

Figure 1: 1(a) Three $(v,w)$-grounded paths. We have
$P_{1}\prec_{\mathrm{lex}}P_{2}\prec_{\mathrm{lex}}P_{3}$,
$P_{1}\prec_{\mathrm{top}}P_{2}$, $P_{1}\prec_{\mathrm{top}}P_{3}$, but
$P_{2}\not\prec_{\mathrm{top}}P_{3}$. 1(b) A $(v,w)$-grounded path $P$ and its
left area $\Gamma_{\mathsf{L}}(P)$ (filled in blue).

Intuitively, $P_{1}\prec_{\mathrm{lex}}P_{2}$ if at the end of the common
prefix of $P_{1}$ and $P_{2}$, the path $P_{1}$ terminates or branches off
left of $P_{2}$ (Figure 1(a)). Observe that $\prec_{\mathrm{lex}}$ induces a
linear order on all paths grounded at a vertex $v\in V(F)$. Thus, given any
vertex $w\in V(G)$ reachable from $v$ in $G$, we define $L_{vw}$, the
_lexicographically leftmost_ path from $v$ to $w$, as the unique minimal path
from $v$ to $w$ with respect to $\prec_{\mathrm{lex}}$. Given a combinatorial
embedding of $G$, we can compute the lexicographically leftmost path from $v$
to $w$ in time $\mathcal{O}(n)$: it suffices to run a depth-first search of
$G$ in which each vertex considers all its neighbors in the left-to-right
order.

We follow with a more restrictive way of comparing paths in $G$. Given a
$(v,w)$-grounded path $P$, we define the _area left of $P$_, denoted
$\Gamma_{\mathsf{L}}(P)$, as the region of the plane whose anti-clockwise
boundary is the closed walk defined as the concatenation of $P$ and the anti-
clockwise segment of the boundary of $F$ from $w$ to $v$ (Figure 1(b)). Note
that the interior of $\Gamma_{\mathsf{L}}(P)$ may be disconnected if $P$
internally intersects the boundary of $F$.

######  Definition 2.2.

Given two $(v,w)$-grounded paths $P_{1}$ and $P_{2}$, we say that $P_{1}$ is
_topologically left of_ $P_{2}$ (denoted $P_{1}\prec_{\mathrm{top}}P_{2}$) if
$\Gamma_{\mathsf{L}}(P_{1})\subsetneq\Gamma_{\mathsf{L}}(P_{2})$.

Note that if $P_{1}\prec_{\mathrm{top}}P_{2}$, then
$P_{1}\prec_{\mathrm{lex}}P_{2}$. Thus, $\prec_{\mathrm{top}}$ is a partial
order on the set of all $(v,w)$-grounded paths, and $\prec_{\mathrm{lex}}$
restricted to those paths is a linear extension of $\prec_{\mathrm{top}}$. It
is straightforward to observe that the lexicographically leftmost path from
$v$ to $w$ — the minimum $(v,w)$-grounded path in $\prec_{\mathrm{lex}}$ — is
also the unique minimum $(v,w)$-grounded path in $\prec_{\mathrm{top}}$. So if
both $v$ and $w$ lie on $F$, we call $L_{vw}$ simply the _leftmost path_ from
$v$ to $w$.

Analogously, we define the _(lexicographically) rightmost path_ from $v$ to
$w$, denoted $R_{vw}$, and the _area right of_ a $(v,w)$-grounded path $P$,
denoted $\Gamma_{\mathsf{R}}(P)$. Note that each $(v,w)$-grounded path $P$
splits the graph into two parts: the area $\Gamma_{\mathsf{L}}(P)$ left of $P$
and the area $\Gamma_{\mathsf{R}}(P)$ right of $P$, with both areas
intersecting only at $P$.

### Simplifying the outer face.

Both the lexicographical and the topological comparisons of grounded paths
require the outer face $F$ of a plane graph $G$ to be simple. However, this
precondition might not be satisfied in the setting of our problem. To
alleviate this issue, we show how to simplify the outer face by adding two
directed arcs to the plane graph.

Let $u$ and $v$ be two vertices of $F$. The _$(u,v)$ -simplification_ of the
outer face in $G$, denoted $\mathsf{Simplify}(G,u,v)$, is the digraph obtained
from $G$ by adding two arcs $f_{1}$, $f_{2}$, each from $u$ to $v$. Both arcs
are embedded in the outer face $F$ of $G$, so that the outer face of
$\mathsf{Simplify}(G,u,v)$ is bounded by $f_{1}$ and $f_{2}$ (see Figure 2).
Thus, the outer face of $\mathsf{Simplify}(G,u,v)$ is simple and contains two
vertices, $u$ and $v$. We remark that $\mathsf{Simplify}(G,u,v)$ is not
necessarily a simple digraph; however, this does not pose a problem since
after the simplification, the number of edges of the graph is still linearly
bounded in the number of vertices of the graph.

$u$$v$

$u$$v$$f_{1}$$f_{2}$

Figure 2: An example plane digraph (left) and its $(u,v)$-simplification
(right).

### Cutting arcs of plane graphs.

We finally describe an operation on plane graphs that introduces new vertices
to the outer face $F$ of the embedding. Assume that $F$ is simple. Take two
vertices $u\in V(F)$, $v\notin V(F)$, both incident to an arc $e\in E(G)$. An
operation of _cutting the graph along_ $e$ produces a new graph $G_{e}$ which
is the result of the following process (see Figure 3):

  1. 1.

Enumerate all arcs incident to $u$ in anti-clockwise order:
$e_{1},e_{2},\dots,e_{k}$, where $e_{1},e_{k}\in E(F)$.

  2. 2.

Let $\ell\in\\{2,3,\dots,k-1\\}$ be such that $e_{\ell}=e$.

  3. 3.

Remove $u$ from the graph, along with all arcs incident to $u$.

  4. 4.

Introduce two new vertices $u_{1}$, $u_{2}$ to the graph. For each
$i\in\\{1,2,\dots,\ell\\}$, add to the graph a new arc $e_{i}^{1}$ which is
obtained from the arc $e_{i}$ by replacing the endpoint $u$ with $u_{1}$.
Similarly, for each $i\in\\{\ell,\ell+1,\dots,k\\}$, add to the graph a new
arc $e_{i}^{2}$ which is obtained from the arc $e_{i}$ by replacing the
endpoint $u$ with $u_{2}$.

Intuitively, $G_{e}$ is produced by drawing the graph $G$ on a piece of paper
and cutting the piece of paper along $e$. Note that after this operation, the
resulting graph is still planar (Figure 3). Moreover, the outer face $F_{e}$
of $G_{e}$ is simple, and $V(F)\setminus V(F_{e})=\\{u\\}$ and
$V(F_{e})\setminus V(F)=\\{u_{1},v,u_{2}\\}$. That is, $v$ now lies on the
outer face of the new graph.

We can generalize this procedure to paths instead of just edges. Assume that
$P=v_{1}v_{2}\dots v_{k}$ is a $v_{1}$-grounded path which is disjoint with
$V(F)$ except for $v_{1}$. Then, cutting the graph along $P$ entails cutting
the graph along the arcs $v_{1}v_{2},v_{2}v_{3},\dots,v_{k-1}v_{k}$, in this
order. This way we obtain a plane graph where the destination of the path lies
on the outer face. See Figure 3 for an illustration.

It is immediate that given the combinatorial embedding of a plane graph $G$,
one can compute a plane embedding of the graph obtained by cutting $G$ along a
path $P$ in time linear with respect to the size of the graph. Thus we again
obtain a plane graph.

$v$$u$$e$$P$ (a)

$v$$u_{2}$$u_{1}$ (b)

(c)

Figure 3: (a) A directed plane graph $G$. (b) The result of cutting $G$ along
$e$. (c) The result of cutting $G$ along $P$.

##  3 Directed Detour

In this section we prove Theorem 1.1.

Let $G$ be a plane digraph, and let $s,t\in V(G)$ be a pair of vertices.
Recall that we assume $G$ to be weakly connected and we fix the plane
embedding of $G$. Therefore, from now on for simplicity we identify features
in $G$ (vertices, edges, paths, etc.) with their images under the embedding.
Our goal is to decide whether there is an $s$-to-$t$ path in $G$ of length at
least
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+1$.
We are going to reduce this question to solving a set of instances of the
$2$-Disjoint Paths problem. The reduction is similar to the algorithm of Fomin
et al. [3] for Directed Long Detour.

First, we run breadth-first search (BFS) starting from $s$ in $G$. Let $L_{i}$
denote the $i$-th layer of this BFS, that is, $L_{i}=\\{v\in
V(G)\mid\mathchoice{\mathsf{dist}_{G}\\!\left(s,v\right)}{\mathsf{dist}_{G}\\!\left(s,v\right)}{\mathsf{dist}_{G}\left(s,v\right)}{\mathsf{dist}_{G}\left(s,v\right)}=i\\}$
for $i\in\\{0,1,\ldots,n\\}$.

Suppose now that the instance $(G,s,t)$ is a yes-instance, and let $P$ be an
$s$-to-$t$ path witnessing this fact. Since $P$ is a non-shortest path from
$s$ to $t$, there is an index $p\in\\{0,1,\ldots,n\\}$ such that the layer
$L_{p}$ contains at least two vertices of $P$. Let us choose $p$ to be the
smallest such an index. Let $G_{\geqslant p}$ be the plane digraph obtained
from $G$ by removing all the vertices in $L_{0}\cup L_{1}\cup\ldots\cup
L_{p-1}$. We may assume that $G_{\geqslant p}$ is weakly connected, for
otherwise we discard all of its weakly connected components that do not
contain the vertex $t$.

######  Claim 1.

All vertices of $L_{p}$ lie on one face of $G_{\geqslant p}$.

###### Proof.

Consider any vertex $v$ of $L_{p}$ and any shortest path $Q$ from $s$ to $v$
in $G$. Observe that all vertices of $Q$ except for $v$ lie in layers
$L_{0},L_{1},\ldots,L_{p-1}$, hence they are removed when constructing
$G_{\geqslant p}$ from $G$. We conclude that $v$ lies on the boundary of the
(unique) face of $G_{\geqslant p}$ that contains $s$. ∎

Denote by $x$ and $y$, respectively, the first and the second vertex on the
path $P$ that lie in the layer $L_{p}$. In our algorithm we iterate over all
possible choices for the vertex $y$. Note that the choice of $y$ determines
the value of $p$, because $y\in L_{p}$. Observe that if we guess the vertex
$y$ correctly, then in order to find a non-shortest path from $s$ to $t$ it is
enough to find a vertex $x\in L_{p}$ ($x\neq y$) and three paths
$P_{\text{start}}$, $P_{\text{middle}}$ and $P_{\text{end}}$ such that

  * •

$P_{\text{start}}$ is a shortest path from $s$ to $x$ in $G$; and

  * •

$P_{\text{middle}}$, $P_{\text{end}}$ are two internally vertex-disjoint paths
in $G_{\geqslant p}$ going respectively from $x$ to $y$ and from $y$ to $t$.

Note that $y$ might be equal to $t$ and then $P_{\text{end}}$ is a trivial
path only consisting of the single vertex $t$.

On one hand, vertices $x$ and $y$ divide $P$ into subpaths $P_{\text{start}}$,
$P_{\text{middle}}$, and $P_{\text{end}}$ satisfying the properties stated
above. On the other hand, if we find a vertex $x$ and paths
$P_{\text{start}},P_{\text{middle}},P_{\text{end}}$ satisfying the above, then
their concatenation forms a valid solution. This is because the path
$P_{\text{start}}$ goes consecutively through layers
$L_{0},L_{1},\ldots,L_{p}$ due to being a shortest path, and thus it is
internally vertex-disjoint from $P_{\text{middle}}$ and $P_{\text{end}}$.
Also, the concatenation of $P_{\text{start}},P_{\text{middle}},P_{\text{end}}$
is a non-shortest path from $s$ to $t$ due to containing at least two
different vertices from layer $L_{p}$.

It would be natural to also iterate through all possible choices for $x$, but
for the sake of optimizing the running time we do the following instead.
Construct a digraph $H$ from the digraph $G_{\geqslant p}$ by adding to it a
vertex $x_{\text{super}}$ together with arcs $x_{\text{super}}u$ for all $u\in
L_{p}\setminus\\{y\\}$.

######  Claim 2.

$H$ is a planar digraph and its implicit embedding can be obtained from the
implicit embedding of $G_{\geqslant p}$ in linear time.

###### Proof.

It suffices to extend the implicit embedding of $G_{\geqslant p}$ by embedding
$x_{\text{super}}$ anywhere in the unique face whose boundary contains all
vertices of $L_{p}$ (which exists by Claim 1) and draw arcs connecting
$x_{\text{super}}$ with vertices of $L_{p}\setminus\\{y\\}$ within this face.
It is straightforward to see that this can be done in the setting of implicit
embeddings in linear time. ∎

Observe that pairs $(P_{1},P_{2})$ of internally vertex-disjoint paths going
respectively from $x_{\text{super}}$ to $y$ in $H$ and from $y$ to $t$ in $H$
correspond one-to-one to pairs $(P_{\text{middle}},P_{\text{end}})$ of
internally vertex-disjoint paths going respectively from some vertex $x\in
L_{p}$ ($x\neq y$) to $y$ in $G_{\geqslant p}$ and from $y$ to $t$ in
$G_{\geqslant p}$. We may additionally assume that the face of $H$ containing
both $x_{\text{super}}$ and $y$ is the outer face of $H$. This way we reduced
our original problem to a set of at most $n$ instances (one instance per each
choice of the vertex $y$) of the following problem:

Problem A Input: A plane digraph $H$ and three vertices $x,y,t\in V(H)$, where
$x$ and $y$ lie on the outer face of $H$. Question: Are there two internally
vertex-disjoint paths $P_{1}$ and $P_{2}$ such that $P_{1}$ is an $x$-to-$y$
path and $P_{2}$ is a $y$-to-$t$ path in $H$?

So to conclude Theorem 1.1 it is enough to show the following lemma.

######  Lemma 3.1.

Problem A can be solved in time $\mathcal{O}(n)$.

###### Proof.

Let $H^{\star}$ be a $(y,x)$-simplification of the outer face of $H$.
Naturally, the outer face of $H^{\star}$ is simple. Moreover,
$(H^{\star},x,y,t)$ is a yes-instance if and only if $(H,x,y,t)$ is a yes-
instance: $H^{\star}$ is exactly the graph $H$ with two additional $yx$ arcs,
which plainly cannot be a part of the sought solution.

Suppose now that $(H^{\star},x,y,t)$ is a yes-instance, and let
$(P_{1},P_{2})$ be a pair of paths in $H^{\star}$ that form a solution to
Problem A on $H^{\star}$. $P_{1}$ connects $x$ to $y$ which lie on the outer
face $F_{O}$ of $H^{\star}$ (which is a simple cycle), thus it is
$\left(x,y\right)$-grounded with respect to $F_{O}$. Therefore, it splits the
whole digraph $H$ into two parts, the area $\Gamma_{\mathsf{L}}(P_{1})$ left
of $P_{1}$ and the area $\Gamma_{\mathsf{R}}(P_{1})$ right of $P_{1}$, with
both areas intersecting only at $P_{1}$. Since $P_{2}$ is internally disjoint
with $P_{1}$, it must be entirely contained within
$\Gamma_{\mathsf{L}}(P_{1})$ or $\Gamma_{\mathsf{R}}(P_{1})$; without loss of
generality assume that $P_{2}$ is contained in the latter. Then, let $L_{x,y}$
be the leftmost path from $x$ to $y$ in $H^{\star}$.

######  Claim 3.

$(L_{x,y},P_{2})$ is also a valid solution to Problem A.

###### Proof.

By the definition of the leftmost path we know that
$\Gamma_{\mathsf{L}}(L_{x,y})\subseteq\Gamma_{\mathsf{L}}(P_{1})$, that is,
$L_{x,y}$ cannot use any vertex lying on the right side of $P_{1}$. Since all
vertices of $P_{2}$ (apart from $y$) lie on the right side of $P_{1}$ we
conclude the claim. ∎

An analogous argument shows that if $P_{2}$ is contained in
$\Gamma_{\mathsf{L}}(P_{1})$, then $(R_{x,y},P_{2})$ is a valid solution to
Problem A, where $R_{x,y}$ is the rightmost path from $x$ to $y$ in
$H^{\star}$. By the observation above, we know that in order to verify whether
$(H^{\star},x,y,t)$ is a yes-instance it is enough to find $L_{x,y}$ and
$R_{x,y}$ as candidates for $P_{1}$, and to check for each candidate whether
the vertex $t$ is reachable from $y$ in
$H^{\star}-(V(P_{1})\setminus\\{y\\})$. All these checks can be done in time
$\mathcal{O}(n)$ by running a proper depth-first search algorithm. ∎

##  4 Directed Long Detour

In this section we prove Theorem 1.2.

We are given a plane digraph $G$, two vertices $s,t\in V(G)$ and an integer
$k\in\mathds{N}$. As in Section 3, we assume that $G$ is weakly connected, and
we fix the plane embedding of $G$. We need to decide whether there is an
$s$-to-$t$ path in $G$ of length at least
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+k$.
We are going to reduce this question to solving a set of instances of the
$2$-Disjoint Paths problem (with some additional requirements).

We begin with running the algorithm of Bezáková et al. [1] to check whether
there is an $s$-to-$t$ path of length
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+l$
for some $l\in\\{k,k+1,\ldots,3k-1\\}$. From now on, we assume there is no
such $s$-to-$t$ path.

As in Section 3, we run a BFS starting from $s$ in $G$ and set $L_{i}=\\{v\in
V(G)\mid\mathchoice{\mathsf{dist}_{G}\\!\left(s,v\right)}{\mathsf{dist}_{G}\\!\left(s,v\right)}{\mathsf{dist}_{G}\left(s,v\right)}{\mathsf{dist}_{G}\left(s,v\right)}=i\\}$
for $i=0,1,\ldots,n$. For $i=1,2,\ldots,n$, let $G_{\geqslant i}$ be the plane
digraph obtained from $G$ by removing all the vertices in $L_{0}\cup\ldots\cup
L_{i-1}$. Again, without loss of generality, we assume that $G_{\geqslant i}$
is weakly connected.

Now, we iterate through all values for $p=1,2,\ldots,n$, and through all
choices for $x,y\in L_{p}$, where $x\neq y$ (there are at most $n^{2}$ choices
for $(p,x,y)$). Recall from Section 3 (Section 1) that both $x$ and $y$ lie on
the outer face of $G_{\geqslant p}$. Next, let $G_{\geqslant p}^{x,y}$ be the
$(y,x)$-simplification of the outer face of $G_{\geqslant p}$. We are now
going to search for three paths $P_{\text{start}}$, $P_{\text{middle}}$ and
$P_{\text{end}}$ satisfying the conditions:

  1. $(a)$

$P_{\text{start}}$ is a shortest $s$-to-$x$ path in $G$;

  2. $(b)$

$P_{\text{middle}}$ is an $(x,y)$-grounded path in $G_{\geqslant p}^{x,y}$ of
length at least $2k$;

  3. $(c)$

$P_{\text{end}}$ is a $y$-to-$t$ path in $G_{\geqslant p}^{x,y}$;

  4. $(d)$

paths $P_{\text{middle}}$ and $P_{\text{end}}$ are internally vertex-disjoint;
and

  5. $(e)$

if $P_{\text{end}}\subseteq\Gamma_{\mathsf{R}}(P_{\text{middle}})$, then there
is no $(x,y)$-grounded path $P_{\text{middle}}^{\prime}$ in $G_{\geqslant
p}^{x,y}$ of length at least $k$ such that
$P_{\text{middle}}^{\prime}\prec_{\mathrm{top}}P_{\text{middle}}$; and if
$P_{\text{end}}\subseteq\Gamma_{\mathsf{L}}(P_{\text{middle}})$, then there is
no such path with
$P_{\text{middle}}\prec_{\mathrm{top}}P_{\text{middle}}^{\prime}$.

We remark that the two $yx$ arcs added in the process of
$(y,x)$-simplification of $G_{\geqslant p}$ cannot be a part of any of the
paths $P_{\text{start}}$, $P_{\text{middle}}$, $P_{\text{end}}$ and hence
their existence can be safely ignored in the following series of claims.

First, we show that the procedure described above is actually equivalent to
solving the Directed Long Detour problem on the instance $(G,s,t,k)$.

######  Claim 4.

Assume that the paths $P_{\text{start}}$, $P_{\text{middle}}$ and
$P_{\text{end}}$ satisfy the properties $(a)$ – $(d)$ above. Then the
concatenation

$P=P_{\text{start}}\circ P_{\text{middle}}\circ P_{\text{end}}$

forms a valid solution for the Directed Long Detour problem.

###### Proof.

First, $P$ is a simple $s$-to-$t$ path. Indeed, $P_{\text{middle}}$ and
$P_{\text{end}}$ are internally vertex-disjoint by property $(d)$. Moreover,
since the path $P_{\text{start}}$ is a shortest $s$-to-$x$ path in $G$, it
does not use any vertex of $L_{p}\cup\ldots\cup L_{n}=V(G_{\geqslant p})$
apart from $x$, and thus $P_{\text{start}}$ is internally vertex-disjoint from
$P_{\text{middle}}$ and $P_{\text{end}}$ as well.

By property $(b)$ the length of $P$ is at least

$\mathchoice{\mathsf{dist}_{G}\\!\left(s,x\right)}{\mathsf{dist}_{G}\\!\left(s,x\right)}{\mathsf{dist}_{G}\left(s,x\right)}{\mathsf{dist}_{G}\left(s,x\right)}+2k+\mathchoice{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}=\mathchoice{\mathsf{dist}_{G}\\!\left(s,y\right)}{\mathsf{dist}_{G}\\!\left(s,y\right)}{\mathsf{dist}_{G}\left(s,y\right)}{\mathsf{dist}_{G}\left(s,y\right)}+2k+\mathchoice{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}\geqslant\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+2k,$

which finishes the proof. ∎

######  Claim 5.

If $(G,s,t,k)$ is a yes-instance, then there exist an integer $p\in\mathds{N}$
and vertices $x,y\in L_{p}$ for which there are paths $P_{\text{start}}$,
$P_{\text{middle}}$ and $P_{\text{end}}$ satisfying the properties $(a)$ –
$(e)$.

###### Proof.

Assume that $(G,s,t,k)$ is a yes-instance. Let $P$ be an $s$-to-$t$ path
witnessing this fact. If there are many such paths, we choose $P$ to be a
shortest one. As we established that there is no $s$-to-$t$ path of length
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+l$
for any $l\in\\{k,k+1,\ldots,3k-1\\}$, we may assume that the path $P$ is of
length at least
$\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+3k$.
Since $P$ is a non-shortest $s$-to-$t$ path, we may define
$p\in\\{1,2,\ldots,n\\}$ to be the smallest index such that $L_{p}$ contains
at least two vertices of the path $P$. Let $x$ and $y$ be, respectively, the
first and the second vertex on the path $P$ that lie in the layer $L_{p}$.

By definition of $p$, the subpath $P[s\to x]$ is a shortest $s$-to-$x$ path,
and thus we may set $P_{\text{start}}\coloneqq P[s\to x]$. We also set
$P_{\text{end}}\coloneqq P[y\to t]$. We will choose $P_{\text{middle}}$ later
in the course of the proof.

Let us observe that the length of the subpath $P[x\to y]$ is at least $2k$:
otherwise, we consider the path $P^{\prime}$ being the concatenation of a
shortest $s$-to-$y$ path in $G$ and the subpath $P[y\to t]$. As in Claim 4, we
argue that $P^{\prime}$ is a simple $s$-to-$t$ path in $G$, and the length of
$P^{\prime}$ is

$\displaystyle\mathchoice{\mathsf{dist}_{G}\\!\left(s,y\right)}{\mathsf{dist}_{G}\\!\left(s,y\right)}{\mathsf{dist}_{G}\left(s,y\right)}{\mathsf{dist}_{G}\left(s,y\right)}+\mathchoice{\mathsf{length}\\!\left(P[y\to
t]\right)}{\mathsf{length}\\!\left(P[y\to
t]\right)}{\mathsf{length}\left(P[y\to t]\right)}{\mathsf{length}\left(P[y\to
t]\right)}$
$\displaystyle=\mathchoice{\mathsf{dist}_{G}\\!\left(s,x\right)}{\mathsf{dist}_{G}\\!\left(s,x\right)}{\mathsf{dist}_{G}\left(s,x\right)}{\mathsf{dist}_{G}\left(s,x\right)}+\mathchoice{\mathsf{length}\\!\left(P[y\to
t]\right)}{\mathsf{length}\\!\left(P[y\to
t]\right)}{\mathsf{length}\left(P[y\to t]\right)}{\mathsf{length}\left(P[y\to
t]\right)}$
$\displaystyle=\mathchoice{\mathsf{length}\\!\left(P\right)}{\mathsf{length}\\!\left(P\right)}{\mathsf{length}\left(P\right)}{\mathsf{length}\left(P\right)}-\mathchoice{\mathsf{length}\\!\left(P[x\to
y]\right)}{\mathsf{length}\\!\left(P[x\to
y]\right)}{\mathsf{length}\left(P[x\to y]\right)}{\mathsf{length}\left(P[x\to
y]\right)}$
$\displaystyle>(\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+3k)-2k=\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+k.$

Hence, $P^{\prime}$ is also a valid solution for our instance $(G,s,t,k)$ that
is shorter than $P$, which is a contradiction.

Since $P[x\to y]$ is an $(x,y)$-grounded path in $G_{\geqslant p}^{x,y}$ and
is internally disjoint from $P[y\to t]$, we may assume that $P[y\to
t]\subseteq\Gamma_{\mathsf{R}}(P[x\to y])$ in $G_{\geqslant p}^{x,y}$; the
case $P[y\to t]\subseteq\Gamma_{\mathsf{L}}(P[x\to y])$ is symmetric.

Observe now, that if we set $P_{\text{middle}}\coloneqq P[x\to y]$, then the
properties $(a)$ – $(d)$ are satisfied. If the condition $(e)$ holds as well,
then we are done. Otherwise, we define $P_{\text{middle}}$ as a minimal, with
respect to $\prec_{\mathrm{top}}$, $(x,y)$-grounded path in $G_{\geqslant
p}^{x,y}$ of length at least $2k$. Then,
$P_{\text{middle}}\prec_{\mathrm{top}}P[x\to y]$, and consequently
$P_{\text{middle}}$ is internally vertex disjoint from $P_{\text{end}}=P[y\to
t]$ as we have $P[y\to t]\subseteq\Gamma_{\mathsf{R}}(P[x\to y])$.

It remains to show that the pair $(P_{\text{middle}},P_{\text{end}})$
satisfies the property $(e)$. By the definition of $P_{\text{middle}}$ we know
there is no $(x,y)$-grounded path of length at least $2k$ which is
topologically left of $P_{\text{middle}}$. Suppose now that there exists an
$(x,y)$-grounded path $P_{\text{middle}}^{\prime}$ in $G_{\geqslant p}^{x,y}$
such that $P_{\text{middle}}^{\prime}\prec_{\mathrm{top}}P_{\text{middle}}$
and
$\mathchoice{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}\in[k,2k-1]$.
Consider the following walk $P^{\prime}$:

$P^{\prime}=P[s\to x]\circ P_{\text{middle}}^{\prime}\circ P[y\to t].$

$P^{\prime}$ is a simple path as in $G_{\geqslant p}$ we have
$P_{\text{middle}}^{\prime}\prec_{\mathrm{top}}P_{\text{middle}}\prec_{\mathrm{top}}P[x\to
y]$ and $P[y\to t]\subseteq\Gamma_{\mathsf{R}}(P[x\to y])$, therefore
$P_{\text{middle}}^{\prime}$ is internally vertex-disjoint from both $P[s\to
x]$ and $P[y\to t]$. Moreover, the length of $P^{\prime}$ is at least

$\displaystyle\mathchoice{\mathsf{dist}_{G}\\!\left(s,x\right)}{\mathsf{dist}_{G}\\!\left(s,x\right)}{\mathsf{dist}_{G}\left(s,x\right)}{\mathsf{dist}_{G}\left(s,x\right)}+\mathchoice{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}+\mathchoice{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}=$
$\displaystyle\mathchoice{\mathsf{dist}_{G}\\!\left(s,y\right)}{\mathsf{dist}_{G}\\!\left(s,y\right)}{\mathsf{dist}_{G}\left(s,y\right)}{\mathsf{dist}_{G}\left(s,y\right)}+\mathchoice{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\\!\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}{\mathsf{dist}_{G}\left(y,t\right)}+\mathchoice{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}\geqslant$
$\displaystyle\
\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+\mathchoice{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}\geqslant\mathchoice{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\\!\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}{\mathsf{dist}_{G}\left(s,t\right)}+k.$

Consequently, $P^{\prime}$ is a valid solution for the instance $(G,s,t,k)$.
Finally, since
$\mathchoice{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\\!\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}{\mathsf{length}\left(P_{\text{middle}}^{\prime}\right)}<2k\leqslant\mathchoice{\mathsf{length}\\!\left(P[x\to
y]\right)}{\mathsf{length}\\!\left(P[x\to
y]\right)}{\mathsf{length}\left(P[x\to y]\right)}{\mathsf{length}\left(P[x\to
y]\right)}$, the path $P^{\prime}$ is shorter than the path $P$ which is a
contradiction.

∎

It remains to show how we can find paths $P_{\text{start}}$,
$P_{\text{middle}}$ and $P_{\text{end}}$ satisfying the above-mentioned
conditions. Let us assume that we guess the values of $p$, $x$ and $y$
correctly. By Claim 4, we know that $P_{\text{start}}$ can be set to any
shortest $s$-to-$x$ path, and we see that in order to find the desired paths
$P_{\text{middle}}$ and $P_{\text{end}}$ we can restrict ourselves to the
digraph $G_{\geqslant p}^{x,y}$. Let us call a pair of paths
$(P_{\text{middle}},P_{\text{end}})$ _special_ for $(G_{\geqslant
p}^{x,y},x,y,t,k)$ if they satisfy the properties $(b)$ – $(e)$ stated above.
This reduces our instance of the Directed Long Detour problem to solving the
set of at most $n^{2}$ instances (one for each choice of $x$ and $y$) of the
following problem (with $H\coloneqq G_{\geqslant p}^{x,y}$).

Problem B Input: A plane digraph $H$, three vertices $x,y,t\in V(H)$, and an
integer $k\in\mathds{N}$, where $x$ and $y$ lie on the outer face of $H$. The
outer face of $H$ is simple and contains only the vertices $x$ and $y$.
Question: Does there exist a special pair of paths $(P_{1},P_{2})$ for
$(H,x,y,t,k)$?

To finish the proof of Claim 1.2 it is enough to show the following lemma.

######  Lemma 4.1.

Problem B can be solved in time $2^{\mathcal{O}(k)}\cdot n^{2}$ by a Monte
Carlo algorithm, or deterministically in time $2^{\mathcal{O}(k)}\cdot
n^{2}\log n$.

###### Proof.

We use a variant of the standard color coding technique [4]. Let us color
independently every vertex of $H$ with one of two colors, say green and blue,
each with probability $\frac{1}{2}$.

Assume for now that $(H,x,y,t,k)$ is a yes-instance, and let $(P_{1},P_{2})$
be a special pair of paths for our instance. As per our previous
considerations, we know that $P_{2}\subseteq\Gamma_{\mathsf{L}}(P_{1})$ or
$P_{2}\subseteq\Gamma_{\mathsf{R}}(P_{1})$. Without loss of generality assume
that $P_{2}\subseteq\Gamma_{\mathsf{R}}(P_{1})$. Recall that
$\mathchoice{\mathsf{length}\\!\left(P_{1}\right)}{\mathsf{length}\\!\left(P_{1}\right)}{\mathsf{length}\left(P_{1}\right)}{\mathsf{length}\left(P_{1}\right)}\geqslant
2k$. Therefore, we may define $x^{\prime}$ to be the $k$-th vertex on $P_{1}$
and $y^{\prime}$ to be the $k$-th vertex from the end of $P_{1}$. Then,
$\mathchoice{\mathsf{length}\\!\left(P_{1}[x\to
x^{\prime}]\right)}{\mathsf{length}\\!\left(P_{1}[x\to
x^{\prime}]\right)}{\mathsf{length}\left(P_{1}[x\to
x^{\prime}]\right)}{\mathsf{length}\left(P_{1}[x\to
x^{\prime}]\right)}=\mathchoice{\mathsf{length}\\!\left(P_{1}[y^{\prime}\to
y]\right)}{\mathsf{length}\\!\left(P_{1}[y^{\prime}\to
y]\right)}{\mathsf{length}\left(P_{1}[y^{\prime}\to
y]\right)}{\mathsf{length}\left(P_{1}[y^{\prime}\to y]\right)}=k-1$ and the
paths $P_{1}[x\to x^{\prime}]$ and $P_{1}[y^{\prime}\to y]$ are vertex-
disjoint.

Suppose that the colors are assigned in such a way that all vertices of the
path $P_{1}[x\to x^{\prime}]$ are green, and all vertices of the path
$P_{1}[y^{\prime}\to y]$ are blue. The probability of such an event occurring
is $(1/2)^{2k}$. Let $\mathcal{G}$ be the set of green vertices of $H$ in the
random coloring. Note that we assume that $V(P_{1}[x\to
x^{\prime}])\subseteq\mathcal{G}$.

######  Claim 6.

$P_{1}[x\to x^{\prime}]$ is the lexicographically leftmost $x$-to-$x^{\prime}$
path in $H$ entirely contained in $\mathcal{G}$.

###### Proof.

Suppose that there is an $x$-to-$x^{\prime}$ path $Q$ in $H$, entirely
contained in $\mathcal{G}$, such that $Q\prec_{\mathrm{lex}}P_{1}[x\to
x^{\prime}]$. Let $q\in V(H)$ be the vertex for which path $P_{1}[x\to q]$ is
the longest common prefix of $P_{1}$ and $Q$. Also, let $r$ be the first
vertex on $Q[q\to x^{\prime}]$, not including $q$, such that $r\in V(P_{1})$.
Here, $r$ is well-defined as the vertex $x^{\prime}$ belongs to both $Q[q\to
x^{\prime}]$ and $P_{1}$. Since $r$ lies on $Q$, we necessarily have that $r$
is green. Thus, $r\not\in V(P_{1}[y^{\prime}\to y])$ since
$P_{1}[y^{\prime}\to y]$ consists only of blue vertices. Hence, the following
walk $P_{1}^{\prime}$:

$P_{1}^{\prime}=Q[x\to r]\circ P_{1}[r\to y]$

is an $(x,y)$-grounded path in $H$ of length at least

$\mathchoice{\mathsf{length}\\!\left(P_{1}[y^{\prime}\to
y])\right)}{\mathsf{length}\\!\left(P_{1}[y^{\prime}\to
y])\right)}{\mathsf{length}\left(P_{1}[y^{\prime}\to
y])\right)}{\mathsf{length}\left(P_{1}[y^{\prime}\to y])\right)}+1=k.$

Recall that $Q\prec_{\mathrm{lex}}P_{1}$ in $H$. By the definition of $r$ we
observe that $Q[x\to r]\prec_{\mathrm{top}}P_{1}[x\to r]$. Hence,
$P_{1}^{\prime}\prec_{\mathrm{top}}P_{1}$. We conclude that the path
$P_{1}^{\prime}$ has length at least $k$ and is left of $P_{1}$, which
contradicts the property $(e)$ of the pair $(P_{1},P_{2})$. ∎

Note that the path $P_{1}[x\to x^{\prime}]$ is disjoint from the set of
vertices on the outer face of $H$, apart from its first vertex $x$. This
allows us to define $H^{\textrm{cut}}$ as the plane digraph obtained from $H$
by cutting along the path $P_{1}[x\to x^{\prime}]$. Next, let $Z\subseteq
V(H^{\textrm{cut}})$ be the set of new vertices introduced to $H^{\prime}$ by
this operation. Let $H^{\prime}$ be a $(y,x^{\prime})$-simplification of the
outer face of $H^{\textrm{cut}}$.

######  Claim 7.

$P_{1}[x^{\prime}\to y]$ is the leftmost path in $H^{\prime}$ among all the
paths between $x^{\prime}$ and $y$ which do not contain any vertex of $Z$.

###### Proof.

Suppose that there is an $x^{\prime}$-to-$y$ path $Q$ in $H^{\prime}$ which
avoids $Z$ and satisfies $Q\prec_{\mathrm{lex}}P_{1}[x^{\prime}\to y]$. Let
$q\in V(H)$ be the vertex of $H$ such that $Q[x^{\prime}\to q]$ is the longest
common prefix of $Q$ and $P_{1}[x^{\prime}\to y]$. Let $r$ be the first vertex
on $Q[q\to y]$ (not including $q$) such that $r\in V(P_{1})$.

Analogously as in the proof of Claim 6, we show that the walk $P_{1}^{\prime}$
defined in $H$ as follows:

$P_{1}^{\prime}=P_{1}[x\to x^{\prime}]\circ Q[x^{\prime}\to r]\circ P_{1}[r\to
y]$

is a simple path of length at least $k$ that lies lexicographically left of
$P_{1}$ in $H$. This leads to a contradiction to property $(e)$ of
$(P_{1},P_{2})$. ∎

The observations above lead to an algorithm for Problem B. First, consider the
case where in the solution $(P_{1},P_{2})$, we have that
$P_{2}\subseteq\Gamma_{\mathsf{R}}(P_{1})$. After the random assignment of
colors to vertices of $H$, we iterate through all vertices $u\in
V(H)\setminus\\{x,y,t\\}$ as candidates for the vertex $x^{\prime}$. Then, we
find the leftmost path $S$ from $x$ to $u$ in $H$ whose all vertices are
green. Next, we construct $H^{\textrm{cut}}$ and $H^{\prime}$, and find the
leftmost path $T$ from $u$ to $y$ in $H^{\prime}$ that avoids any new vertices
introduced to $H^{\prime}$ by the split. Finally, we set $P_{1}=S\circ T$.
Then it only remains to verify whether there exists any path $P_{2}$ from $y$
to $t$ in $H$ that is internally disjoint with $P_{1}$. All these checks can
be done by running proper depth-first searches in total linear time.

Next, we consider the case where $P_{2}\subseteq\Gamma_{\mathsf{L}}(P_{1})$.
Hence, we repeat all the above steps with any leftmost paths in $H$ replaced
with the corresponding rightmost paths. To obtain the constant probability of
error, we repeat the entire process above $2^{\mathcal{O}(k)}$ times.

To derandomize this algorithm, instead of assigning the colors to vertices at
random, we construct and use an $(n,2k)$-universal set [7]. In our case this
universal set is a family $\mathcal{U}$ of subsets of $V(H)$ such that for any
subset $A$ of $V(H)$ of size $2k$ the family $\\{A\cap U\mid
U\in\mathcal{U}\\}$ contains all $2^{2k}$ subsets of $A$. We interpret each
element of $\mathcal{U}$ as a single coloring, that is, a subset
$A\in\mathcal{U}$ corresponds to the coloring $c$ which assigns color green to
the vertices of $A$, and blue to the rest.

We know that there is such family $\mathcal{U}$ of size
$2^{\mathcal{O}(k)}\cdot\log n$ and it can be constructed in time
$2^{\mathcal{O}(k)}\cdot n\log n$ [7]. We construct it once in the algorithm,
and instead of drawing random colorings, we iterate through all elements of
the constructed universal set $\mathcal{U}$. By the property of $\mathcal{U}$
there is an element $U\in\mathcal{U}$ such that $V(P_{1}[x\to
x^{\prime}])\subseteq U$ and $V(P_{1}[y^{\prime}\to y])\cap U=\emptyset$
because $|V(P_{1}[x\to x^{\prime}])\cup V(P_{1}[y^{\prime}\to y])|=2k$. This
guarantees the correctness of our deterministic algorithm. ∎

### Acknowledgement.

The authors thank Olek Łukasiewicz for pointing us to the work of Wu and Wang
[9].

## References

  * [1] Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin.  Finding detours is fixed-parameter tractable.  SIAM J. Discret. Math., 33(4):2326–2345, 2019.
  * [2] Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk.  The Planar Directed $k$-Vertex-Disjoint Paths problem is fixed-parameter tractable.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pages 197–206. IEEE Computer Society, 2013.
  * [3] Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh.  Detours in Directed Graphs.  In 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, volume 219 of LIPIcs, pages 29:1–29:16. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2022.
  * [4] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Long directed (_s_ , _t_)-path: FPT algorithm.  Inf. Process. Lett., 140:8–12, 2018.
  * [5] Steven Fortune, John E. Hopcroft, and James Wyllie.  The directed subgraph homeomorphism problem.  Theor. Comput. Sci., 10:111–121, 1980.
  * [6] John E. Hopcroft and Robert Endre Tarjan.  Efficient Planarity Testing.  J. ACM, 21(4):549–568, 1974.
  * [7] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan.  Splitters and near-optimal derandomization.  In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 182–191. IEEE Computer Society, 1995.
  * [8] Alexander Schrijver.  Finding $k$ disjoint paths in a directed planar graph.  SIAM J. Comput., 23(4):780–788, 1994.
  * [9] Bang Ye Wu and Hung-Lung Wang.  The next-to-shortest path problem on directed graphs with positive edge weights.  Networks, 65(3):205–211, 2015.