# Max $s,t$-Flow Oracles and Negative Cycle Detection
in Planar Digraphs

Adam Karczmarz University of Warsaw and IDEAS NCBR, Poland.
<EMAIL_ADDRESS>Partially supported by the ERC CoG grant TUgbOAT no
772346 and the National Science Centre (NCN) grant no. 2022/47/D/ST6/02184.

###### Abstract

We study the maximum $s,t$-flow oracle problem on planar _directed_ graphs
where the goal is to design a data structure answering max $s,t$-flow value
(or equivalently, min $s,t$-cut value) queries for arbitrary source-target
pairs $(s,t)$. For the case of polynomially bounded integer edge capacities,
we describe an _exact_ max $s,t$-flow oracle with truly subquadratic space and
preprocessing, and sublinear query time. Moreover, if
$(1-\epsilon)$-approximate answers are acceptable, we obtain a static oracle
with near-linear preprocessing and $\widetilde{O}(n^{3/4})$ query time and a
dynamic oracle supporting edge capacity updates and queries in
$\widetilde{O}(n^{6/7})$ worst-case time.

To the best of our knowledge, for _directed_ planar graphs, no (approximate)
max $s,t$-flow oracles have been described even in the unweighted case, and
only trivial tradeoffs involving either no preprocessing or precomputing all
the $n^{2}$ possible answers have been known.

One key technical tool we develop on the way is a sublinear (in the number of
edges) algorithm for finding a negative cycle in so-called dense distance
graphs. By plugging it in earlier frameworks, we obtain improved bounds for
other fundamental problems on planar digraphs. In particular, we show:

  1. (1)

a deterministic $O(n\log(nC))$ time algorithm for negatively-weighted SSSP in
planar digraphs with integer edge weights at least $-C$. This improves upon
the previously known bounds in the important case of weights polynomial in
$n$.

  2. (2)

an improved $O(n\log{n})$ bound on finding a perfect matching in a bipartite
planar graph.

##  1 Introduction

Single-source shortest paths (with negative weights allowed) and maximum flow
are among the most fundamental computational problems on directed graphs. The
best known _strongly polynomial_ $\widetilde{O}(nm)$ time bounds for these
problems [Bel58, FJ56, GN80, ST83] have stood for decades. The scaling
framework [EK72, Gab85] made it apparent that this quadratic barrier can be
overcome in a relaxed _weakly polynomial_ model, where the magnitude $\log{C}$
of the largest numeric value $C$ (such as the maximum absolute weight/capacity
of an edge) is also used to measure the size of an instance. That is, a graph
algorithm is weakly polynomial-time if it runs in time polynomial in $n$, $m$,
and $\log{C}$. Weakly polynomial-time algorithms typically assume integer data
to guarantee that exact solutions are computed. In particular, [Gab85] showed
an $O(mn^{3/4}\log{C})$ algorithm for single-source shortest paths with
integer weights (and more general problems such as minimum-cost bipartite
matching). That method has been subsequently refined to run in time
$\widetilde{O}(m\sqrt{n}\log{C})$ [GT89, Gol95]. Later, a similar subquadratic
bound has been obtained also for the maximum flow problem by Goldberg and Rao
[GR98]. These algorithms, developed in the previous century, remain the best
deterministic combinatorial algorithms for these problems to date.

Recent years have brought impressive progress on single-source shortest paths
and maximum flow in the weakly polynomial regime with integer data. The usage
of the interior-point method (IPM) for solving linear programs [Kar84] along
with dynamic algebraic data structures proved very powerful for solving
fundamental polynomial-time graph problems and ultimately led to very
efficient ${\widetilde{O}((m+n^{3/2})\log{C})}$111As usual, throughout we use
the $\widetilde{O}(\cdot)$ notation to suppress $\operatorname{polylog}(n)$
factors. [vdBLL+21] and $O(m^{1+o(1)}\log^{2}{C})$ time [CKL+22, vdBCK+23]
algorithms for the minimum-cost flow problem, which generalizes both the SSSP
and maximum flow problems. Even more recently, [BNW22] developed a randomized
algorithm for the negatively-weighted SSSP problem exclusively that is purely
combinatorial in nature and runs (with the tweaks of [BCF23] applied) in
$O(m\log^{2}{n}\log{(nC)}\log\log{n})$ expected time.

The focus of this paper is on algorithms for planar digraphs. Planarity-
exploiting near-optimal _strongly polynomial_ algorithms have been known for
both single-source shortest paths and maximum flow. Fakcharoenphol and Rao
[FR06] gave the first near-optimal $O(n\log^{3}{n})$-time algorithm for
negative cycle detection and SSSP in planar digraphs. This has been
subsequently improved by [KMW10, MW10] and the current best known bound is
$O(n\log^{2}{n}/\log\log{n})$. Maximum $s,t$-flow on planar digraphs can be
computed in $O(n\log{n})$ time [BK09, Eri10]. The multiple-source multiple-
sink case of max-flow is not easily reducible to the single-source single-sink
case while preserving planarity, and the best known upper bound for that case
is $O(n\log^{3}{n})$ [BKM+17]. All these state-of-the-art algorithms for
planar graphs are combinatorial and deterministic.

Since planarity enables efficient strongly polynomial algorithms for shortest
paths and maximum flow, the study of _weakly polynomial-time_ algorithms for
these problems in the planar case has been rather limited. To the best of our
knowledge, the combinatorial scaling framework has only been applied to unit-
capacity minimum-cost flow problems on planar graphs [AKLR20, KS19, LR19], but
the achieved bounds were still a polynomial factor away from linear. Recently,
an algebraic IPM-based near-linear randomized algorithm for planar min-cost
flow has been proposed [DGG+22].

In this paper we apply the combinatorial scaling framework to the maximum
$s,t$-flow oracle problem and the negative-weights single-source shortest
paths problem on planar digraphs.

###  1.1 Our contribution

####  1.1.1 Max $s,t$-flow oracles

We consider the following _max $s,t$-flow oracle_ problem. Given a planar
digraph ${G=(V,E)}$, preprocess it into a data structure supporting max
$s,t$-flow value (or, equivalently, min $s,t$-cut capacity) queries for
arbitrary pairs $s,t\in V\times V$. One extreme trivial solution for this
problem is to skip preprocessing and answer queries using the state-of-the-art
$O(n\log{n})$-time max $s,t$-flow algorithms for planar digraphs [BK09,
Eri10]. Another extreme approach is to store all the possible $O(n^{2})$
answers and read the stored result in $O(1)$ time upon query. [ŁNSW12] showed
that computing all-pairs max $s,t$-flow values in planar graphs takes near-
optimal $\widetilde{O}(n^{2})$ time. They also showed that in planar digraphs
there might be $\Theta(n^{2})$ distinct max $s,t$-flow values (as opposed to
_general_ undirected graphs, where there may be at most $n-1$ max-flow values)
and asked whether constant-time queries are possible after subquadratic
preprocessing. Nussbaum [Nus14, Section 9.1.3] relaxed this open question and
asked whether _sublinear_ query time is possible after _subquadratic_
preprocessing. Of course, ideally, we would like to support queries in
$\widetilde{O}(1)$ time after $\widetilde{O}(n)$-time preprocessing. This is
in fact possible in _undirected_ planar graphs [BSW15], where min $s,t$-cuts
have much more convenient structure compared to directed planar graphs.
However, for the directed case, no non-trivial preprocessing/query tradeoffs
have been described to date even for the case when the input graph is
unweighted and/or we only seek constant-factor approximate query answers.

First of all, we give an affirmative answer to the open problem posed in
[Nus14] in the important case of integer weights which also covers unweighted
graphs.

######  Theorem 1.1.

Let $G=(V,E)$ be a planar digraph with integer edge capacities in $[1,C]$ and
let $r\in[1,n]$. In $\widetilde{O}(nr)$ time one can construct an
$\widetilde{O}(nr)$-space data structure that, for any query pair $(s,t)\in
V\times V$, computes the max $s,t$-flow (or min $s,t$-cut) value in $G$ in
$\widetilde{O}(n^{3/2}/r^{3/4}\cdot\log^{2}{C})$ time.

Note that the data structure of Theorem 1.1 achieves both truly subquadratic
preprocessing/space and sublinear query time whenever $r=n^{\delta}$ satisfies
$\delta\in(2/3,1)$. It can also be used for computing max $s,t$-flow values
for some $k$ specified source-sink pairs faster than using the aforementioned
trivial tradeoffs following from [BK09, Eri10, ŁNSW12] unless
$k=\widetilde{O}(n^{2/3})$ or $k=\widetilde{\Omega}(n^{5/4})$. By suitably
choosing the parameter $r=n^{2/7}k^{4/7}$, we obtain the following.

######  Corollary 1.2.

Let $G=(V,E)$ be a planar digraph with integer edge capacities in $[1,C]$ and
let$k\in[n^{2/3},n^{5/4}]$ be an integer. One can compute exact max
$s_{i},t_{i}$-flow values for $k$ source/sink pairs
$(s_{1},t_{1}),\ldots,(s_{k},t_{k})\in V\times V$ in $G$ in
$\widetilde{O}(n^{9/7}k^{4/7}\log^{2}{C})$ time.

It is worth noting that [ŁNSW12] in fact showed a near-linear time algorithm
computing max $s,t$-flow values for $n$ pairs $(s,t)$, where the source $s$ is
_fixed_ (that is, common to all pairs) and $t\in V$ is arbitrary. In
comparison, the algorithm of Corollary 1.2 can handle $n$ _arbitrary_ source-
sink pairs in $\widetilde{O}(n^{13/7})$ time in the case of
$\operatorname{poly}(n)$-bounded integer edge capacities. Achieving
subquadratic time for general integer-weighted sparse graphs is unlikely
(conditionally on SETH) even in the single-source all-sinks case [AWY18,
KT18].

On the way to obtaining the exact oracle of Theorem 1.1, we show a
significantly more efficient _feasible $\lambda$-$s,t$-flow oracle_. The
oracle is given a parameter $\lambda\in[1,nC]$ upon construction and is only
required to support querying whether there exists a flow between a specified
source/sink pair of value precisely (or, equivalently, at least) $\lambda$.
Note that for $\lambda$ fixed to $1$, the problem is equivalent to the
_reachability oracle_ problem on planar digraphs, for which an optimal
solution has been shown in [HRT15]. In unweighted digraphs, if $\lambda$ is
fixed to be an integer more than $1$, the problem is called the
$\lambda$-reachability oracle problem. A near-optimal $2$-reachability oracle
for planar digraphs is known [IKP21]. To the best of our knowledge, no non-
trivial $\lambda$-reachability oracle for planar digraphs and arbitrary
$\lambda\geq 3$ has been described so far. We show an oracle with _near-
linear_ preprocessing (and space) and _sublinear_ query time for an arbitrary
parameter $\lambda$.

######  Theorem 1.3.

Let $G$ be a planar digraph with integer edge capacities in $[1,C]$ and let
$\lambda\in[1,nC]$ be an integer. In $\widetilde{O}(n)$ time one can construct
a data structure that can test, for any given query source/sink pair $(s,t)$
whether there exists an $s,t$-flow of value $\lambda$ in $G$ in
$\widetilde{O}(n^{3/4}\log{C})$ time.

Using standard methods, the feasible flow oracle can be extended in two
natural ways. First, by using $O(\log{(nC)}/\epsilon)$ copies of the data
structure, it can be turned into an $(1-\epsilon)$-approximate max $s,t$-flow
oracle with near-linear preprocessing and sublinear query time. Formally, we
have:

######  Corollary 1.4.

Let $G$ be a planar digraph with integer capacities in $[1,C]$. In
$\widetilde{O}(n\log{(C)}/\epsilon)$ time one can construct an
$\widetilde{O}(n\log{(C)}/\epsilon)$-space data structure that, for any query
source/sink pair $(s,t)$, estimates the max $s,t$-flow value in $G$ up to a
factor $1-\epsilon$ in
$\widetilde{O}(n^{3/4}\cdot\log{C}\cdot\log{(\log(C)/\epsilon)})$ time.

By following the same approach that has been previously used to convert the
static distance oracles into dynamic distance oracles for planar graphs [FR06,
Kle05, KMNS17], we obtain a dynamic approximate max $s,t$-flow oracle
supporting edge capacity updates.

######  Theorem 1.5.

Let $G$ be a planar digraph with integer edge capacities in $[1,C]$. There
exists a dynamic $(1-\epsilon)$-approximate max $s,t$-flow oracle with
$\widetilde{O}(n^{6/7}\cdot\log{C}\cdot\log{(\log{(C)}/\epsilon)})$ query time
that supports edge capacity updates in
$\widetilde{O}(n^{6/7}\log{(C)}/\epsilon)$ worst-case time.

To the best of our knowledge, no other dynamic max $s,t$-flow oracles with
sublinear update and query bounds for planar _directed_ graphs have been
described so far. _Exact_ dynamic max $s,t$-flow oracles with sublinear update
and query time have been previously developed only for planar _undirected_
graphs [INSW11]. It is worth noting that [Kar21] gave a dynamic algorithm
maintaining $(1-\epsilon)$-approximate max $s,t$-flow value in a planar
digraph for a single fixed pair $s,t$ in
$\widetilde{O}(n^{2/3}\log{(C)}/\epsilon)$ amortized time per update. Whereas
the algorithm of [Kar21] also exploits the connection between the feasible
flow problem and negative cycle detection, it crucially relies on the fact
that a _single_ value is maintained and its update bound is inherently
amortized.

Let us remark that all the proposed max $s,t$-flow oracles can be easily
extended to report a certifying $s,t$-cut-set $F\subseteq E$ after answering
the query (i.e., an $s,t$-cut-set of capacity less than $\lambda$ in the case
of the feasible flow oracle, an $(1+\epsilon)$-approximate min $s,t$-cut-set
in the approximate oracle, and exact min $s,t$-cut-set in the exact oracle) in
near-optimal $\widetilde{O}(|F|)$ extra time.

##### Reduction to negative cycle detection in DDGs.

The key tool that we develop to enable sublinear-time queries in max-flow
oracles is a new algorithm for finding a negative cycle in so-called _dense
distance graphs_ (DDGs) [FR06] that constitute a fundamental concept in the
area of planar graph algorithms.

Roughly speaking, a dense distance graph $\mathrm{DDG}(\mathcal{R})$
associated with an $r$-division $\mathcal{R}$ with few holes [KMS13] of a
plane digraph $G$ is a certain graph with $O(n/\sqrt{r})$ vertices and $O(n)$
edges allowing efficient shortest paths computations. [FR06] famously
developed an implementation of Dijsktra‘s algorithm on a dense distance graph
running in $\widetilde{O}(n/\sqrt{r})$ time, and an implementation of the
Bellman-Ford algorithm (accepting also negative edges) running in
$\widetilde{O}(n^{2}/r)$ time. While both are faster than their respective
general-graph implementations for any $r=\operatorname{poly}{n}$, the latter
never runs in time sublinear in the graph size since $r\leq n$.

Based on scaling techniques [GT89, GHKT17, KS19] we give a deterministic
algorithm for finding a negative cycle in $\mathrm{DDG}(\mathcal{R})$ in
$\widetilde{O}(n^{3/2}/r^{3/4})$ time in the case of polynomial integer
weights (see Theorem 4.3). Crucially, this bound is truly sublinear in $n$ for
a sufficiently large choice of $r$.

Our max $s,t$-flow oracles use negative cycle detection on dense distance
graphs in a fairly black-box manner. As a result, obtaining a faster algorithm
for that subproblem (ideally, matching the $\widetilde{O}(n/\sqrt{r})$
Dijkstra bound of [FR06]) – formulated with no connection to flows – will lead
to more efficient max $s,t$-flow oracles for planar digraphs. This is an
especially promising further research direction given the recent randomized
near-linear combinatorial SSSP algorithm [BNW22, BCF23].222A very recent
manuscript [ABC+23] generalizes [BNW22] into a black-box reduction of
negatively-weighted SSSP on a digraph $G$ to non-negatively weighted SSSP
instances on subgraphs of $G$ (not necessarily vertex-induced, and with edge
weights potentially changed) of total size $mn^{o(1)}$. It is not clear how to
apply that framework here, though. First, even describing the subgraphs might
require $\Theta(m)$ space. Moreover, a dense distance graph with some edges
removed does not, in general, preserve the properties leveraged by the
efficient Dijkstra implementation of [FR06].

####  1.1.2 Negatively-weighted SSSP

Our new algorithm finding a negative cycle in a dense distance graph, plugged
in the earlier framework [KMW10], leads to the fastest known algorithm for
negative cycle detection and single-source shortest paths in integer-weighted
planar digraphs. Formally, we prove:

######  Theorem 1.6.

Let $G$ be a planar digraph with integer edge weights in $[-C,\infty)$. One
can either detect a negative cycle in $G$ or compute a feasible price function
of $G$ in $O(n\log{(nC)})$ time.

It is well-known that computing a feasible price function of a graph reduces
the SSSP problem to a non-negatively weighted instance, which can be in turn
solved in $O(m+n\log{n})$ time using Dijkstra‘s algorithm. For planar
digraphs, an even faster linear-time algorithm is known [HKRS97].

For the important case $C=\operatorname{poly}{n}$, our SSSP algorithm runs in
$O(n\log{n})$ time. This improves upon the state-of-the-art strongly
polynomial $O(n\log^{2}{n}/\log\log{n})$ bound of [MW10]. Like all the
previous shortest paths algorithms for planar graphs – and in contrast to the
recent breakthrough combinatorial result for general graphs [BNW22] – our
algorithm is also deterministic.

As shown by [MN95], routing a _feasible flow_ respecting given vertex demands
in a plane digraph reduces to solving a (negatively-weighted) SSSP problem in
the dual graph. We thus obtain:

######  Corollary 1.7.

Let $G$ be a planar digraph with integer edge capacities no larger than $C$.
Let $d:V(G)\to\mathbb{Z}$ be a demand vector. Then, in $O(n\log{(nC)})$ time
one can compute a flow function $f:E(G)\to\mathbb{Z}_{\geq 0}$ on $G$ such
that the excess of a vertex $v\in V(G)$ equals $d(v)$ (if such $f$ exists).

An important special case of the above feasible flow problem is that of
finding a perfect matching in a bipartite graph (use unit-capacity edges, and
demands $\pm 1$ depending on the side of a vertex).

######  Corollary 1.8.

A perfect matching in a bipartite planar graph $G$ can be found in
$O(n\log{n})$ time.

The previous best time bound for the planar bipartite perfect matching problem
was that of negative cycle detection, i.e.,
$O\left(n\frac{\log^{2}{n}}{\log\log{n}}\right)$ [MW10]. Our obtained bound
also looks much cleaner.

####  1.1.3 A more general framework for solving structured transportation-
like problems.

Even though all our developments are motivated by shortest paths and maximum
flow applications in planar graphs, on the way to proving Theorem 1.6, we
develop a fairly general framework for solving the minimum-cost circulation
problem (up to additive error $\delta$) on networks $G$ with a relatively
small (say $O(n)$) sum of vertex capacities and whose most of the defined
edges are uncapacitated and structured in a way. One can easily observe that
this setting captures the transportation problem, the minimum-cost perfect
matching problem, and – crucially for our applications – the negative cycle
detection problem (as observed by [Gab85]). The goal is to be able to solve
the problem in time that is _sublinear_ in the number of uncapacitated edges
defined implicitly.

This general idea has been previously used by Sharathkumar and Agarwal [SA12]
to obtain an $\widetilde{O}(n^{3/2}\cdot\Phi(n)\cdot\log{(C/\delta)})$
algorithm (based on [GT89]) for $\delta$-additive approximate transportation
problem with sum of demands $O(n)$ on _geometric networks_ with diameter $C$,
where $\Phi(n)$ is the update/query time of a _dynamic weighted nearest
neighbor data structure_ on the input point set wrt. the used metric. For
example, if the points lie on the plane, have integer coordinates, and the
metric used is $L_{1}$ or $L_{\infty}$, [SA12] give an exact
$\widetilde{O}(n^{3/2}\log{C})$-time algorithm for such a problem, even though
the network in consideration has $\Theta(n^{2})$ defined edges.

We generalize this approach to arbitrary digraphs, where the edge costs need
not form a metric. Our framework is an extension of the minimum-cost
circulation algorithms in [GHKT17, KS19]. We analyze the performance of the
framework wrt. the efficiency of dynamic _closest pair_ and _near neighbor_
graph data structures (defined precisely in Section 3) on the subgraph
$G_{\infty}\subseteq G$ containing the uncapacitated edges. Intuitively,
networks $G_{\infty}$ with good graph closest pair data structures are those
that allow very efficient (e.g., sublinear in $|E(G_{\infty})|$)
implementations of Dijkstra‘s algorithm, whereas fast near neighbor data
structures allow very efficient computation of blocking flows. These data-
structural abstractions are flexible enough to compose them efficiently by
taking graph unions or performing the vertex-splitting transformation (Section
4.3) which is crucial for applying the framework to the negative-cycle
detection problem. We note that the idea of analyzing the performance of graph
algorithms in terms of abstract dynamic closest pair data structures is not
new and has been described before e.g. in [CE01]. See Section 4.3 and Theorem
7.1 for details.

We believe that our generalized min-cost circulation framework is of
independent interest, and can be also applied beyond planar graphs, e.g. in
some more complex geometric settings. To support this claim, we now give an
example of a problem where our framework is applicable. Suppose the network
$G=(V,E)$ is a _weighted unit disk graph_ on $n$ points in the plane, where
every vertex except the source $s$ and sink $t$ has _unit vertex capacity_ and
$||s-t||>1$. For each $u,v\in V$, there is an implicit uncapacitated edge $uv$
with cost $||u-v||$ if $||u-v||\leq 1$. The vertices can also have costs
assigned. The goal is to compute the minimum cost $s\to t$ flow of a specified
value $k\leq n$. With our framework, and using known dynamic weighted nearest
neighbor structures [AES99]333Which also imply dynamic closest pair data
structures in a black-box way [Cha20]., we can compute an $\delta$-additive
approximation of the min-cost $s,t$-flow of value $k$ in $G$ in truly
subquadratic time (also dependent on $\log(1/\delta)$), even though $G$ may
have $\Theta(n^{2})$ edges defined implicitly.

###  1.2 Further related work

For general undirected graphs, the max $s,t$-flow oracle problem can be solved
by computing the so-called _cut-equivalent tree_ (or, the _Gomory-Hu tree_)
that encodes all the pairwise max-flow information [GH61]. Recently, there has
been a lot of effort to compute cut-equivalent trees efficiently (e.g.,
[AKT21, AKT22, LPS21, Zha22]) which culminated in an almost-optimal algorithm
for unweighted graphs and an $\widetilde{O}(n^{2})$-time algorithm on weighted
graphs [AKL+22, CKL+22].

For general directed graphs, there is a $n^{3-o(1)}$ conditional lower bound
[KT18] for the problem of computing all-pairs max-flows in weighted _sparse_
graphs, which almost matches the obvious upper bound that follows from the
recent near-optimal max-flow algorithms [CKL+22, vdBCK+23].

##  2 Preliminaries

In this paper we deal with _directed_ graphs. We write $V(G)$ and $E(G)$ to
denote the sets of vertices and edges of $G$, respectively. We omit $G$ when
the graph in consideration is clear from the context. We write $e=uv\in E(G)$
when referring to edges of $G$. We call $u$ the tail of $e$, and $v$ the head
of $e$.

The graphs we deal with are _weighted_ , i.e., the edges have either weights
or costs assigned (but not both). Following the literature, when dealing with
minimum cost flow problems, we stick to the term _cost_ , and when talking
about shortest paths or negative cycles, we use the term _weight_. We use
$w_{G}(uv)$ to denote the weight of an edge $uv$, and $c_{G}(uv)$ to denote
its cost. The domain of possible edge weights/costs may vary, but will be
always either stated explicitly or clear from the context. The subscript is
dropped when it is clear which graphs‘s weights/costs we are referring to.

The _cost_ or _length_ of the path $\ell(P)$ is defined as
$\ell(P)=\sum_{i=1}^{k}c(e_{i})$ or $\ell(P)=\sum_{i=1}^{k}w(e_{i})$,
depending on whether edges have costs or weights assigned.

The _distance_ $\delta_{G}(u,v)$ between the vertices $u,v\in V(G)$ is the
length of the _shortest_ , i.e., minimum-cost/minimum-length $u\to v$ path in
$G$ or $\infty$, if no $u\to v$ path exists in $G$. Note that the distance is
well-defined only if $G$ contains no negative cycles.

We call any function $p:V\to\mathbb{R}$ a _price function_ on $G$. The
_reduced cost_ (_reduced weight_) of an edge $uv=e\in E$ wrt. $p$ is defined
as $c_{p}(e):=c(e)-p(u)+p(v)$ ($w_{p}(e)=w(e)-p(u)+p(v)$, resp.). We call $p$
a _feasible price function_ 444In the shortest paths literature (e.g.,
[Gol95]), the price of the edge’s tail is usually added to $w(e)$, and the
price of the head is subtracted. But in the min-cost flow literature (e.g.,
[GHKT17]), it is the other way around. We stick to the latter definition even
when talking about shortest paths. of $G$ if each $e\in E$ has non-negative
reduced cost/weight wrt. $p$.

It is known that $G$ has no negative-cost/weight cycles (negative cycles, in
short) iff some feasible price function $p$ for $G$ exists. If $G$ has no
negative cycles, distances in $G$ are well-defined.

######  Fact 2.1.

Suppose $G$ has no negative cycles. Suppose $s$ can reach all vertices of $G$.
Then the _minus distance_ function $p(v):=-\delta_{G}(s,v)$ is a feasible
price function of $G$.

##  3 Data structural abstractions and negative cycle detection

In this section we define the interface of abstract graph data structures
whose operations constitute the bottleneck of our min-cost circulation
algorithm that is in turn used to efficiently find negative cycles in dense
distance graphs built upon $r$-divisions of planar graphs (Theorem 4.3). The
missing proofs from this section can be found in Section 9.

###  3.1 Graph near neighbor data structure

Let $G=(V,E)$ be a directed graph with edge costs given by $w:E\to\mathbb{R}$.
After some preprocessing of $G$, a _graph near neighbor data structure_ on $G$
has the following interface.

  1. 1.

_Initialization_ with a subset $T\subseteq V$ and two mappings
$p:T\to\mathbb{R}$ (vertex prices), and $\tau:V\to\mathbb{R}$ (vertex
thresholds).

  2. 2.

_Near neighbor query_ : given $v\in V$, compute an incident edge $vt=e\in E$
with $t\in T$, such that

$w(e)+p(t)<\tau(v).$

If no such $e$ exists, $\perp$ is returned.

  3. 3.

_Deactivation_ of $t\in T$ removes $t$ from the subset $T$.

The _total update time_ of the graph near neighbor data structure is defined
as the total time needed for initialization and processing an arbitrary
sequence of deactivations resulting in $T=\emptyset$. The _query time_ is the
time needed for processing a near neighbor query.

For a graph $H$, we denote by $T_{\mathrm{nn}}(H)=\Omega(|V(H)|)$ its total
update time and by $Q_{\mathrm{nn}}(H)=\Omega(1)$ its query time. We assume
that these bounds hold only after suitably preprocessing $H$ (possibly given
implicitly) in time $P_{\mathrm{nn}}(H)$. The reason why preprocessing is not
included in the total update time is that the preprocessing can be shared by
many instantiations of the data structure.

######  Observation 3.1.

For a digraph $G=(V,E)$ with $n$ vertices and $m$ edges given explicitly,
there exists a near neighbor data structure with $T_{\mathrm{nn}}(G)=O(m+n)$
and $Q_{\mathrm{nn}}(G)=O(1)$.

The following lemma allows composing graph near neighbor data structures
efficiently.

######  Lemma 3.2.

Let $G_{1}=(V_{1},E_{1}),\ldots,G_{k}=(V_{k},E_{k})$ be weighted digraphs with
preprocessed near neighbor data structures. There exists a near neighbor data
structure for $\bigcup_{i=1}^{k}G_{i}$ that requires no further preprocessing
and satisfies

$\displaystyle T_{\mathrm{nn}}\left(\bigcup_{i=1}^{k}G_{i}\right)$
$\displaystyle=\sum_{i=1}^{k}\left(T_{\mathrm{nn}}(G_{i})+|V_{i}|\cdot
Q_{\mathrm{nn}}(G_{i})+O(|V_{i}|)\right),$ $\displaystyle
Q_{\mathrm{nn}}\left(\bigcup_{i=1}^{k}G_{i}\right)$
$\displaystyle=\max_{i=1}^{k}\\{Q_{\mathrm{nn}}(G_{i})\\}+O(1).$

###  3.2 Graph closest pair data structure

Let $G=(V,E)$ be as in Section 3.1. Let $S,T\subseteq V$ and let
$\alpha:S\to\mathbb{R}$ and $\beta:T\to\mathbb{R}$ be vertex weights. A _graph
closest pair data structure_ on $G$ explicitly maintains an edge $st=e^{*}\in
E\cap(S\times T)$ (if exists) such that

$d(e^{*}):=w(e^{*})+\alpha(s)+\beta(t)$

is minimized. After preprocessing $G$ (possibly given implicitly), it has the
following interface.

  1. 1.

_Initialization_ with specified sets $S,T\subseteq V$, and mappings
$\alpha,\beta$.

  2. 2.

_Activation_ of $s\in V\setminus S$ so that $s$ gets inserted into $S$ (with a
given value $\alpha(s)$).

  3. 3.

_Extraction_ of $t\in T$, so that $t$ gets removed from $T$.

The _total update time_ of the graph closest pair data structure is defined as
the total time needed for initialization and processing an arbitrary sequence
of (at most $n-|S_{0}|$, where $S_{0}$ is the initial set $S$) activations and
(at most $|T_{0}|$, where $T_{0}$ is the initial set $T$) extractions.

We denote by $T_{\mathrm{cp}}(H)=\Omega(|V(H)|)$ the total update time of a
graph closest pair data structure on an appropriately preprocessed graph $H$.

Below we state some useful observations about the above closest pair
abstraction.

######  Fact 3.3.

For a single-edge digraph $G$, there exists a graph closest pair data
structure with total update time $T_{\mathrm{cp}}(G)=O(1)$.

######  Lemma 3.4.

[CE01] Given a feasible price function $p$ and a preprocessed graph closest
pair data structure on $G$, the distances $\delta_{G}(s,\cdot)$ from any
source $s$ can be computed in $\widetilde{O}\left(T_{\mathrm{cp}}(G)\right)$
time.

###### Proof.

We initialize a graph closest pair data structure $\mathcal{D}$ on $G$ with
$S=\\{s\\}$, $\alpha(s):=-p(s)$, $T=V\setminus S$, $\beta(t):=p(t)$.

We simulate Dijkstra‘s algorithm on $G$ using $\mathcal{D}$. Recall that
Dijkstra‘s algorithm maintains a growing set $S$ (initially $S=\\{s\\}$) of
vertices $v$ for which distances $\delta_{G}(s,v)$ are known and repeatedly
picks vertices $z$ minimizing

$g(z):=\min_{vz=e\in E\cap(S\times(V\setminus
S))}\\{\delta_{G}(s,v)+(w_{G}(e)-p(v)+p(z))\\},$ (1)

and subsequently establishes that $\delta_{G}(s,z)$ equals $g(z)$ and extends
$S$ with $z$. We can indeed achieve the same using the data structure
$\mathcal{D}$ as follows. Whenever Dikstra‘s algorithm establishes some
distance $\delta_{G}(s,a)$, we activate $a$ in $\mathcal{D}$ with
$\alpha(a):=\delta_{G}(s,a)-p(a)$. For finding next $z\in T$ minimizing
$g(z)$, observe that the edge $e^{*}=vz$ maintained by $\mathcal{D}$ is the
one minimizing $g(z)$ over the set $T$. To maintain the invariant that
$T=V\setminus S$ in $\mathcal{D}$, we simply extract $z$ from $\mathcal{D}$
after activating $z$ in $S$.

Clearly, such an implementation of Dijkstra‘s algorithm runs in $O(n)$ time
plus the total update time of $\mathcal{D}$, which is $\Omega(n)$. ∎

######  Lemma 3.5.

Let $G_{1}=(V_{1},E_{1}),\ldots,G_{k}=(V_{k},E_{k})$ be weighted digraphs with
preprocessed closest pair data structures. There exists a graph closest pair
data structure for $\bigcup_{i=1}^{k}G_{i}$ with no further preprocessing
required and total update time

$T_{\mathrm{cp}}\left(\bigcup_{i=1}^{k}G_{i}\right)=\sum_{i=1}^{k}T_{\mathrm{cp}}(G_{i})+\sum_{i=1}^{k}O(|V_{i}|\log{k}).$

###  3.3 Negative cycle detection

Having defined the data structural abstractions, we are now ready to state the
following result giving an upper bound on the running time of a negative cycle
detection algorithm in terms of the performance characteristics of the assumed
graph data structures.

######  Theorem 3.6.

Let $G$ be a graph with integer edge weights in $[-C,\infty)$. Suppose closest
pair and near neighbor data structures have been preprocessed for $G$. Then,
one can test whether $G$ contains a negative cycle (and possibly find one) in

$\widetilde{O}\left(\sqrt{n}\cdot(T_{\mathrm{cp}}(G)+T_{\mathrm{nn}}(G)+n\cdot
Q_{\mathrm{nn}}(G))\log{C}\right)$

time. If no negative cycle is detected, a feasible price function $p$ of $G$
is returned.

We give an overview of the techniques behind the algorithm of Theorem 3.6 and
compare it with the previous scaling approaches in Section 4.3. A complete
proof can be found in Section 7.

##  4 Technical overview

In this section we give an overview of the techniques used in (1) our results
for planar graphs regarding negatively-weighted SSSP and max $s,t$-flow
oracles and (2) our min-cost circulation framework for general graphs with
efficient graph near neighbor and closest pair data structures.

###  4.1 Negative cycle detection in DDGs and planar digraphs

All the previous near-optimal algorithms for negative cycle detection in
planar digraphs [FR06, KMW10, MW10] rely on an efficient implementation of the
Bellman-Ford algorithm on so-called _dense distance graphs_ built upon _$r$
-divisions with few holes_.

Let us now introduce these and some other standard planar graph tools in more
detail. Once again, an _$r$ -division_ [Fre87] $\mathcal{R}$ of a planar
graph, for $r\in[1,n]$, is a decomposition of a planar graph $G$ into $O(n/r)$
_pieces_ $P\subseteq G$ of size $O(r)$ such that each piece $P$ shares
$O(\sqrt{r})$ vertices with other pieces. The shared vertices of a piece $P$,
denoted $\partial{P}$, are called its _boundary vertices_. We denote by
$\partial{\mathcal{R}}$ the set $\bigcup_{P\in\mathcal{R}}\partial{P}$. If
additionally all pieces of $\mathcal{R}$ are connected, and the boundary
vertices of each piece $P\in\mathcal{R}$ are distributed among $O(1)$ faces of
$P$ (containing boundary vertices exclusively, also called the holes555This
definition is slightly more general than usually. Namely, the definition of an
$r$-division does not assume a fixed embedding of the entire $G$; it only
assumes some fixed embeddings of individual pieces. of $P$), we call
$\mathcal{R}$ an _$r$ -division with few holes_.

######  Theorem 4.1 ([KMS13]).

Let $G$ be a simple triangulated connected plane graph with $n$ vertices. For
any $r\in[1,n]$, an $r$-division with few holes of $G$ can be computed in
$O(n)$ time.

A dense distance graph $\mathrm{DDG}(\mathcal{R})$ built upon $\mathcal{R}$ is
obtained by unioning, for each piece $P\in\mathcal{R}$, a complete weighted
graph $\mathrm{DDG}(P)$ on $\partial{P}$ encoding distances between vertices
$\partial{P}$ in $P$. The graph $\mathrm{DDG}(\mathcal{R})$ has
$O(n/\sqrt{r})$ vertices and $O(n)$ edges. Dense distance graphs are typically
constructed using the following _multiple-source shortest paths_ data
structure.

######  Theorem 4.2 (MSSP [CCE13, Kle05]).

Let $G=(V,E)$ be a plane digraph with a distinguished face $f$. Suppose a
feasible price function on $G$ is given. Then, in $O(n\log{n})$ time one can
construct a data structure that can compute $\delta_{G}(s,t)$ for any query
vertices $s\in V(f)$, $t\in V$ in $O(\log{n})$ time.

A naive implementation of the Bellman-Ford algorithm on
$\mathrm{DDG}(\mathcal{R})$ runs in $O(n^{2}/\sqrt{r})$ time. [FR06, KMW10,
MW10] showed how to implement the Bellman-Ford algorithm on
$\mathrm{DDG}(\mathcal{R})$ in
$\widetilde{O}(|V(\mathrm{DDG}(\mathcal{R}))|^{2})=\widetilde{O}(n^{2}/r)$
time. Using this implementation for $r=\Theta(n)$ or
even$r=n/\operatorname{polylog}{n}$, in combination with recursion, one
obtains near-linear (strongly polynomial) running time, which [MW10] manage to
optimize to $O(n\log^{2}{n}/\log\log{n})$. To obtain Theorem 1.6 and all the
other results for planar graphs in this paper, we prove the following.

######  Theorem 4.3.

Let $\mathcal{R}$ be an $r$-division with few holes of a planar digraph $G$
whose edge weights are integers in $[-C,\infty)$. Given
$\mathrm{DDG}(\mathcal{R})$, one can either detect a negative cycle in
$\mathrm{DDG}(\mathcal{R})$ or compute its feasible price function in
$\widetilde{O}\left(|V(\mathrm{DDG}(\mathcal{R}))|^{3/2}\log{C}\right)=\widetilde{O}(n^{3/2}/r^{3/4}\cdot\log{C})$
time.

Let us first explain how Theorem 3.6 implies Theorem 4.3. Let $\mathcal{R}$ be
an $r$-division with few holes of $G$. It is well-known [FR06, MW10, GK18]
that for $P\in\mathcal{R}$, $\mathrm{DDG}(P)$, seen as a matrix with rows and
columns $\partial{P}$, can be expressed as an element-wise minimum of a number
of _full Monge matrices_ 666An $n\times m$ matrix $\mathcal{M}$ is called
_Monge_ , if for any rows $a\preceq b$ and columns $c\preceq d$ we have
$\mathcal{M}_{a,c}+\mathcal{M}_{b,d}\leq\mathcal{M}_{a,d}+\mathcal{M}_{b,c}$.
$\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ with a total of
$\widetilde{O}(|\partial{P}|)$ rows and columns (counting with
multiplicities). For $m_{1}\times m_{2}$ Monge matrices, [MNW18, Lemma 1]
showed an efficient data structure that allows to deactivate columns and
supports queries for a minimum element in a row (limited to the remaining
active columns only). The data structure has total update time
$\widetilde{O}(m_{1}+m_{2})$ and supports queries in $\widetilde{O}(1)$ time.
Such a data structure for $\mathcal{M}_{i}$ can be used in a trivial way to
implement a _near neighbor_ data structure on a graph $G_{\mathcal{M}_{i}}$
whose edges correspond to the elements of $\mathcal{M}_{i}$, so that
$T_{\mathrm{nn}}(G_{\mathcal{M}_{i}})=\widetilde{O}(|V(G_{\mathcal{M}_{i}})|)=\widetilde{O}(|\partial{P}|)$
and $Q_{\mathrm{nn}}(G_{\mathcal{M}_{i}})=\widetilde{O}(1)$. That data
structure, combined with the _Monge heap_ of [FR06], can be used to obtain a
closest pair data structure on $G_{\mathcal{M}_{i}}$ with
$T_{\mathrm{cp}}(G_{\mathcal{M}_{i}})=\widetilde{O}(|\partial{P}|)$. But the
graphs $\bigcup_{i=1}^{k}G_{\mathcal{M}_{k}}$ and $\mathrm{DDG}(P)$ have the
same distances between the vertices $\partial{P}$, and thus by Lemmas 3.5 and
3.2, we also have
$T_{\mathrm{cp}}(\mathrm{DDG}(P)),T_{\mathrm{nn}}(\mathrm{DDG}(P))\in\widetilde{O}(|\partial{P}|)=\widetilde{O}(\sqrt{r})$,
and $Q_{\mathrm{nn}}(\mathrm{DDG}(P))=\widetilde{O}(1)$. Applying Lemmas 3.5
and 3.2 once again, we obtain
$T_{\mathrm{cp}}(\mathrm{DDG}(\mathcal{R})),T_{\mathrm{nn}}(\mathrm{DDG}(\mathcal{R}))\in\widetilde{O}(n/\sqrt{r})$
and $Q_{\mathrm{nn}}(\mathrm{DDG}(\mathcal{R}))=\widetilde{O}(1)$. By plugging
these bounds in Theorem 3.6, we obtain Theorem 4.3.

Given an efficient negative cycle detection algorithm on $r$-divisions, for
negative cycle detection in planar digraphs, we apply the same recursive
strategy as previous works [FR06, KMW10, MW10] did. However, we reduce the
graph size in the recursive calls much more aggressively. First, an
$r$-division with few holes is computed in linear time for $r=n^{8/9}$. Then,
the algorithm is run recursively on the individual pieces of $\mathcal{R}$. If
no piece $P$ has a negative cycle fully contained in $P$, we only need to look
for negative cycles going through
$\partial{\mathcal{R}}=\bigcup_{P\in\mathcal{R}}\partial{P}$. To this end,
$\mathrm{DDG}(\mathcal{R})$ is first built using the obtained per-piece
feasible price functions and the MSSP algorithm [Kle05]. This takes
$O(n\log{n})$ time. Then, the algorithm of Theorem 4.3 is run on
$\mathrm{DDG}(\mathcal{R})$, which takes
$\widetilde{O}(n^{3/2}/r^{3/4}\log{C})=\widetilde{O}(n^{5/6}\log{C})$ time. A
feasible price function of $G$ can be computed out of the price function on
$\mathrm{DDG}(\mathcal{R})$ and the individual per-piece price functions in
$O(n\log{n})$ time.

The time cost $T(n)$ of this algorithm satisfies
$T(n)=O(n\log{n})+\widetilde{O}(n^{5/6}\log{C})+\sum_{P\in\mathcal{R}}T(|P|)$.
Intuitively, the bound $T(n)=O(n\log{n}+n\log{C})$ holds because (a) at each
level of recursion, except possibly the leafmost levels, the total sum of
$\widetilde{O}(n^{5/6}\log{C})$ terms is $o(n\log{C})$, and (b) by summing the
$O(n\log{n})$ terms in subsequent levels of the recursion tree, we have:

$n\log{n}+n\log{n^{8/9}}+n\log{n^{(8/9)^{2}}}+\ldots\leq
n\log{n}\cdot\sum_{i=0}^{\infty}(8/9)^{i}=O(n\log{n}).$

###  4.2 Max $s,t$-flow oracles

Our developments for max-flow oracles build upon a well-known reduction of the
decision variant of the max $s,t$-flow problem on a planar digraph to the
negative cycle detection problem. In the recent literature [Eri10, Nus14],
this reduction is generally attributed to an unpublished manuscript by
Venkatesan (and also appears in [JV83]). The reduction has been generalized to
arbitrary vertex demands in [MN95].

Assume that each edge of $G$ comes with a reverse edge of capacity $0$. This
does not influence the amounts of flow that one can send in this graph. Let
$\lambda\geq 0$. Pick an arbitrary $s\to t$ path $Q_{s,t}$ in $G$. Let
$G_{\lambda}$ be obtained by decreasing the capacity of each edge $e$ of
$Q_{s,t}$ by $\lambda$, and increasing the capacity of the reverse of $e$ by
$\lambda$.

######  Lemma 4.4.

There exits an $s,t$-flow of value $\lambda$ in $G$ iff the dual
$G_{\lambda}^{*}$ of $G_{\lambda}$ has no negative cycles.

For some intuition behind this reduction, see Section 6.1. A full proof can be
found, e.g., in [Eri10]. Note that the reduction allows binary searching for
the maximum $s,t$-flow value. For example, using Theorem 1.6, for integral
capacities in $[1,C]$, one can compute a maximum $s,t$-flow value in
$O(n\log^{2}(nC))$ time. However, this bound is worse and less general than
the best known strongly polynomial $O(n\log{n})$ bound [BK09, Eri10] achieved
without applying this reduction directly. Nevertheless, the reduction is quite
powerful, e.g., in the parallel setting [MN95, KS21].

##### Feasible flow oracle.

Let us first consider the $\lambda$-feasible flow oracle problem, where
$\lambda$ is fixed and we only need to support queries about whether for a
given pair $(s,t)$ the max $s,t$-flow value is at least $\lambda$. Clearly, we
cannot simply find, upon query, a path $Q_{s,t}\in G$, and explicitly adjust
its capacities since such a path can have length $\Theta(n)$. In order to make
use of Lemma 4.4 for many distinct pairs $(s,t)$, we use it combined with a
_recursive decomposition_ $\mathcal{T}(G^{*})$ of the dual graph $G^{*}$ using
cycle separators [Mil84]. Such a decomposition can be computed in linear time
[KMS13]. $\mathcal{T}(G^{*})$ is a tree of connected subgraphs of $G^{*}$
rooted at $G^{*}$, has $O(\log{n})$ depth, and the total size of pieces of
$\mathcal{T}(G^{*})$ is $\widetilde{O}(n)$. Moreover, every piece
$H\in\mathcal{T}(G^{*})$ has at most $\widetilde{O}(\sqrt{n})$ boundary
vertices $\partial{H}$ (i.e., vertices shared with pieces of
$\mathcal{T}(G^{*})$ that are not ancestors nor descendants of $H$), and
$\sum_{H\in\mathcal{T}(G^{*})}|\partial{H}|^{2}=\widetilde{O}(n\log{n})$.

Given the decomposition, we construct a set $\mathcal{P}$ of paths in $G$ such
that for every $(s,t)$, there exists an $s\to t$ path in $G$ that can be
decomposed into $O(\log{n})$ paths from $\mathcal{P}$. Specifically, the set
$\mathcal{P}$ consists of small individual per-piece sets $\mathcal{P}_{H}$,
$H\in\mathcal{T}(G^{*})$, such that $|\mathcal{P}_{H}|=\widetilde{O}(1)$ and
for every path $Q\in\mathcal{P}_{H}$, its dual edges $Q^{*}\subseteq G^{*}$
satisfy $Q^{*}\subseteq H$. Moreover, for every pair $(s,t)$, $G^{*}$ can be
efficiently decomposed into a collection $\mathcal{H}_{s,t}$ of $O(\log{n})$
pieces $H_{1},\ldots,H_{\ell}\in\mathcal{T}(G^{*})$ such that:

  1. 1.

$H_{1}\cup\ldots\cup H_{\ell}=G$, and no two of these pieces are in an
ancestor-descendant relationship,

  2. 2.

there exist paths
$Q_{1}\in\mathcal{P}_{H_{1}},\ldots,Q_{\ell}\in\mathcal{P}_{H_{\ell}}$ such
that $Q_{1}\cup\ldots\cup Q_{\ell}$ forms an $s\to t$ path in $G$, which we
fix as the chosen path $Q_{s,t}$ (as required by the reduction) for that pair
$(s,t)$.

Next, roughly speaking, for every $H\in\mathcal{T}(G^{*})$ and
$Q\in\mathcal{P}_{H}$, we preprocess a dense distance graph
$\mathrm{DDG}(G^{*}_{\lambda}[H],Q)$ (defined, again, as a distance clique on
$\partial{H}$) of the induced subgraph $G^{*}_{\lambda}[H]$ under the
assumption that $G^{*}_{\lambda}[H]\cap Q^{*}_{s,t}=Q^{*}$. Building one such
$\mathrm{DDG}(G^{*}_{\lambda}[H],Q)$ (after either finding a feasible price
function of $G^{*}_{\lambda}[H]$ or detecting a negative cycle) costs
$\widetilde{O}(|H|+|\partial{H}|^{2})$ time using the strongly polynomial
negative cycle detection algorithm [MW10] and the MSSP algorithm [Kle05].
Since $|\mathcal{P}_{H}|=\widetilde{O}(1)$, the total time spent on
preprocessing is
$\widetilde{O}\left(\sum_{H\in\mathcal{T}(G^{*})}|H|+|\partial{H}|^{2}\right)=\widetilde{O}(n)$.

Given the preprocessing, the intuition behind the query algorithm is as
follows. First, we compute the collection
$\mathcal{H}_{s,t}=\\{H_{1},\ldots,H_{\ell}\\}$ as described above. For each
$H_{i}\in\mathcal{H}_{s,t}$, let $Q_{i}\in\mathcal{P}_{H_{i}}$ be the required
subpath of $Q_{s,t}$. Recall that to answer the query, it is enough to check
if $G^{*}_{\lambda}$ contains a negative cycle. We first check whether any of
the graphs $G^{*}_{\lambda}[H_{i}]$ (with $G^{*}_{\lambda}[H_{i}]\cap
Q^{*}_{s,t}=Q^{*}_{i}$) contains a negative cycle, which is an information
that we have precomputed. If not, then any negative cycle in $G^{*}_{\lambda}$
has to pass through a vertex from $\bigcup_{i=1}^{\ell}\partial{H_{i}}$. To
check if such a negative cycle exists, we run (a variant of) the algorithm of
Theorem 4.3 on the graph
$\bigcup_{i=1}^{\ell}\mathrm{DDG}(G^{*}_{\lambda}[H_{i}],Q_{i})$. Since this
graph has only $\widetilde{O}(n^{1/2})$ vertices, negative cycle detection
takes $\widetilde{O}(n^{3/4}\log{C})$ time as desired.

##### Dynamic feasible/approximate max $s,t$-flow oracle.

Turning the static feasible flow and approximate max $s,t$-flow oracles into
corresponding dynamic oracles requires using an _$r$ -division-aware_ version
of the decomposition $\mathcal{H}_{s,t}$, in which the pieces
$\mathcal{H}_{s,t}$ are only allowed to be weak descendants of some fixed
$r$-division $\mathcal{R}$ drawn from the nodes of $\mathcal{T}(G^{*})$ (such
$\mathcal{R}$ always exists [KMS13]). In such a case, $\mathcal{H}_{s,t}$ may
have size $\widetilde{\Theta}(n/r)$, and the corresponding graph
$\bigcup_{i=1}^{\ell}\mathrm{DDG}(G^{*}_{\lambda}[H_{i}],Q_{i})$ may have
$\widetilde{\Theta}(n/\sqrt{r})$ vertices, so the query time gets increased to
$\widetilde{O}(n^{3/2}/r^{3/4}\log{C})$. However, if some edge capacity is
updated, we need to recompute the data structures for only one piece of
$\mathcal{R}$ (and its descendants in $\mathcal{T}(G^{*})$), which takes
$\widetilde{O}(r)$ time. Setting $r=n^{6/7}$ balances the worst-case update
and query times.

##### Exact max $s,t$-flow oracle.

For answering exact max $s,t$-flow queries, we would like to find the maximum
$\lambda\in[0,nC]$ such that $G^{*}_{\lambda}$ does not contain a negative
cycle via binary search. The $r$-division-aware decomposition
$\mathcal{H}_{s,t}$, nor the implied path $Q_{s,t}$, do not depend on the
parameter $\lambda$. Therefore, we would be able to perform binary search in
$\widetilde{O}(n^{3/2}/r^{3/4}\log^{2}{C})$ time if only we had the dense
distance graphs $\mathrm{DDG}(G^{*}_{\lambda}[H_{i}],Q_{i})$ for
$i=1,\ldots,\ell$ precomputed for all parameters $\lambda$ generated on-line
by binary search. Unfortunately, we cannot afford to simply precompute these
graphs for all the $nC$ possible parameters $\lambda$. This would be too
costly even for unweighted graphs.

Recall from the reduction of Theorem 4.3 to Theorem 3.6, that for detecting a
negative cycle, we actually do not need the graphs
$\mathrm{DDG}(G^{*}_{\lambda}[H_{i}],Q_{i})$ themselves, but rather the
associated graph closest pair and near neighbor data structures. We prove that
after preprocessing a piece $H\in\mathcal{T}(G^{*})$ in
$\widetilde{O}(|H^{2}|)$ time, one can construct the required data structures
for $\mathrm{DDG}(G^{*}_{\lambda}[H],Q)$ (where $Q\in P_{H}$) for any _given_
$\lambda$, so that
$T_{\mathrm{cp}}(\mathrm{DDG}(G^{*}_{\lambda}[H],Q)),T_{\mathrm{nn}}(\mathrm{DDG}(G^{*}_{\lambda}[H],Q))\in\widetilde{O}(|\partial{H}|)$,
and $Q_{\mathrm{nn}}(\mathrm{DDG}(G^{*}_{\lambda}[H],Q))=\widetilde{O}(1)$. As
we need this preprocessing only for the pieces $H\in\mathcal{T}(G^{*})$ that
are weak descendants of $\mathcal{R}$, this costs
$\sum_{H\in\mathcal{T}(G^{*})}\widetilde{O}(|H|^{2})\leq\widetilde{O}(r)\cdot\sum_{H}\widetilde{O}(|H|)=\widetilde{O}(nr)$
time.

Recall that $\partial{H}$ lies on $O(1)$ holes $h^{1},\ldots,h^{k}$ of $H$. We
first decompose $\mathrm{DDG}(G^{*}_{\lambda}[H],Q)$ into subgraphs that
capture only shortest paths between $O(1)$ fixed pairs of holes $h^{i},h^{j}$.
We prove that for given $\lambda$, $h^{i}$, and $h^{j}$, the shortest paths
between the vertices $V(h^{i})$ of the hole $h^{i}$ and vertices $V(h^{j})$ of
the hole $h^{j}$ all cross the path $Q$ (seen as a curve in
$G^{*}_{\lambda}[H]$) _almost the same number of times_. More specifically,
the individual net numbers of crossings (or simply the _crossing numbers_) of
these shortest paths wrt. $Q$ differ by at most $O(1)$. Tracking crossing
numbers is useful, since the length of a path $P$ with crossing number $\pi$
in $G^{*}_{\lambda}[H]$ can be seen to be the length of $P$ in $G^{*}_{0}[H]$
shifted by $\lambda\cdot\pi$. This allows us to limit our attention to
constructing the required data structures for auxiliary graphs that encode
minimum lengths of such paths between $V(h^{i})$ and $V(h^{j})$ in
$G^{*}_{0}[H]$ that additionally have their crossing numbers wrt. $Q$ equal
precisely $\pi$, where $\pi$ is a parameter chosen in $O(1)$ possible ways
(which can be determined efficiently).

To solve the modified problem, we consider a graph $H^{\prime}$ obtained from
$H$ by first cutting $H$ along $Q$ and then gluing $2n+1$ copies of the cut
graph, numbered $-n,\ldots,n=|V(H)|$. The graph $H^{\prime}$ is conceptually
similar to the infinite ’’universal cover‘‘ graph from [Eri10, Section 2.4].
The crucial property of $H^{\prime}$ is that the distance between the $0$-th
copy of $u\in V(h^{i})$ and the $\pi$-th copy of $v\in V(h^{j})$ in
$H^{\prime}$ equals the minimum length of a _simple_ $u\to v$ path in $H$ with
crossing number wrt. $Q$ precisely $\pi$. This way, we reduce our modified
problem to constructing the required data structures for a graph encoding
distances between some two holes of the much larger graph $H^{\prime}$.

Using an MSSP data structure [Kle05] built on $H^{\prime}$, we can access
distances from the $0$-th copy $h_{0}^{i}$ of $h^{i}$ to any specified copy
$h_{l}^{j}$ of $h^{j}$ in $\widetilde{O}(1)$ time. However, in order to
construct efficient closest pair/near neighbor data structures for a graph
encoding distances from $h_{0}^{i}$ to $h_{\pi}^{j}$, we need to be able to
organize these distances into Monge matrices. While this is easy if
$h_{0}^{i}=h_{\pi}^{j}$, it is more problematic if these holes are distinct.
[MW10] deal with this general problem using additional _near-linear_
preprocessing _per each pair of holes_ of interest, that allows to decompose
the respective distance matrix into element-wise minimum of two _full_ (i.e.,
rectangular) Monge matrices. Unfortunately, in our case we need to handle
$\Theta(|H|)$ pairs of holes $(h_{0}^{i},h_{l}^{j})$ (for all
$j=-n,\ldots,n$), so using their approach would lead to $O(|H|^{3})$-time
preprocessing per piece, which in our case would eventually prevent us from
achieving subquadratic preprocessing and sublinear query time.

We develop a more involved method which allows to achieve the goal for single
_source hole_ and all _target holes_ at once using near-linear preprocessing.
However, the produced decomposition involves element-wise minimum of two so-
called _partial_ Monge matrices which are slightly more difficult to handle.
Fortunately, any $m\times m$ partial Monge matrix can be decomposed into full
Monge matrices with $\widetilde{O}(m)$ total rows and columns [GMW20].
Consequently, efficient closest pair and near neighbor data structures can be
constructed as was the case for piecewise dense distance graphs in Theorem
4.3.

###  4.3 Min-cost circulations and negative cycle detection in general graphs

We use the term _vertex splitting_ to refer to the following graph
transformation: for each $v\in V$, create two vertices
$v_{\textrm{in}},v_{\textrm{out}}$, and for each non-loop edge $uv=e\in E$
(i.e., $u\neq v$), replace it with an edge $u_{\textrm{out}}v_{\textrm{in}}$
of the same weight. As shown by the following lemmas (proved in Section 9),
graph near-neighbor and closest pair data structures are well-behaved under
vertex splitting.

######  Observation 4.5.

Suppose a graph near neighbor data structure has been preprocessed for $G$. If
the graph $G^{\prime}=(V^{\prime},E^{\prime})$ is obtained from $G=(V,E)$ by
vertex splitting, then with no additional preprocessing we have
$T_{\mathrm{nn}}(G^{\prime})=O(T_{\mathrm{nn}}(G))$ and
$Q_{\mathrm{nn}}(G^{\prime})=O(Q_{\mathrm{nn}}(G))$.

######  Lemma 4.6.

Suppose a graph closest pair data structure has been preprocessed for $G$. If
the graph $G^{\prime}=(V^{\prime},E^{\prime})$ is obtained from $G=(V,E)$ by
vertex splitting, then with no additional preprocessing we have and
$T_{\mathrm{cp}}(G^{\prime})=\widetilde{O}(T_{\mathrm{cp}}(G))$.

Gabow [Gab85] gave an elegant vertex splitting-based reduction of the integral
negative cycle detection problem to the minimum-cost perfect matching problem
with acceptable additive error $O(1/n)$. In the proof of Theorem 3.6, we use a
similar reduction777We use this approach, instead of e.g., adapting the more
direct Goldberg’s scaling algorithm [Gol95] for negative cycle detection
because it is easily described in terms of repeated non-negative shortest
paths computations [KS19], for which very efficient algorithms on dense
distance graphs (see Section 4.1) are known [FR06]., but instead of
considering matchings, we find it more convenient to reduce to the minimum-
cost circulation problem in a network satisfying the following: for each
vertex $v$, the minimum $\lambda_{v}$ of the total capacity of $v$‘s incoming
edges and the total capacity of $v$‘s outgoing edges satisfies
$\lambda_{v}=1$. This resembles so-called ’’type 2‘‘ networks from [ET75,
GHKT17], for which classical combinatorial unit-capacity flow algorithms
[ET75, GHKT17] run in $O(\sqrt{n}m)$ time as opposed to $O(m^{3/2})$ time. In
the reduction that we apply, the transformed graph for which we want to solve
the min-cost circulation instance consists of all the edges of $G$
(uncapacitated) and $O(n)$ auxiliary unit-capacity edges.

The reduction allows us to focus on the more general min-cost circulation
problem with the additional parameter $\Lambda:=\sum_{v\in V}\lambda_{v}$. For
arbitrary values of $\Lambda\geq n$, in Section 8 (Theorem 7.1) we prove that
a $\delta$-additive approximation of the min-cost circulation can be computed
in time

$\widetilde{O}\left(\sqrt{\Lambda}\log{(\Lambda
C/\delta)}\cdot\left(T_{\mathrm{cp}}(G_{\infty})+T_{\mathrm{nn}}(G_{\infty})+m_{\mathrm{fin}}+\Lambda\cdot
Q_{\mathrm{nn}}(G_{\infty})\right)\right).$ (2)

Here, $G_{\infty}\subseteq G$ is the subgraph of $G$ containing all the
uncapacitated edges, and $m_{\mathrm{fin}}$ is the number of finite-capacity
edges in $G$. Recall that in the instance arising from the reduction, we have
$G_{\infty}=G$, $\Lambda=n$ and $m_{\mathrm{fin}}=O(n)$, and we need additive
error $\delta=O(1/n)$. This is how Theorem 3.6 follows from the bound (2)
proved in Theorem 7.1.

The minimum-cost circulation algorithm of Section 8 is a modification of a
simple successive shortest augmenting path algorithm for min-cost circulation
in unit-capacity networks, as described in [KS19]. The outer loop of the
algorithm implements the successive approximation framework of [GT90]: each
iteration (called _refinement_) is supposed to convert a
$2\epsilon$-approximate min-cost circulation into an $\epsilon$-approximate
circulation. Since a trivial zero circulation is always a $\Theta(\Lambda\cdot
C)$-approximate min-cost circulation, using $O(\log{(\Lambda C/\delta)})$
refinement steps, it can be turned into a circulation whose cost differs from
the optimum by at most $\delta$.

In [KS19], the refinement step first converts the input circulation into a
flow $f$ that is trivially minimum-cost, but violates conservation, i.e. $f$
is not a circulation. Next, it suitably _rounds_ the edge costs $c$ in the
residual network $G_{f}$ up to nearest multiple of $\epsilon$, this way
obtaining a modified _discretized_ cost function $c^{\prime}$. Then, it
gradually converts $f$ into a circulation by sending flow from excess to
deficit vertices in $G_{f}$ while maintaining that $f$ is minimum-cost wrt.
costs $c^{\prime}$. More specifically, it simply runs $O(\sqrt{\Lambda})$
_augmentation_ steps888In [KS19], only the $O(\sqrt{m})$ bound on the number
of augmentation steps is proven for unit-capacity networks. For such networks,
only the bound $\Lambda=O(m)$ can be proven with no additional assumptions. We
extend their analysis (based on [GHKT17]) to networks with integer or infinite
capacities and arbitrary values $\Lambda$. sending flow along a maximal set of
edge-disjoint shortest paths (wrt. $c^{\prime}$) in $G_{f}$. Each such step in
turn can be split into substeps (1): a single-source distances computation and
(2): finding a maximal set of edge-disjoint paths consisting of edges with
reduced cost $0$ using a DFS-like procedure (both can be implemented in
$\widetilde{O}(m)$ time).

Compared to [KS19], our refinement procedure avoids rounding for the following
reason: we want to keep the subgraph $G_{\infty}$ with unchanged costs in the
residual network at all times, since we want to benefit from closest pair and
near neighbor data structures for $G_{\infty}$. These data structures could
have, in principle, much worse performance if applied to e.g., a subgraph of
$G_{\infty}$ or $G_{\infty}$ with perturbed costs. On the other hand, without
rounding, the bound $O(\sqrt{\Lambda})$ on the number of augmentation steps
fails to hold due to lack of discretization of possible lengths of shortest
augmenting paths. Nevertheless, we show that such a bound still holds if we
(i) only increase the cost of $O(\Lambda)$ edges in $G_{f}\setminus G$ by
$\epsilon$, and (ii) after computing distances in substep (1), we augment the
flow through a maximal set of _nearly-tight_ edges in substep (2), with
reduced costs less than $\epsilon/2$. In substep (1), the distances can be
computed using Lemma 3.4 in $\widetilde{O}(T_{\mathrm{cp}}(G_{f}))$ time. But
since graph closest pair data structures can be efficiently composed under
unions (Lemma 3.5) we have:

$T_{\mathrm{cp}}(G_{f})=T_{\mathrm{cp}}(G_{\infty})+T_{\mathrm{cp}}(G_{f}\setminus
G_{\infty})+\widetilde{O}(n)=T_{\mathrm{cp}}(G_{\infty})+\widetilde{O}(m_{\mathrm{fin}}+\Lambda).$

Similarly, to implement substep (2), we show a simple procedure whose running
time is dominated by the total update time $T_{\mathrm{nn}}(G_{f})$ of a graph
near neighbor data structure on $G_{f}$, and performing $O(\Lambda)$ queries
on such a data structure. Again, by Lemma 3.2, we get:

$T_{\mathrm{nn}}(G_{f})+Q_{\mathrm{nn}}(G_{f})\cdot
O(\Lambda)=T_{\mathrm{nn}}(G_{\infty})+Q_{\mathrm{nn}}(G_{\infty})\cdot
O(\Lambda)+\widetilde{O}(m_{\mathrm{fin}}+\Lambda).$

##  5 Negative-weight shortest paths in planar graphs

In this section we describe a recursive algorithm that, given a simple
connected plane digraph $G$ with integral edge weights at least $-C$, either
detects a negative weight cycle in $G$ or computes a feasible price function
of $G$. Assume that $C\geq 2$, so that $\log{C}\geq 1$.

If $G$ has $n\leq n_{0}$ vertices, where $n_{0}$ is a constant to be set
later, we solve the problem in $O(n^{2})=O(n_{0}^{2})=O(1)$ time using any
strongly polynomial algorithm, e.g., Bellman-Ford. So, in the following,
assume that $n$ is at least a sufficiently large constant.

Suppose $n>n_{0}$. We start by computing an embedding of $G$. We then
triangulate $G$ by adding bidirectional edges of weight $nC$ inside faces
whose bounding cycles have more than $3$ edges. Note that this cannot
introduce any new negative cycles to $G$ and the lower bound $-C$ on the
smallest weight still holds. Next, for $r<n$ to be set later, we build an
$r$-division with few holes $\mathcal{R}$ of $G$. This can be done in linear
time by Theorem 4.1. In the following, for $P\in\mathcal{R}$ we will use the
notation $|P|$ to refer to $|V(P)|$. Note that we have
$\sum_{P\in\mathcal{R}}|P|=n+O(n/\sqrt{r})$ by the definition of boundary
vertices. The individual pieces $P\in\mathcal{R}$ may have non-simple (that
is, whose bounding cycles are not simple cycles) holes. For simplicity, in the
following part of this section we assume this is not the case and discuss how
to deal with non-simple holes in Section 10.

We then solve the problem recursively for each piece $P\in\mathcal{R}$. If any
of the recursive calls finds a negative cycle, $G$ has a negative cycle and we
can stop. Otherwise, let $p_{P}$ be the feasible price function of the piece
$P$. Observe that if $G$ has a negative cycle $O$ and none of the individual
pieces $P\in\mathcal{R}$ has one, then by splitting $O$ into a sequence of
maximal subpaths fully contained in some single piece, such a sequence will
have length at least $2$, and thus each of the subpaths will connect two
vertices of $\partial{R}$. Consequently, we can focus our attention on cycles
of that kind only. The following lemma is the key to achieving sublinear time
for detecting such negative cycles.

######  Lemma 5.1.

Suppose a feasible price function $p_{P}$ of $P\in\mathcal{R}$ is given. Then,
for $\mathrm{DDG}(P)$, there exist:

  * •

a closest pair data structure with total update time
$\widetilde{O}(|\partial{P}|)$.

  * •

a near neighbor data structure with total update time
$\widetilde{O}(|\partial{P}|)$ and query time $\widetilde{O}(1)$.

Both data structures require $O((|P|+|\partial{P}|^{2})\log{|P|})$
preprocessing time.

###### Proof.

To obtain efficient closest pair and near neighbor data structures for
$\mathrm{DDG}(P)$ we need it decomposed into Monge matrices. The following
lemma states the properties of such a decomposition proved in [FR06, MW10].

######  Lemma 5.2 ([FR06, MW10]).

Given a feasible price function $p_{P}$ of $P$, the graph $\mathrm{DDG}(P)$
(seen as a distance matrix) can be computed and decomposed into a set $D_{P}$
of Monge matrices whose sum of numbers of rows and columns (that are subsets
of $\partial{P})$ is $O(|\partial{P}|)$. For all $u,v\in\partial{P}$ we have:

  * •

for each $\mathcal{M}\in D_{P}$ such that $\mathcal{M}_{u,v}$ is defined,
$\mathcal{M}_{u,v}\geq\delta_{P}(u,v)$.

  * •

there exists $\mathcal{M}\in D_{P}$ such that $\mathcal{M}_{u,v}$ is defined
and $\mathcal{M}_{u,v}=\delta_{P}(u,v)$.

The decomposition can be computed in $O((|P|+|\partial{P}|^{2})\log{|P|})$
time.

Computing $\mathrm{DDG}(P)$ and the decomposition $D_{P}$ of Lemma 5.2
constitutes the only preprocessing for both desired data structures. As a
result, preprocessing takes $O((|P|+|\partial{P}|^{2})\log{|P|})$ time.

A Monge matrix $\mathcal{M}\in D_{P}$ can be also interpreted as a directed
graph $G_{\mathcal{M}}$ with vertices corresponding to the union of rows and
columns of $\mathcal{M}$, and a directed edge from $r$ to $c$ of weight
$\mathcal{M}_{r,c}$ if the entry $\mathcal{M}_{r,c}$ is defined.

[MNW18, Lemma 1] showed a data structure for $m_{1}\times m_{2}$ Monge
matrices that allows to deactivate columns and supports queries for a minimum
element in a row (limited to active columns only) and a contiguous range of
columns, given only black-box oracle access to the entries of the input
matrix. The data structure has total update time $\widetilde{O}(m_{1}+m_{2})$
and supports queries in $\widetilde{O}(1)$ time. Observe that such a data
structure for the matrix $\mathcal{M}^{\prime}$, obtained from $\mathcal{M}$
by shifting all entries in each column $c$ by some offset $p(c)$, can be used
to implement a near neighbor data structure on $G_{\mathcal{M}}$ with
$T_{\mathrm{nn}}(G_{\mathcal{M}})=\widetilde{O}(|V(G_{\mathcal{M}})|)$ total
update time and $Q_{\mathrm{nn}}(G_{\mathcal{M}})=\widetilde{O}(1)$ query
time. To see this, note first that $\mathcal{M}^{\prime}$ is also a Monge
matrix and can be accessed in $O(1)$ time. The deactivations of vertices in
the near neighbor data structure correspond to deactivations of columns of
$\mathcal{M}^{\prime}$. A near neighbor query can be handled using a single
query for a minimum element in a row of $\mathcal{M}^{\prime}$.

Let us now discuss a closest pair data structure of $G_{\mathcal{M}}$, where
$\mathcal{M}\in D_{P}$. We essentially use a variant of the Monge heap of
[FR06], which we now sketch for completeness. Again, let
$\mathcal{M}^{\prime\prime}$ be a Monge matrix obtained from $\mathcal{M}$ by
shifting every element in a row $r$ by $\alpha(r)$, and every element in a
column $c$ by $\beta(c)$. To get a desired closest pair data structure, it is
enough to have a data structure for $\mathcal{M}^{\prime\prime}$ that:

  1. (1)

starts with a subset of _active_ rows $S$ and columns $T$ for which the
offsets $\alpha$ and $\beta$ are known,

  2. (2)

maintains some minimum entry in $\mathcal{M}^{\prime\prime}$ (limited to the
active rows and columns),

  3. (3)

supports activations of rows $s\notin S$ revealing $\alpha(s)$ and
deactivations of columns $t\in T$.

It is well-known (see, e.g., [FR06]) that for a Monge matrix
$\mathcal{M}^{\prime\prime}$, there exist such a sequence
$\mathcal{S}=(r_{i},c_{i},d_{i})_{i=1}^{k}$, that:

  1. (a)

for each $i$, $c_{i}\preceq d_{i}$, the row $r_{i}$ is active and contains
some column minimum of each of the active columns between $c_{i}$ and $d_{i}$
(inclusive),

  2. (b)

the intervals $[c_{i},d_{i}]$ are disjoint and cover all active columns of
$\mathcal{M}^{\prime\prime}$, and

  3. (c)

the sequences $(r_{i})_{i=1}^{k}$, $(c_{i})_{i=1}^{k}$, $(d_{i})_{i=1}^{k}$
are monotonous wrt. natural orders $\prec$ on rows and columns of
$\mathcal{M}^{\prime\prime}$.

The data structure maintains such a sequence $\mathcal{S}$ subject to row
activations in $\mathcal{M}^{\prime\prime}$ in a balanced binary search tree.
We can even allow that $c_{i},d_{i}$ come from an initial set $T_{0}$ of
columns so that a column deactivation does not break the invariants posed on
$\mathcal{S}$. Additionally, for each $i$ we explicitly maintain a currently
active column $\gamma_{i}$ such that $c_{i}\preceq\gamma_{i}\preceq d_{i}$ and
$\mathcal{M}^{\prime\prime}_{r_{i},\gamma_{i}}$ is the minimum entry in the
subrow of $r_{i}$ spanned by (active) columns in $[c_{i},d_{i}]$. The values
$\mathcal{M}^{\prime\prime}_{r_{i},\gamma_{i}}$ are all stored in a sorted
multiset, so that their minimum $\psi$ is maintained efficiently. This way,
whenever $\gamma_{i}$ gets updated or deleted, $\psi$ is updated in
$\widetilde{O}(1)$ time. Observe that $\psi$ equals, in fact, the sought
minimum value in $\mathcal{M}^{\prime\prime}$ at all times.

Finally, we also build and maintain the data structure of [MNW18, Lemma 1] for
the matrix $\mathcal{M}^{\prime}$ (as in the near neighbor data structure,
with no row offsets $\alpha$ and all rows active, but including the column
offsets $\beta$) to allow subrow minimum queries and column deactivations in
$\mathcal{M}^{\prime}$.

Let us now describe how the data structure operates. The initial $\mathcal{S}$
can be constructed in $O(|V(G_{\mathcal{M}})|)$ time by finding the initial
column minima of $\mathcal{M}^{\prime\prime}$ using the algorithm of [AKM+87].

When a column $t\in T$ is deactivated, $\mathcal{S}$ needs no updates.
However, the value $\gamma_{j}$ for the unique $j$ such that $c_{i}\leq t\leq
d_{j}$ might change. Such a $j$ can be located in $\widetilde{O}(1)$ time
since $\mathcal{S}$ is stored in a BST. The new value $\gamma_{j}$ can be
found using a single subrow minimum query to the stored data structure of
[MNW18, Lemma 1] after processing the deactivation of $t$. Note that a subrow
minimum value in $\mathcal{M}^{\prime\prime}$ can be obtained from a subrow
minimum value in $\mathcal{M}^{\prime}$ by shifting the result by
$\alpha(r_{j})$.

Now suppose a row $s$ is activated. As in [FR06], the sequence $\mathcal{S}$
is updated as follows. First, one needs to identify such columns
$c^{*},d^{*}$, $c^{*}\preceq d^{*}$, that $s$ contains the minima in columns
in the range $[c^{*},d^{*}]$. To find such a $c^{*}$ in $\widetilde{O}(1)$
time, one can perform binary search using the previous $\mathcal{S}$: we need
to find a minimum $c^{*}$ such that if $(r_{j},c_{j},d_{j})$ satisfies
$c_{j}\preceq c^{*}\preceq d_{j}$, then
$\mathcal{M}_{r_{j},c^{*}}>\mathcal{M}_{s,c^{*}}$. As in [FR06], the Monge
property can be used to prove that binary search indeed works in this case.
Similarly, $d^{*}$ can be found in $\widetilde{O}(1)$ time. With $c^{*},d^{*}$
computed, if they exist, one needs to remove some number of elements
$(r_{i},c_{i},d_{i})$ with $[c_{i},d_{i}]\subseteq[c^{*},d^{*}]$ from
$\mathcal{S}$, insert $(t,c^{*},d^{*})$ at some index $l$ to $\mathcal{S}$,
and possibly update the values $d_{l-1}$ and $c_{l+1}$ of the two neighboring
elements of $(t,c^{*},d^{*})$ in $\mathcal{S}$. For each updated element of
$\mathcal{S}$, we recompute $\gamma_{i}$ as before (or remove it). While a row
activation can remove many elements from the sequence, it can cause at most
one insertion into the sequence, and thus the amortized update time is
$\widetilde{O}(1)$. As a result, for the closest pair data structure we get
$T_{\mathrm{cp}}(G_{\mathcal{M}})=\widetilde{O}(|V(G_{\mathcal{M}})|)$.

Consider a graph $H_{P}=\bigcup_{\mathcal{M}\in D_{P}}G_{\mathcal{M}}$. By
Lemma 3.5, we obtain a closest pair data structure for $H_{P}$ with

$T_{\mathrm{cp}}(H_{P})=\widetilde{O}\left(\sum_{\mathcal{M}\in
D_{P}}T_{\mathrm{cp}}(G_{\mathcal{M}})\right)=\widetilde{O}\left(\sum_{\mathcal{M}\in
D_{P}}|V(G_{\mathcal{M}})|\right)=\widetilde{O}(|\partial{P}|).$

Similarly, by Lemma 3.2 we obtain
$T_{\mathrm{nn}}(H_{P})=\widetilde{O}(|\partial{P}|)$ and
$Q_{\mathrm{nn}}(H_{P})=\widetilde{O}(1)$.

By Lemma 5.2, we have that $\mathrm{DDG}(P)\subseteq H_{P}$, and for each
$u,v\in V(H_{P})$, the minimum weight of an edge $uv=e$ in $H_{P}$ satisfies
$w_{H_{P}}(e)=w_{\mathrm{DDG}(P)}(uv)$. Since parallel edges with non-minimal
weight are effectively ignored by the closest pair and near neighbor data
structures, the respective data structures for $H_{P}$ can be used as
corresponding data structures for $\mathrm{DDG}(P)$. Hence, we obtain
$T_{\mathrm{cp}}(\mathrm{DDG}(P))=\widetilde{O}(|\partial{P}|)$,
$T_{\mathrm{nn}}(\mathrm{DDG}(P))=\widetilde{O}(|\partial{P}|)$ and
$Q_{\mathrm{nn}}(\mathrm{DDG}(P))=\widetilde{O}(1)$, as desired. ∎

By the definition of boundary vertices, we have that
$\mathrm{DDG}(G):=\bigcup_{P\in\mathcal{R}}\mathrm{DDG}(P)$ preserves
distances between the vertices of $\partial{\mathcal{R}}$ in $G$. As a result,
to detect a negative cycle that goes through at least two vertices of
$\partial{\mathcal{R}}$ in $G$, we can equivalently test whether the graph
$\mathrm{DDG}(G)$ has a negative cycle. Note that we have
$|V(\mathrm{DDG}(G))|\leq\sum_{P\in\mathcal{R}}|\partial{P}|=O(n/\sqrt{r})$.

Observe that by Lemma 5.1, the total time needed for preprocessing closest
pair and near neighbor data structures through all $\mathrm{DDG}(P)$ is:

$\sum_{P\in\mathcal{R}}O\left(|P|+|\partial{P}|^{2}\log{|P|}\right)=O(n/r)\cdot
O\left(\left(r+(\sqrt{r})^{2}\right)\log{r}\right)=O(n\log{n}).$

By applying Lemmas 3.5 and 3.2 to the data structures of Lemma 5.1, we obtain:

######  Corollary 5.3.

Given preprocessed closest pair and near neighbor data structures for all
$P\in\mathcal{R}$, there exist closest pair and near neighbor data structures
for $\mathrm{DDG}(G)$ such that:

$\displaystyle T_{\mathrm{cp}}(\mathrm{DDG}(G))$
$\displaystyle=\widetilde{O}\left(\sum_{P\in\mathcal{R}}|\partial{P}|\right)=\widetilde{O}(n/\sqrt{r}),$
$\displaystyle T_{\mathrm{nn}}(\mathrm{DDG}(G))$
$\displaystyle=\widetilde{O}\left(\sum_{P\in\mathcal{R}}|\partial{P}|\right)=\widetilde{O}(n/\sqrt{r}),$
$\displaystyle Q_{\mathrm{nn}}(\mathrm{DDG}(G))$
$\displaystyle=\widetilde{O}(1).$

As the edges of $\mathrm{DDG}(G)$ represent distances in individual pieces of
$\mathcal{R}$, edge weights in $\mathrm{DDG}(G)$ are integral and their
absolute values can be bounded by $O(rC)=O(nC)$. By applying Theorem 3.6 to
$\mathcal{D}:=\mathrm{DDG}(G)$, we obtain that one can test for a negative
cycle in $\mathrm{DDG}(G)$ (or find a feasible price function $q$ of
$\mathrm{DDG}(G)$) in

$\widetilde{O}\left(\sqrt{|V(\mathcal{D})|}\cdot(T_{\mathrm{cp}}(\mathcal{D})+T_{\mathrm{nn}}(\mathcal{D})+|V(\mathcal{D})|\cdot
Q_{\mathrm{nn}}(\mathcal{D}))\cdot\log{C}\right)=\widetilde{O}\left(\frac{n^{3/2}}{r^{3/4}}\log{C}\right)$

time. If no negative cycle in $\mathrm{DDG}(G)$ is found, we still need to
find a feasible price function of $G$.

######  Lemma 5.4.

Given feasible price functions $p_{P}$ of all pieces $P\in\mathcal{R}$, and a
feasible price function $q$ of $\mathrm{DDG}(G)$, one can compute a feasible
price function $p$ of $G$ in $O(n\log{n})+\widetilde{O}(n/\sqrt{r})$ time.

###### Proof.

Let $G^{\prime}$ ($\mathrm{DDG}^{\prime}(G)$) be obtained from $G$
($\mathrm{DDG}(G)$, resp.) by adding a super-source $s$ and connecting it to
all vertices $v$ of $G$ ($\mathrm{DDG}(G)$, resp.) using an edge of weight $0$
if $v\in\partial{\mathcal{R}}$ and of weight $nC$ if
$v\notin\partial{\mathcal{R}}$ (i.e., the auxiliary edges of weight $nC$
appear only in $G^{\prime}$). We will compute single-source distances in
$G^{\prime}$ from $s$, as $p(v):=-\delta_{G^{\prime}}(s,v)$ gives a feasible
price function of $G^{\prime}$, and thus also of $G$.

Observe that by Fact 3.3, Lemma 3.5 and Lemma 3.4 combined, using the price
function $q$ of $\mathrm{DDG}(G)$ (extended to $s$ so that $-q(s)$ is large
enough and $q$ becomes a feasible price function of
$\mathrm{DDG}(G)^{\prime}$) we can compute single-source distances from $s$ on
$\mathrm{DDG}^{\prime}(G)$ in
$\widetilde{O}(T_{\mathrm{cp}}(\mathrm{DDG}^{\prime}(G)))=\widetilde{O}(n/\sqrt{r})$
time.

Now, for each piece $P\in\mathcal{R}$, consider a graph $P^{\prime}$ obtained
from $P$ by adding the super-source $s$ with edges of weight $nC$ to all $v\in
V(P)\setminus\partial{P}$, and with edges of weight
$\delta_{\mathrm{DDG}^{\prime}(G)}(s,v)$ to all $v\in\partial{P}$. Let us
extend the feasible price function $p_{P}$ of $P$ to a feasible price function
of $P^{\prime}$ similarly as we did for $q$. Using $p_{P}$, using standard
Dijkstra‘s algorithm, we compute single-source distances
$\delta_{P^{\prime}}(s,v)$ to all $v\in V(P)$ and set
$p(v)=-\delta_{P^{\prime}}(s,v)$. This takes $O(|P|\log{|P|})$ time. Through
all pieces, we spend $O(n\log{n})$ time on this.

To prove the above algorithm computing a feasible price function $p$ of
$G^{\prime}$ correct, it is enough to argue that for a piece
$P\in\mathcal{R}$, we have $\delta_{P^{\prime}}(s,v)=\delta_{G^{\prime}}(s,v)$
for all $v\in V(P)$. It is clear that
$\delta_{P^{\prime}}(s,v)\geq\delta_{G^{\prime}}(s,v)$ since $P^{\prime}$ is a
subgraph of $G^{\prime}$ with some edges shortcutting paths in $G^{\prime}$
added. To prove $\delta_{P^{\prime}}(s,v)\leq\delta_{G^{\prime}}(s,v)$,
consider a shortest path $R=s\to v$ in $G^{\prime}$. If $R$ contains no
vertices of $\partial{P}$, then we have $R\subseteq P^{\prime}$ so the
inequality holds. Otherwise, let $z$ be the last vertex of $\partial{P}$
appearing on $R$. Let us write $R=R_{1}R_{2}$, where $R_{1}=s\to z$ and
$R_{2}=z\to v$. Note that we have $R_{2}\subseteq P^{\prime}$ so it is enough
to argue that $\delta_{P^{\prime}}(s,z)$ is no more than the length of
$R_{1}$. If the first edge of $R_{1}$ is $sb$, where
$b\in\partial{\mathcal{R}}$, then
$\delta_{\mathrm{DDG}^{\prime}(G)}(s,z)\leq\delta_{\mathrm{DDG}^{\prime}(G)}(b,z)=\delta_{G^{\prime}}(b,z)=\ell(R_{1})$.
But there is an edge $sz$ of weight $\delta_{\mathrm{DDG}^{\prime}(G)}(s,z)$
in $P^{\prime}$ which proves that $\delta_{P^{\prime}}(s,z)\leq\ell(R_{1})$.
So suppose the first edge of $R_{1}$ is $sy$, where
$y\notin\partial{\mathcal{R}}$. But then $\ell(R_{1})=nC+\delta_{G}(y,z)\geq
nC-(n-1)C=C>0$. However, we have
$\delta_{P^{\prime}}(s,z)\leq\delta_{\mathrm{DDG}^{\prime}(G)}(s,z)\leq 0$
since there is a direct $0$-weight edge $sz$ in $\mathrm{DDG}^{\prime}(H)$. So
$\delta_{P^{\prime}}(s,z)\leq\ell(R_{1})$ in this case as well. ∎

Let us analyze the running time $T(n)$ of the given algorithm for our choice
of $r=n^{8/9}$. We have

$T(n)=O(n\log{n})+\widetilde{O}(n^{5/6}\log{C})+\sum_{P\in\mathcal{R}}T(|P|).$
(3)

We now proceed with a formal proof of the bound $T(n)=O(n\log{(nC)})$. Let
$z\geq 1$ be a constant simultaneously larger than that hidden in the
$O(n\log{n})$ term in (3), the one in the $O(r)$ piece size bound, the one in
the $O(n/r)$ bound on $|\mathcal{R}|$, and the one in the $O(\sqrt{r})$ bound
on $|\partial{P}|$.

Note that $\mathcal{R}$ has at least $n/(2zr)$ pieces of size at least
$r/(2z)$, as otherwise the total number of vertices in pieces would be less
then $(n/(2zr))\cdot zr+(zn/r)\cdot(r/2z)=n$, a contradiction.

We now prove that $T(n)\leq cn\log{(nC)}-dn^{0.9}\log{C}$ for some constants
$c\geq 2$, $d>0$ by induction on $n$. Let $n_{0}$ be a constant such that for
all $n\geq n_{0}$ we have (1) $16z^{2}<n^{0.01}$, (2)
$z^{2}(n/\sqrt{r})(\log{n}+1)=z^{2}n^{5/9}(\log{n}+1)\leq n^{0.9}$, (3) the
term $\widetilde{O}(n^{5/6}\log{C})$ is no more than $n^{0.9}\log{C}$ in the
right-hand side of (3). Then for any $P\in\mathcal{R}$ we also have $|P|\leq
zr\leq zn^{8/9}\leq n^{8/9+0.01}\leq n^{0.9}$.

Suppose first that $n>n_{0}$ and the bound holds for all $n^{\prime}<n$. Then
we have:

$\displaystyle T(n)$ $\displaystyle\leq
O(n\log{n})+\widetilde{O}(n^{5/6}\log{C})+\sum_{P\in\mathcal{R}}\left(c\cdot|P|(\log{|P|}+\log{C})-d\cdot|P|^{0.9}\log{C}\right)$
$\displaystyle\leq
zn\log{n}+n^{0.9}\log{C}+\sum_{P\in\mathcal{R}}c\cdot|P|\left(\log
n^{9/10}+\log{C}\right)-d\cdot\frac{n}{2zr}\left(\frac{r}{2z}\right)^{0.9}\log{C}$
$\displaystyle\leq
zn\log{n}+n^{0.9}\log{C}+c\left(\frac{9}{10}\log{n}+\log{C}\right)\cdot\sum_{P\in\mathcal{R}}|P|-\frac{d}{4z^{2}}\frac{n}{r^{0.1}}\log{C}$
$\displaystyle\leq
zn\log{n}+n^{0.9}\log{C}+c\left(\frac{9}{10}\log{n}+\log{C}\right)\cdot\left(n+z^{2}n/\sqrt{r}\right)-\frac{d}{4z^{2}}\frac{n}{r^{0.1}}\log{C}$
$\displaystyle\leq\left(z+\frac{9}{10}c\right)n\log{n}+cn\log{C}+n^{0.9}\log{C}+c\left(\frac{9}{10}\log{n}+\log{C}\right)\cdot\frac{z^{2}n}{\sqrt{r}}-\frac{d}{4z^{2}}\cdot
n^{0.91}\log{C}$
$\displaystyle\leq\left(z+\frac{9}{10}c\right)n\log{n}+cn\log{C}+\left(c+1-\frac{d}{4z^{2}}n^{0.01}\right)n^{0.9}\log{C}.$

To finish the proof we first set the constant $c=\Omega(n_{0})$ so that
$z+\frac{9}{10}c\leq c$, and $cn/2$ is for $n\leq n_{0}$ at least as large as
the $O(n^{2})$ bound on the running time of Bellman-Ford algorithm. We would
also like to have $(c+1-\frac{d}{4z^{2}}n^{0.01})\leq-d$, which would imply
the desired bound $cn\log{(nC)}-dn^{0.9}\log{C}$ for $n>n_{0}$. For that to
hold, it is enough to put $d=\frac{c+1}{(n_{0}^{0.01}/4z^{2})-1}$. This way,
by $n_{0}^{0.01}/4z^{2}\geq 4$, we also have $d\leq\frac{c+1}{3}\leq c/2$. We
can use this to prove the base of the induction. Indeed, we have
$cn\log{(nC)}-dn^{0.9}\log{C}\geq(c-d)n\log{C}\geq cn/2$, which, by the
definition of $c$, is enough to cover the cost of running Bellman-Ford for
$n\leq n_{0}$. We have thus proved the following.

See 1.6

##  6 Max $s,t$-flow oracles for planar digraphs

###  6.1 Reduction to a parametric negative cycle detection problem

We now refer to a well-known reduction of the decision variant of the max
$s,t$-flow problem on a planar digraph to the negative cycle detection
problem. In the recent literature [Eri10, Nus14], this reduction is generally
attributed to an unpublished manuscript by Venkatesan (see also [JV83]).

Let us denote by $u(e)\geq 0$ the capacity of an edge $e$. Let us assume that
each edge $e\in G$ has also its reverse $e^{\mathrm{R}}$ in $G$, with the same
embedding as $e$, of capacity $u(e^{\mathrm{R}})=0$. This does not change the
amounts of flow that can be sent between the vertices but enables the
correspondence between cuts and dual cycles, and also guarantees that each
connected subgraph of $G$ (and also the dual graph) is strongly connected. For
a subset $F\subseteq E$, let $u(F)=\sum_{e\in F}u(e).$

Let $\lambda\geq 0$. Let us embed some $s\to t$ path $Q_{s,t}$ in $G$ – this
path can be chosen in an arbitrary way, for example it can be embedded
’’almost parallel‘‘ to some of the existing $s\to t$ paths $P$ in $G$. The
’’capacity‘‘ of each edge of $Q_{s,t}$ is set to $-\lambda$, whereas its
reverse capacity is set to $\lambda$. The path $Q_{s,t}$ can be likewise
embedded _on_ $P$ in $G$ without introducing new edges or faces – it is enough
to increase the capacity of each edge $e\in P$ by $-\lambda$, and the capacity
of $e^{\mathrm{R}}$ by $\lambda$.

Let $G_{\lambda}$ be the graph obtained this way, i.e., we have some $s\to t$
path $Q_{s,t}\subseteq G$ fixed, and $G_{\lambda}$ differs from $G$ only by
edge weights on the path $Q_{s,t}$ and its reverse.

See 4.4 Whereas in the primal graph edges have capacities (as typical for max-
flow problems), in the dual graph, we call them weights (as typical in the
negative cycle detection problem).

The intuition behind Lemma 4.4 is as follows (see e.g., [Eri10] for a formal
proof). By the max-flow-min-cut theorem, there exists a flow of value
$\lambda$ in $G$ iff the minimum $s,t$-cut in $G$ has capacity $\lambda$ or
more. It is well known that simple undirected $s,t$-cuts in $G$ correspond to
simple cycles in the dual $G^{*}$ that contain one of the faces $s^{*},t^{*}$
inside and the other outside. However, not all directed cycles in $G^{*}$ with
this property correspond to simple directed $s,t$-cuts in $G$. Directed cycles
in the dual have the ’’left‘‘ and the ’’right‘‘ side (defined naturally once
we fix what is the left side of a directed edge in $G^{*}$). Only simple
cycles with $s^{*}$ on the left and $t^{*}$ on the right correspond to simple
directed $s,t$-cuts in $G$. For any directed _simple_ cycle $C^{*}$ in the
dual, consider counting how many times $Q_{s,t}$ crosses it in the following
way: if $Q_{s,t}$ crosses $C^{*}$ left to right (i.e., an edge $e\in Q_{s,t}$
satisfies $e^{*}\in E(C^{*})$), increment the counter by $1$, and if $Q_{s,t}$
crosses $C^{*}$ right to left (i.e., an edge $e\in Q_{s,t}$ satisfies
$(e^{\mathrm{R}})^{*}\in E(C^{*})$) decrement the counter by $1$. One can
prove (see [Eri10]):

######  Fact 6.1.

The final value of the counter, called the _crossing number_ of $C^{*}$ wrt
$Q_{s,t}$, is in the set $\\{-1,0,1\\}$.

The above actually holds for any Jordan curve $C^{*}$, not only simple cycles
in the dual. Formally, for any subsets $A\subseteq E(G)$, $B\subseteq
E(G^{*})$, we will use:

$\displaystyle\pi_{B}(A)$ $\displaystyle=|\\{e\in A:e^{*}\in B\\}|-|\\{e\in
A:(e^{R})^{*}\in B\\}|,$ $\displaystyle\pi_{A}(B)$ $\displaystyle=|\\{e^{*}\in
B:e\in A\\}|-|\\{e^{*}\in B:e^{R}\in A\\}|.$

With this definition, a directed dual $C^{*}$ corresponds to a simple directed
$s,t$-cut if and only if $\pi_{Q_{s,t}}(C^{*})=\pi_{C^{*}}(Q_{s,t})=1$. Note
that for any cycle $C^{*}$ in $G^{*}_{\lambda}$, its weight
$w_{G^{*}_{\lambda}}(C^{*})$ equals $u(C)-\lambda\cdot\pi_{Q_{s,t}}(C^{*})$
(where $C=\\{e\in E(G):e^{*}\in C^{*}\\}$). Thus, we have
$w_{G^{*}_{\lambda}}(C^{*})\geq u(C)\geq 0$ if $\pi_{Q_{s,t}}(C^{*})\leq 0$
and $w_{G^{*}_{\lambda}}(C^{*})=u(C)-\lambda$ if $\pi_{Q_{s,t}}(C^{*})=1$.
Since simple $s,t$-cuts in $G_{\lambda}$ correspond precisely to simple cycles
$C^{*}$ with $\pi_{Q_{s,t}}(C^{*})=1$ in $G^{*}_{\lambda}$, one can prove that
there exists a negative cycle in $G^{*}_{\lambda}$ if and only if there is an
$s,t$-cut with capacity less than $\lambda$ in $G$.

Note that the reduction allows binary searching for the maximum $s,t$-flow via
using negative cycle detection-based tests. For example, using Theorem 1.6,
for integral capacities in $[0,C]$ one can compute a maximum $s,t$-flow value
in $O(n\log^{2}(nC))$ time. However, this bound is worse and less general than
the best known strongly polynomial $O(n\log{n})$ bound [BK09, Eri10].

###  6.2 Combining the reduction with a decomposition

Even though the reduction from Section 6.1 is not the most efficient method to
compute max $s,t$-flow in a planar graph, it turns out to be robust enough to
allow combining it with a recursive decomposition to answer queries about max
$s,t$-flow between arbitrary $(s,t)$ pairs. For any $(s,t)$ pair, we will be
able to reduce the problem to $O(\log{n})$ negative cycle detection instances
on graphs with $\widetilde{O}(\sqrt{n})$ vertices. In each of these graphs, we
will search for a negative cycle in sublinear time (in the number of edges)
even though the graph will have $\Theta(n)$ edges defined.

We will use the following recursive decomposition of a simple plane graph.
Miller [Mil84] showed how to compute, in a triangulated plane graph with $n$
vertices, a simple cycle of size $2\sqrt{2}\sqrt{n}$ that separates the graph
into two subgraphs, each with at most $2n/3$ vertices. Simple cycle separators
can be used to recursively separate a planar graph until pieces have constant
size. [KMS13] show how to obtain a complete recursive decomposition tree
$\mathcal{T}(G)$ of a triangulated graph $G$ using cycle separators in $O(n)$
time. $\mathcal{T}(G)$ is a binary tree whose nodes correspond to subgraphs of
$G$ (pieces), with the root being all of $G$ and the leaves being pieces of
constant size. We identify each piece $P$ with the node representing it in
$\mathcal{T}(G)$. We can thus abuse notation and write $P\in\mathcal{T}(G)$.
The _boundary vertices_ $\partial{P}$ of a _non-leaf piece_ $P$ are vertices
that $P$ shares with some other piece $Q\in\mathcal{T}(G)$ that is neither
$P$‘s ancestor nor its descendant. We assume $P$ to inherit the embedding from
$G$. The faces of $P$ that are faces of $G$ are called _natural_ , whereas the
faces of $P$ that are not natural are the _holes_ of $P$. The construction of
[KMS13] additionally guarantees that for each piece $H\in\mathcal{T}(G)$:

  1. (a)

$H$ is connected and contains at least one natural face,

  2. (b)

if $H$ is a non-leaf piece, then each natural face $f$ of $H$ is a face of
precisely one child of $H$,

  3. (c)

$H$ has $O(1)$ holes containing precisely the vertices $\partial{H}$.

Note that since the natural faces of a piece are partitioned among its
children, and there are $O(1)$ holes per piece, the subtree of
$\mathcal{T}(G)$ rooted at $H$ has $O(|V(H)|)$ nodes. Throughout, to avoid
confusion, we use _nodes_ when referring to $\mathcal{T}(G)$ and _vertices_
when referring to $G$ or its subgraphs. It is well-known [BSW15, GMWW18,
KMS13] that by suitably choosing cycle separators that alternate between
balancing vertices, boundary vertices, and holes, one can also guarantee that
(1) $\sum_{H\in\mathcal{T}(G)}|H|=O(n\log{n})$, (2)
$\sum_{H\in\mathcal{T}(G)}|\partial{H}|^{2}=O(n\log{n})$, and (3)
$|\partial{H}|=O(\sqrt{n})$.

To proceed, we first need to guarantee that $G$ has degree $3$. This is easily
achieved by standard embedding-respecting transformations. First, we
repeatedly introduce parallel $0$-capacity edges incident to vertices of
degree less than $3$, until there are none. Afterwards, we replace each vertex
by a cycle of sufficiently large-capacity edges. The graph $G$ grows by a
constant factor only, and clearly for any pair of vertices, the max $s,t$-flow
value in $G$ before the transformation equals the max
$s^{\prime},t^{\prime}$-flow values between some copies $s^{\prime}$ of $s$
and $t^{\prime}$ of $t$ after the transformation. Therefore, in the following
we assume that each vertex in $G$ has degree $3$.

Observe that by the degree-$3$ assumption, the dual graph $G^{*}$ is
triangulated. We can thus build a recursive decomposition $\mathcal{T}(G^{*})$
of $G^{*}$ as described above.

For simplicity, let also additionally assume that the obtained decomposition
satisfies the following: for each node $H\in\mathcal{T}(G^{*})$ the holes of
$H$ are _simple and pairwise vertex-disjoint_. We discuss how to drop this
assumption in Section 10.

Recall that the faces of $G^{*}$ correspond to the vertices of $G$. As a
result, for a node $H\in\mathcal{T}(G^{*})$, every natural face of $H$
corresponds to some vertex of $G$. Let us denote by $W(H)$ the vertices of $G$
whose duals in $G^{*}$ are natural faces of $H$. We use $W^{*}(H)$ when
referring to natural faces of $H$.

Since a piece $H\in\mathcal{T}(G^{*})$ has simple and vertex-disjoint holes,
for any of $H$‘s two natural faces $f=u^{*},g=v^{*}$, corresponding to
vertices $u,v\in V$ respectively, there is a chain of distinct natural faces
$f=f_{1},\ldots,f_{k+1}=g$ in $H$ such that $f_{i}$ and $f_{i+1}$ share an
edge $e_{i}^{*}$ in $H$. To see this, note that for each hole $h$, any two of
its neighboring (natural) faces can be connected with a face chain consisting
of the neihboring (natural) faces of $h$ only. Therefore, any path between two
natural faces of $H$ can be transformed to avoid the holes. A chain
$f_{1},\ldots,f_{k+1}$ in question corresponds to a _simple_ path between
$u\to v$ in $G$. If $H$ is a _leaf piece_ , let us fix an arbitrary one such
chain and denote by $Y_{H}[f,g]$ the corresponding $u\to v$ path $e_{1}\ldots
e_{k}$ (where $e_{i}^{*}$ is the dual of $e_{i}$) in $G$.

##### Split faces and edges.

For each non-leaf node $H\in\mathcal{T}(G^{*})$, let us arbitrarily pick two
natural _split faces_ $f_{H,1},f_{H,2}$ of the children nodes $H_{1},H_{2}$ of
$H$ satisfying the following: $f_{H,i}$ is a face of $H_{i}$ but not of
$f_{H,{3-i}}$ and $f_{H,1},f_{H,2}$ are adjacent faces of $H$. To see that
such a pair exists, recall that both $H_{1}$ and $H_{2}$ contain at least one
natural face and the natural faces of $H$ are partitioned among $H_{1}$ and
$H_{2}$. Consider a simple chain of faces of $H$ connecting a natural face of
$H_{1}$ to a natural face of $H_{2}$ (that we have already argued to exist).
Such a chain has to contain a natural face of $H_{1}$ followed by a natural
face of $H_{2}$. We also say that $f_{H,i}$ is a _sibling split face_ of
$f_{H,3-i}$.

Denote by $e_{H}^{*}$ the common edge of $f_{H,1}$ and $f_{H,2}$, called a
_dual split edge_. The _primal split edge_ $e_{H}$ is such that $e_{H}^{*}$ is
the dual of $e_{H}$.

##### Choosing and decomposing the primal $s,t$-path.

Having defined split faces, we will now fix, for any pair $(s,t)\in V\times
V$, a particularly convenient simple $s\to t$ path $Q_{s,t}\subseteq G$ which
is required by the reduction of Section 6.1.

We will set $Q_{s,t}$ to be the path $\Phi(G^{*},s^{*},t^{*})$ constructed
using a recursive function $\Phi(H,x^{*},y^{*})$ that, given a piece
$H\in\mathcal{T}(G^{*})$ and its two natural faces $x^{*},y^{*}\in W^{*}(H)$,
produces a simple path $x\to y$ in $G$ whose edges‘ duals come from $E(H)$.
Let $H_{1},H_{2}$ denote the children of $H$, if $H$ is non-leaf. We set:

$\Phi(H,x^{*},y^{*})=\begin{cases}Y_{H}[x^{*},y^{*}]&\text{ if }H\text{ is a
leaf piece of }\mathcal{T}(G^{*}),\\\ \Phi(H_{i},x^{*},y^{*})&\text{ if
$x,y\in W(H_{i})$},\\\ \Phi(H_{i},x^{*},f_{H,i})\cdot
e_{H}\cdot\Phi(H_{3-i},f_{H,{3-i}},y^{*})&\text{ $x\in W(H_{i})$ and $y\in
W(H_{3-i})$}.\end{cases}$ (4)

Since the sets $W(H_{1}),W(H_{2})$ are disjoint if $H_{1},H_{2}$ are children
of the same parent, we have:

######  Fact 6.2.

For any $H\in\mathcal{T}(G^{*})$, and $x,y\in W(H)$, $\Phi(H,x^{*},y^{*})$ is
a simple $x\to y$ path in $G$.

Recall that for the purpose of using the reduction of Section 6.1, ideally, we
would like to be able to increase the capacities of the edges on $Q_{s,t}$ by
$-\lambda$, and of the reverse edges on $Q_{s,t}$ by $\lambda$. Unfortunately,
the path $Q_{s,t}$ can be in general of length $\Theta(n)$ which seems
prohibitive if we want to explicitly adjust the weights upon source/sink
query.

We will now prove that the possible paths $Q_{s,t}$ constructed via
$\Phi(G^{*},s^{*},t^{*})$ have many subpaths in common. For any
$H\in\mathcal{T}(G^{*})$, define the _split set_ $Z(H)$ to contain all the
natural faces $f$ of $H$ such that $f$ is a split face of one of $H$‘s
ancestors in $\mathcal{T}(G^{*})$. We would like each element of $Z(H)$ to
also record the ancestor $A$ where the split face originates from, so
technically $Z(H)$ might be a multiset. Additionally, it will be convenient to
assume that the faces of $Z(H)$ are not considered ordinary natural faces of
$H$ since they carry more information (about the ancestor). As a result, we
will assume that $W^{*}(H)\cap Z(H)=\emptyset$. However, if $x^{*}\in
W^{*}(H)$, we might still say that $x^{*}$ is an _ancestor split face_ if
$Z(H)$ contains at least one element based on the face $x^{*}$. Similarly, for
$z^{*}\in Z(H)$, $z^{*}$ can be projected on $W^{*}(H)$ (converted to an
element of $W^{*}(H)$) by dropping the ancestor information in a trivial way.

Observe that for any $H$ we have $|Z(H)|=O(\log{n})$ since $H$ has
$O(\log{n})$ ancestors and each of them contributes at most a single split
face. As a result, $W^{*}(H)$ contains $O(\log{n})$ ancestor split faces.
Moreover, note that for any $f_{A,i}\in Z(H)$, where $A$ is some ancestor of
$H$, $f_{A,3-i}$ is not a natural face of $H$ and the dual split edge
$e_{A}^{*}$ lies on the boundary of some hole of $H$. As a result, the primal
split edge $e_{A}$ crosses the boundary of that hole of $H$.

The following lemma gives a decomposition of any of $\Omega(n^{2})$ possible
$Q_{s,t}$ paths into a small number of subpaths coming from a set of only
$\widetilde{O}(n)$ distinct paths in $G$.

######  Lemma 6.3.

Any path $\Phi(G^{*},s^{*},t^{*})$ can be expressed as a concatenation of
$O(\log{n})$ paths, each of which is either

  1. 1.

a split edge,

  2. 2.

or is of the form $\Phi(H,x^{*},y^{*})$, where $x^{*},y^{*}\in W^{*}(H)$ are
ancestor split faces of $H$,

  3. 3.

or is of the form $\Phi(L,x^{*},y^{*})$, where $L$ is a leaf of
$\mathcal{T}(G^{*})$.

Such a decomposition can be computed in $O(\log{n})$ time.

###### Proof.

We prove that a desired decomposition exists for all paths
$\Phi(H,x^{*},y^{*})$, where $H\in\mathcal{T}(G^{*})$ and $x^{*},y^{*}\in
W^{*}(H)$, by induction on the height $d$ of the subtree of
$\mathcal{T}(G^{*})$ rooted at $H$. The sought decomposition will have at most
$4d+1$ elements if none of $x^{*},y^{*}$ are ancestor split faces of $H$, at
most $2d+1$ elements if at least one of $x^{*},y^{*}$ is an ancestor split
face of $H$, and precisely $1$ element if both $x^{*},y^{*}$ are ancestor
split faces of $H$. The lemma will follow as the height of
$\mathcal{T}(G^{*})$ is $O(\log{n})$.

If $H$ has no children, i.e., $d=0$, then $H$ is a leaf and thus
$\Phi(H,x^{*},y^{*})$ is a valid decomposition of size $1$, so the desired
bound holds in all cases. So in the following assume $d\geq 1$.

If both $x^{*}$ and $y^{*}$ are ancestor split faces, we don‘t need to
decompose $\Phi(H,x^{*},y^{*})$, so a decomposition of size $1\leq 2d+1$
exists. Otherwise, we apply Equation (4) and recursively decompose the right-
hand side of (4).

If neither $x^{*}$ nor $y^{*}$ is an ancestor split face, then there is either
one recursive call of the same kind that yields a decomposition of size
$4(d-1)+1\leq 4d+1$, or two recursive calls with at least one ancestor split
face that, combined, yield a decomposition of size
$2\cdot(2(d-1)+1)+1=4d-1\leq 4d+1$.

Finally, let us assume that exactly one of $x^{*},y^{*}$ is an ancestor split
face. Suppose that $H$ has children $H_{1},H_{2}$. If both $x^{*},y^{*}\in
W^{*}(H_{i})$ for some $i$, then
$\Phi(H,x^{*},y^{*})=\Phi(H_{i},x^{*},y^{*})$. Moreover, if $x^{*}$ or $y^{*}$
is an ancestor split face of $H$, then it is an ancestor split face of $H_{i}$
as well. As a result, among $x^{*},y^{*}$ there is at least one ancestor split
face of $H_{i}$, so we can apply the inductive assumption and the
decomposition of $\Phi(H,x^{*},y^{*})$ has length at most $2d-1\leq 2d+1$.

Otherwise, $\Phi(H,x^{*},y^{*})=\Phi(H_{i},x^{*},f_{H,i})\cdot
e_{H}\cdot\Phi(H_{3-i},f_{H,{3-i}},y^{*})$. Suppose wlog. that $x^{*}$ is an
ancestor split face of $H$. Then, both $x^{*},f_{H,i}$ are ancestor split
faces of $H_{i}$, so the decomposition of $\Phi(H_{i},x^{*},f_{H,i})$ has size
$1$. By the fact that $f_{H,{3-i}}$ is an ancestor split face of $H_{3-i}$ and
the inductive assumption, the decomposition of
$\Phi(H_{3-i},f_{H,{3-i}},y^{*})$ has size at most $2d-1$. So indeed there
exists a decomposition of $\Phi(H,x^{*},y^{*})$ of size at most
$1+1+(2(d-1)+1)=2d+1$.

Clearly, the above inductive proof can be turned into an $O(\log{n})$ time
algorithm expressing $\Phi(G^{*},s^{*},t^{*})$ as desired. ∎

###  6.3 A feasible flow oracle

Let us first consider the problem of designing a data structure that supports
queries $(s,t)$ whether the max $s,t$-flow is at least $\lambda$, where
$\lambda$ is a fixed parameter given upon initialization.

####  6.3.1 Preprocessing

For each $H\in\mathcal{T}(G^{*})$, we will explicitly compute the
$O(|Z(H)|^{2})=\widetilde{O}(1)$ paths of the form $\Phi(H,x^{*},y^{*})$,
where $x^{*},y^{*}$ are ancestor split faces of $H$. Note that computing
$\Phi(H,x^{*},y^{*})$ from the definition takes $O(|V(H)|)$ time. As a result,
computing all these required paths explicitly takes
$\sum_{H\in\mathcal{T}(G)}|Z(H)|^{2}\cdot|H|=\widetilde{O}(1)\cdot\sum_{H\in\mathcal{T}(G)}|H|=\widetilde{O}(n)$
time.

To proceed, we first need to extend the definition of $\Phi(H,x^{*},y^{*})$
from $x^{*},y^{*}\in W^{*}(H)$ to all $x^{*},y^{*}\in W^{*}(H)\cup Z(H)$. If
$x^{*}\in Z(H)$ ($y^{*}\in Z(H)$), then let $(x^{\prime})^{*}$
($(y^{\prime})^{*}$, resp.) be the sibling split face of $x^{*}$ ($y^{*}$,
resp). We extend the definition naturally as follows:

$\Phi(H,x^{*},y^{*})=\begin{cases}x^{\prime}x\cdot\Phi(H,x^{*},y^{*})\cdot
yy^{\prime}&\text{ if $x^{*}\in Z(H)$, $y^{*}\in Z(H)$, }\\\
\Phi(H,x^{*},y^{*})\cdot yy^{\prime}&\text{ if $x^{*}\in W^{*}(H)$, $y^{*}\in
Z(H)$, }\\\ x^{\prime}x\cdot\Phi(H,x^{*},y^{*})&\text{ if $x^{*}\in Z(H)$,
$y^{*}\in W^{*}(H)$. }\end{cases}$

In the right-hand side above, where needed, the faces $x^{*},y^{*}$ are
projected naturally onto $W^{*}(H)$ as explained before.

For any $H\in\mathcal{T}(G^{*})$ and $x^{*},y^{*}\in Z(H)$, where $x^{*}\neq
y^{*}$, we apply the following additional preprocessing. Observe that
$\Phi(H,x^{*},y^{*})$ is a simple $x^{\prime}\to y^{\prime}$ path in $G$ whose
all vertices but its endpoints correspond to natural faces of $H$. Moreover,
the dual edges $(\Phi(H,x^{*},y^{*}))^{*}$ of $\Phi(H,x^{*},y^{*})$ satisfy
$(\Phi(H,x^{*},y^{*}))^{*}\subseteq E(H)$. From the point of view of $H$,
$\Phi(H,x^{*},y^{*})$ is a simple directed curve in the plane

  1. (i)

originating in a hole $h_{x}$ of $H$ that contains the primal vertex
$x^{\prime}$ (as embedded in $G$),

  2. (ii)

ending in the hole $h_{y}$ that contains the primal vertex $y^{\prime}$,

  3. (iii)

going only through natural faces of $H$ between leaving $h_{x}$ and entering
$h_{y}$.

Let $G^{*}_{\lambda}[H](x^{*},y^{*})$ denote the edge-induced subgraph
$G^{*}[H]$ such that the weight of edges $(\Phi(H,x^{*},y^{*}))^{*}$ have been
increased by $-\lambda$, and their reverse edges by $\lambda$.

First, we test whether $G^{*}_{\lambda}[H](x^{*},y^{*})$ contains a negative
cycle and potentially also compute a feasible price function $p$ of that
graph. For this, we can either use Theorem 3.6 or the strongly polynomial
algorithm of [MW10] run on that graph whose size is $O(|H|)$. Moreover, with
the help of the feasible price function $p$ and the MSSP data structure, we
compute the dense distance graph
$\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$ (with vertex set
$\partial{H}$, defined analogously as in Section 5) in
$\widetilde{O}(|H|+|\partial{H}|^{2})$ time. Since Lemma 5.1 only required the
boundary vertices to lie on $O(1)$ faces of the piece, using Lemma 5.1, we
preprocess the closest pair and near neighbor data structures for
$\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$ in
$\widetilde{O}(|H|+|\partial{H}|^{2})$ time and space.

Finally, for each piece $H\in\mathcal{T}(G^{*})$, we also precompute and store
the dense distance graph $\mathrm{DDG}(H)$ along with the closest pair and
near neighbor data structures using MSSP and Lemma 5.1. This requires
$\widetilde{O}(|H|+|\partial{H}|^{2})$ time and space as well.

######  Lemma 6.4.

Preprocessing takes $\widetilde{O}(n)$ time.

###### Proof.

The cost of preprocessing (through all pieces and pairs of split faces) can be
bounded by:

$\sum_{H\in\mathcal{T}(G)}\widetilde{O}\left(|Z(H)|^{2}\cdot\left(|H|+|\partial{H}|^{2}\right)\right)=\widetilde{O}(1)\cdot\sum_{H\in\mathcal{T}(G)}\left(|H|+|\partial{H}|^{2}\right)=\widetilde{O}(n).\qed$

####  6.3.2 Query procedure

We are now ready to give an algorithm detecting a negative cycle in
$G^{*}_{\lambda}$ given the source/sink pair $s,t$. By the reduction of
Section 6.1, this is equivalent to deciding whether the max $s,t$-flow in $G$
is less than $\lambda$. Recall that we have fixed the path $Q_{s,t}$ in $G$
(as required by the reduction) to be specifically the path
$\Phi(G^{*},s^{*},t^{*})$.

Similarly as before, for $H\in\mathcal{T}(G)$, $x^{*},y^{*}\in W^{*}(H)\cup
Z(H)$, let $G^{*}_{\lambda}[H](x^{*},y^{*})$ denote the edge-induced subgraph
$G^{*}[H]$ such that the weights of edges $(\Phi(H,x^{*},y^{*}))^{*}$ have
been increased by $-\lambda$, and the weights of their reverse edges by
$\lambda$.

We now define a recursive procedure $\mathtt{detect}(\lambda,H,x^{*},y^{*})$
that tests whether $G^{*}_{\lambda}[H](x^{*},y^{*})$ has a negative cycle.
Equipped with this procedure, by calling
$\mathtt{detect}(\lambda,G^{*},s^{*},t^{*})$, we will achieve our goal of
testing whether $G^{*}_{\lambda}$ contains a negative cycle.

The procedure $\mathtt{detect}(\lambda,H,x^{*},y^{*})$ will decompose the
problem in exactly the same way as definition (4) deconstructs the path
$\Phi(H,x^{*},y^{*})$ (with $x^{*},y^{*}$ projected to $W^{*}(H)$) and stop
recursing when we have $x^{*},y^{*}\in Z(H)$ or $H$ is a leaf. By Lemma 6.3,
the recursion tree will have $O(\log{n})$ leaves and $O(\log{n})$ depth, and
thus the number of recursive calls will be $O(\log{n})$.

If $\mathtt{detect}(\lambda,H,x^{*},y^{*})$ does not detect a negative cycle,
it produces (pointers to) preprocessed closest pair and near neighbor data
structures of a graph $D(H,x^{*},y^{*})$ with $\partial{H}\subseteq
V(D(H,x^{*},y^{*}))$ such that for any $u,v\in\partial{H}$ we have

$\delta_{D(H,x^{*},y^{*})}(u,v)=\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(u,v),$

and for all $u,v\in V(D(H,x^{*},y^{*}))$ we have

$\delta_{D(H,x^{*},y^{*})}(u,v)\geq\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(u,v).$

In other words, $D(H,x^{*},y^{*})$ preserves the boundary-to-boundary
distances of $G^{*}_{\lambda}[H](x^{*},y^{*})$, and does not underestimate any
other distances in $G^{*}_{\lambda}[H](x^{*},y^{*})$. The graphs
$D(H,x^{*},y^{*})$ are not constructed explicitly in principle; we define them
for the purpose of analysis and we operate on the associated data structures
on these graph instead.

We now proceed with describing how the procedure
$\mathtt{detect}(\lambda,H,x^{*},y^{*})$ works.

  1. 1.

If $H$ is a leaf, we run any negative cycle detection algorithm on
$G^{*}_{\lambda}[H](x^{*},y^{*})$. Since $H$ has $O(1)$ size, this takes
$O(1)$ time. If no negative cycle is found, we can
put${D(H,x^{*},y^{*}):=G^{*}_{\lambda}[H](x^{*},y^{*})}$ and preprocess the
required data structures for $D(H,x^{*},y^{*})$ in $O(1)$ time.

  2. 2.

If $x^{*},y^{*}\in Z(H)$, we simply look up the precomputed information
whether $G^{*}_{\lambda}[H](x^{*},y^{*})$ has a negative cycle. If so, we have
found a negative cycle in $G^{*}_{\lambda}$ and the procedure terminates
globally. Otherwise, we return the appropriate preprocessed data structures
for $D(H,x^{*},y^{*})$ set to $\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$.

  3. 3.

Otherwise, if $x^{*},y^{*}\in W^{*}(H_{i})\cup Z(H_{i})$ for some $i$, we
recurse using $\mathtt{detect}(\lambda,H_{i},x^{*},y^{*})$. Note that in this
case we have

$G^{*}_{\lambda}[H](x^{*},y^{*})=G^{*}_{\lambda}[H_{i}](x^{*},y^{*})\cup
H_{3-i}.$ (5)

If the recursive call does not find a negative cycle, let us set $D_{i}$ to be
the graph $D(H_{i},x^{*},y^{*})$ associated with the returned data structures.
Moreover, let us set $D_{3-i}:=\mathrm{DDG}(H_{3-i})$.

  4. 4.

Finally, if $x^{*}\in W^{*}(H_{i})\cup Z(H)$ and $y^{*}\in W^{*}(H_{3-i})\cup
Z(H_{3-i})$, then we perform recursive calls
$\mathtt{detect}(H_{i},\lambda,x^{*},f_{H,i})$ and
$\mathtt{detect}(H_{3-i},\lambda,f_{H,3-i},y^{*})$, where $f_{H,i}\in
Z(H_{i})$ and $f_{H,3-i}\in Z(H_{3-i})$. Note that in this case we have

$G^{*}_{\lambda}[H](x^{*},y^{*})=G^{*}_{\lambda}[H_{i}](x^{*},f_{H,i})\cup
G^{*}_{\lambda}[H_{3-i}](f_{H,3-i},y^{*}).$ (6)

If none of the recursive calls detects a negative cycle, let us set
$D_{i}:=D(H_{i},x^{*},f_{H,i})$ and $D_{3-i}:=D(H_{3-i},f_{H,3-i},y^{*})$.

In cases $3$ and $4$, we proceed with additional computation: even though the
negative cycle does not exist in the parts of
$G^{*}_{\lambda}[H](x^{*},y^{*})$ processed in the recursive calls, it might
still exist in $G^{*}_{\lambda}[H](x^{*},y^{*})$. But then, observe that such
a cycle $C$ has to have parts in both graphs on the respective right-hand
sides of (5) (in case 3) and (6) (in case 4). Since both graphs intersect only
in the vertices of $\partial{H_{1}}\cup\partial{H_{2}}$, it is enough to
search for such a negative cycle in $G^{*}_{\lambda}[H](x^{*},y^{*})$ that
goes through at least one vertices of $\partial{H_{1}}\cup\partial{H_{2}}$.
Since the graphs $D_{1},D_{2}$ preserve distances between $\partial{H_{1}}$
and $\partial{H_{2}}$, resp., in these graphs, similarly as in Section 5, we
can look for a negative cycle in $D(H,x^{*},y^{*}):=D_{1}\cup D_{2}$ instead.
Note that $D(H,x^{*},y^{*})$ defined this way meets the requirement that it
preserves distances between
$\partial{H}\subseteq\partial{H_{1}}\cup\partial{H_{2}}$ in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ and does not underestimate other distances
$G^{*}_{\lambda}[H](x^{*},y^{*})$. The correctness of this approach follows.

Recall that from the recursive calls we get the closest pair and near neighbor
data structures for $D_{1},D_{2}$, so the respective data structures for
$D(H,x^{*},y^{*})$ can be obtained using Lemmas 3.5 and 3.2. Let us put
$D^{*}:=D(H,x^{*},y^{*})$. We then have:

$\displaystyle T_{\mathrm{cp}}(D^{*})$
$\displaystyle=T_{\mathrm{cp}}(D_{1})+T_{\mathrm{cp}}(D_{2})+\widetilde{O}\left(|\partial{H_{1}}|+|\partial{H_{2}}|\right),$
$\displaystyle T_{\mathrm{nn}}(D^{*})$
$\displaystyle=T_{\mathrm{nn}}(D_{1})+T_{\mathrm{nn}}(D_{2})+Q_{\mathrm{nn}}(D_{1})\cdot|\partial{H_{1}}|+Q_{\mathrm{nn}}(D_{2})\cdot|\partial{H_{2}}|+\widetilde{O}\left(|\partial{H_{1}}|+|\partial{H_{2}}|\right),$
$\displaystyle Q_{\mathrm{nn}}(D^{*})$
$\displaystyle=\max(Q_{\mathrm{nn}}(D_{1}),Q_{\mathrm{nn}}(D_{2}))+O(1).$

Consequently, running the algorithm of Theorem 3.6 on the graph
$D(H,x^{*},y^{*})$ takes

$\widetilde{O}\left(\sqrt{|V(D^{*})|}\cdot(T_{\mathrm{cp}}(D^{*})+T_{\mathrm{nn}}(D^{*})+|V(D^{*})|\cdot
Q_{\mathrm{nn}}(D^{*}))\log{C}\right)$ (7)

time. The following lemma analyzes the running time of the call
$\mathtt{detect}(G^{*},s^{*},t^{*})$.

######  Lemma 6.5.

$\mathtt{detect}(\lambda,G^{*},s^{*},t^{*})$ runs in
$\widetilde{O}(n^{3/4}\log{C})$ time.

###### Proof.

Consider the leaves of the recursion tree. Each leaf corresponds precisely to
a single element $\Phi(H,x^{*},y^{*})$ of the decomposition of
$\Phi(G^{*},s^{*},t^{*})$ produced by Lemma 6.3 that is not a split edge.
Consequently, there are $O(\log{n})$ leaves in the recursion tree. As the
height of $\mathcal{T}(G)$ is $O(\log{n})$, there are $\widetilde{O}(1)$
recursive calls in total.

The leaf calls (i.e., cases 1 and 2 of $\mathtt{detect}$) are processed in
$O(1)$ time since we have the necessary information precomputed. Note that the
associated precomputed graph $D(H,x^{*},y^{*}$) (equal to either
$\mathrm{DDG}(H,x^{*},y^{*})$ or $G^{*}_{\lambda}[H](x^{*},y^{*})$) has
$O(|\partial{H}|)$ vertices.

Each leaf call can be seen to contribute the graph $D(H,x^{*},y^{*})$ to the
graph $D^{*}$ of each of its $O(\log{n})$ ancestor calls. Each non-leaf call
with a single child call (case 3), in turn, additionally contributes a single
dense distance graph $\mathrm{DDG}(H_{3-i})$ to the graph $D^{*}$ of each of
its $O(\log{n})$ ancestor calls. In other words, the graph $D(H,x^{*},y^{*})$
can be seen to be the union of the respective graphs
$D^{*}_{L}=D(L,\cdot,\cdot)$ from $O(\log{n})$ descendant leaf calls $L$, and
dense distance graphs from $\widetilde{O}(1)$ non-leaf descendant calls. By
the properties of $\mathcal{T}(G^{*})$, each of these precomputed graphs $X$
whose union forms $D(H,x^{*},y^{*})$ satisfies
$T_{\mathrm{cp}}(X)=\widetilde{O}(\sqrt{n})$,
$T_{\mathrm{nn}}(X)=\widetilde{O}(\sqrt{n})$ and
$Q_{\mathrm{nn}}(X)=\widetilde{O}(1)$. Therefore, we conclude that
$D(H,x^{*},y^{*})$ has $\widetilde{O}(\sqrt{n})$ vertices.

Let us now analyze the performance of closest pair and near neighbor data
structures on the used graphs $D(H,x^{*},y^{*})$. By Lemma 3.2, the quantity
$Q_{\mathrm{nn}}(D(H,x^{*},y^{*}))$ can be seen to be the maximum of
$Q_{\mathrm{nn}}(X)$ over all precomputed graphs $X$ contributing to
$D(H,x^{*},y^{*})$, plus $\widetilde{O}(1)$. As a result, we have
$Q_{\mathrm{nn}}(D(H,x^{*},y^{*}))=\widetilde{O}(1)$.
$T_{\mathrm{cp}}(D(H,x^{*},y^{*}))$ can be bounded by the sum of
$T_{\mathrm{cp}}(X)$ over such graphs $X$ plus a term near-linear in the total
size of boundaries of all graphs in the $\widetilde{O}(1)$ descendant calls of
$\mathtt{detect}(\lambda,H,x^{*},y^{*})$. As a result, we also have
$T_{\mathrm{cp}}(D(H,x^{*},y^{*}))=\widetilde{O}(\sqrt{n})$. By
$Q_{\mathrm{nn}}(D(H,x^{*},y^{*}))=\widetilde{O}(1)$ and a similar argument,
we obtain $T_{{\mathrm{nn}}}(D(H,x^{*},y^{*}))=\widetilde{O}(\sqrt{n})$ as
well. Consequently, by plugging in these bounds into (7), detecting a negative
cycle in $D(H^{*},x^{*},y^{*})$ takes $\widetilde{O}(n^{3/4}\log{C})$ time.
Since the total number of recursive calls is $\widetilde{O}(1)$, the lemma
follows. ∎

By combining Lemmas 6.4 and 6.5, we obtain the following.

See 1.3

######  Remark 6.6.

The data structure of Theorem 1.3 can be also extended to report an $s,t$-cut-
set $F$ of capacity less than $\lambda$ in
$\widetilde{O}(|F|)=\widetilde{O}(\lambda)$ additional time, if such a cut-set
exists.

###### Proof sketch.

If the algorithm of Theorem 3.6 used inside
$\mathtt{detect}(\lambda,H,x^{*},y^{*})$ detects a negative cycle in
$D(H,x^{*},y^{*})$, it can also report one such cycle $C$ in
$\widetilde{O}(n^{3/4}\log{C})$ time. Recall that $D(H,x^{*},y^{*})$ is a
union of dense distance graphs, so each edge of $C$ corresponds to some path
between boundary vertices of a graph (say $G^{*}_{\lambda}[H](x^{*},y^{*})$ or
$H_{3-i}$) from which the respective dense distance graphs is derived from.
Since a DDG is constructed using MSSP, we can reuse MSSP to expand each edge
$e\in C$ into an actual path $P\subseteq G^{*}$. We can even extend the
dynamic tree used by MSSP (in a standard way, e.g., by enabling reporting a
maximum weight edge on a tree path) so that only the $p$ positive-weight edges
of $P$ are reported in $\widetilde{O}(p)$ time (recall that we added some
zero-capacity reverse edges to $G$ to make use of duality). This way, an $s,t$
cut-set $F\subseteq G$ of capacity less than $\lambda$ can be reported in
$\widetilde{O}(n^{3/4}\log{C}+|F|)$ time. Observe that since each edge in $F$
has capacity at least $1$, we have $|F|\leq\lambda$. ∎

###  6.4 An approximate max $s,t$-flow oracle

Let $\epsilon\in(0,1)$ be given. The feasible flow oracle from Theorem 1.3 can
be easily converted into a $(1-\epsilon)$-approximate max $s,t$-flow oracle
(or a $(1+\epsilon)$-approximate min $s,t$-cut oracle).

We simply set up feasible flow oracles for each of the values
$\lambda_{j}=\lceil(1+\epsilon)^{j}\rceil$, where
$j=0,\ldots,\log_{1+\epsilon}(nC)=O(\log{(nC)}/\epsilon)$. To find
$(1-\epsilon)$-approximate max $s,t$-flow value, we simply binary search for
(and return) the largest $\ell$ such that there exists an $s,t$-flow of value
$\lambda_{\ell}$ in $G$. To this end,
$O(\log(\log{(nC)}/\epsilon))=O(\log\log{(nC)}+\log{(1/\epsilon)})$ queries to
feasible flow oracles are enough. If the max $s,t$-flow value is
$\lambda^{*}$, then we have $\lambda^{*}<\lceil(1+\epsilon)^{\ell+1}\rceil$,
which implies

$\lambda^{*}\leq(1+\epsilon)^{\ell+1}\leq(1+\epsilon)\cdot\lceil(1+\epsilon)^{\ell}\rceil=(1+\epsilon)\cdot\lambda_{\ell}.$

So
$\lambda^{*}\geq\lambda_{\ell}\geq\frac{1}{1+\epsilon}\cdot\lambda^{*}\geq(1-\epsilon)\cdot\lambda^{*}$.

See 1.4

For approximating the min $s,t$-cut value, note that there exists an $s,t$-cut
set $F$ with capacity less than $\lambda_{\ell+1}$, i.e., at most
$\lceil(1+\epsilon)^{\ell+1}\rceil-1\leq\lfloor(1+\epsilon)^{\ell+1}\rfloor\leq(1+\epsilon)\cdot\lambda_{\ell}\leq(1+\epsilon)\cdot\lambda^{*}$.
By Remark 6.6, we can also find such $F$ in additional
$\widetilde{O}(n^{3/4}\log{C}+|F|)=\widetilde{O}(n^{3/4}\log{C}+\lambda^{*})$
time.

###  6.5 A dynamic feasible flow oracle

In this section we explain how to convert the static feasible flow oracle into
a dynamic one that supports edge capacity updates. For this, we use a standard
trick that have also been used to convert an $\widetilde{O}(\sqrt{n})$-query
time static exact distance oracle into an $\widetilde{O}(n^{2/3})$
update/query time dynamic distance oracle [FR06, Kle05].

Let $r$ be a parameter to be set later. As proved by [KMS13], the recursive
decomposition $\mathcal{T}(G^{*})$ _admits an $r$-division_. This means that
one can pick a subset $\mathcal{R}$ of pieces from $\mathcal{T}(G^{*})$, such
that (1) each face of $G^{*}$ is a natural face of precisely one piece
$H\in\mathcal{R}$, (2) $|\mathcal{R}|=O(n/r)$, (3) for every
$P\in\mathcal{T}(G)$, $|P|=O(r)$ and $|\partial{P}|=O(\sqrt{r})$. This can be
done in linear time [KMS13] during the preprocessing phase. Since the bounds
$|\partial{H}|=O(\sqrt{n})$ and
$\sum_{H\in\mathcal{T}(G^{*})}|H|+|\partial{H}|^{2}=\widetilde{O}(n)$ still
hold even if we start the decomposition process with $O(\sqrt{n})$ boundary
vertices $\partial{G^{*}}$ on $O(1)$ holes of $G^{*}$, and each
$P\in\mathcal{R}$ is decomposed using exactly the same procedure as $G^{*}$,
for descendants $B$ of $P$ we have $|\partial{B}|=O(\sqrt{r})$, and
$\sum_{P\supseteq
B\in\mathcal{T}(G^{*})}|B|+|\partial{B}|^{2}=\widetilde{O}(r)$.

Suppose the decomposition of $\Phi(G^{*},s^{*},t^{*})$ from Lemma 6.3 is not
allowed to have elements of the form $\Phi(H,x^{*},y^{*})$, where
$x^{*},y^{*}\in Z(H)$, unless $H$ is a descendant of some piece
$P\in\mathcal{R}$. If $H$ is not a descendant of some piece in $\mathcal{R}$,
by further decomposing $\Phi(H,x^{*},y^{*})$ using the recursive definition
(4) until we arrive at descendants $\Phi(H^{\prime},z^{*},w^{*})$ with
$H^{\prime}\in\mathcal{R}$ (note that $z^{*},w^{*}\in Z(H^{\prime})$
necessarily holds in all such descendants), we end up with a decomposition of
size $\widetilde{O}(n/r)$ instead of $O(\log{n})$: there are $O(n/r)$ distinct
pieces in $\mathcal{R}$ and to every piece $H^{\prime}\in\mathcal{R}$ in the
decomposition one can apply Lemma 6.3 to see that it decomposes into
$O(\log{n})$ elements.

By modifying $\mathtt{detect}$ easily so that it obeys the above
$\mathcal{R}$-aware decomposition of $\Phi(G^{*},s^{*},t^{*})$, we obtain that
$\widetilde{O}(n/r)$ preprocessed graphs of the form either
$\mathrm{DDG}(H^{\prime},z^{*},w^{*})$ or $\mathrm{DDG}(H^{\prime})$, where
$H^{\prime}\in\mathcal{R}$, contribute to $O(\log{n})$ negative cycle
detection algorithm applications on some graph $X=D(H,x^{*},y^{*})$. As a
result, the total number of vertices in such graphs $X$ is
$\widetilde{O}(n/r)\cdot O(\sqrt{r})=\widetilde{O}(n/\sqrt{r})$, and by a
similar analysis we have
$T_{\mathrm{cp}}(X)=\widetilde{O}(|V(X)|),T_{\mathrm{nn}}(X)=\widetilde{O}(|V(X)|)$,
and $Q_{\mathrm{nn}}(X)=\widetilde{O}(1)$. Since the bottleneck of
$\mathtt{detect}$ lies in using the algorithm behind Theorem 3.6 on such
graphs $X$, $\mathtt{detect}$ requires

$\sum_{X}\widetilde{O}\left(\sqrt{|V(X)|}\cdot|V(X)|\log{C}\right)=\widetilde{O}\left(\sqrt{\frac{n}{\sqrt{r}}}\log{C}\right)\cdot\sum_{X}\widetilde{O}(|V(X)|)=\widetilde{O}\left(\frac{n^{3/2}}{r^{3/4}}\log{C}\right).$

Observe that although choosing a small parameter $r$ increases the running
time of $\mathtt{detect}$, it causes that we only use the preprocessed data
for pieces that constitute weak descendants of the pieces in
$H\in\mathcal{R}$. When an edge capacity is updated, only $O(1)$ pieces of
$\mathcal{R}$ containing that edge are affected, i.e., the associated
preprocessed data structures of these pieces and their descendants might no
longer contain correct data. At the same time, the preprocessed data
structures for other pieces of $\mathcal{R}$ remain valid. Consequently, after
a single edge capacity update, the possibly invalid data for an affected piece
$H\in\mathcal{R}$ containing that edge and all its descendants can be
recomputed from scratch in $\widetilde{O}\left(\sum_{H\supseteq
B\in\mathcal{T}(G^{*})}|B|+|\partial{B}|^{2}\right)=\widetilde{O}(r)$ time. By
choosing $r=n^{6/7}$, we obtain the following.

######  Theorem 6.7.

Let $G$ be a planar digraph with integer edge capacities in $[1,C]$ and let
$\lambda\in[1,nC]$ be an integer. There exists a dynamic data structure with
$\widetilde{O}(n)$ preprocessing time that can test whether there exists an
$s,t$-flow of value $\lambda$ for any given query source/sink pair $(s,t)$ in
$\widetilde{O}(n^{6/7}\log{C})$ time, and supports edge capacity updates in
$\widetilde{O}(n^{6/7})$ time.

By proceeding analogously as in Section 6.4, the above data structure can be
converted to a dynamic $(1+\epsilon)$-approximate max $s,t$-flow oracle with
$\widetilde{O}(n^{6/7}\log{(C)}/\epsilon)$ worst-case update time and
$\widetilde{O}(n^{6/7}\log{C}\cdot\log(\log{(C)}/\epsilon))$ query time, which
proves Theorem 1.5.

###  6.6 An exact max $s,t$-flow oracle

In this section we show that using subquadratic space and preprocessing time
one can still support exact max $s,t$-flow queries in sublinear time.

Consider the feasible flow oracle of Section 6.3 along with the $r$-division-
aware modification of the procedure $\mathtt{detect}$ of Section 6.5. Note
that the procedure $\mathtt{detect}$ runs in
$\widetilde{O}(n^{3/2}/r^{3/4}\cdot\log{C})$ time as long as we guarantee that
the relevant closest-pair and near neighbor data structures for the graph
$D(H,x^{*},y^{*})$, that preserves distances between $\partial{H}$ in
$G^{*}_{\lambda}[H](x^{*},y^{*})$, can be constructed in
$\widetilde{O}(|\partial{H}|)$ time whenever we end up in a leaf call. In the
following, we concentrate on case 2 of $\mathtt{detect}$, since case 1 can be
handled in $O(1)$ time even with no preprocessing. The main goal in this
section is to prove the following key lemma.

######  Lemma 6.8.

Let $H\in T(G^{*})$ be a piece and let $x^{*},y^{*}\in Z(H)$. After
preprocessing $H$ in $\widetilde{O}(|H|^{2})$ time, for any given $\lambda$,
one can construct closest pair and near neighbor data structures for
$D(H,x^{*},y^{*}):=\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$, as required
by the procedure $\mathtt{detect}$, satisfying
$T_{\mathrm{cp}}(D(H,x^{*},y^{*}))=\widetilde{O}(|\partial{H}|)$,
$T_{\mathrm{nn}}(D(H,x^{*},y^{*}))=\widetilde{O}(|\partial{H}|)$, and
$Q_{\mathrm{nn}}(D(H,x^{*},y^{*}))=\widetilde{O}(1)$.

Before proving Lemma 6.8, let us explain how it leads to an exact max
$s,t$-flow oracle with subquadratic preprocessing/space and sublinear query
time. We apply the preprocessing of Lemma 6.8 to every piece $H$ that is a
weak descendant of some piece in $T(G^{*})\cap\mathcal{R}$. Recall that the
sum of sizes of descendant pieces of $H$ is $\widetilde{O}(|H|)$ since
$T(G^{*})$ has depth $O(\log{n})$ and no two siblings share a natural face. As
a result, the preprocessing time is
$\sum_{H\in\mathcal{R}}\widetilde{O}(|H|^{2})=\widetilde{O}(r)\cdot\sum_{H\in\mathcal{R}}\widetilde{O}(|H|)=\widetilde{O}(nr)$.

Observe that using the preprocessing as given in Lemma 6.8,
$\mathtt{detect}(\lambda,G^{*},s^{*},t^{*})$ runs in
$\widetilde{O}(n^{3/2}/r^{3/4}\log{C})$ time even if $\lambda$ is a query
parameter. In order to compute the exact max $s,t$-flow value $\lambda^{*}$,
we simply find it via binary search (over the interval $[0,nC]$) whose
decisions are driven by the result of
$\mathtt{detect}(\lambda,G^{*},s^{*},t^{*})$. This way, we obtain:

See 1.1 The remaining part of this section is devoted to proving Lemma 6.8.

Recall that so far, the only preprocessing required by the closest pair and
near neighbor data structures was that of Lemma 5.1. Actually, the proof of
Lemma 5.1 goes through for $\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$ if
we only assume the min-decomposition of
$\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$ into Monge matrices with a
total of $\widetilde{O}(|\partial{H}|)$ rows and columns (as in Lemma 5.2) and
$\widetilde{O}(1)$-time access to the edge weights of
$\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$. In the current setting, we
need to access dense distance graphs and its decomposition into Monge matrices
for an arbitrary (integer) parameter $\lambda$ between $0$ and $\lambda^{*}$,
where $\lambda^{*}_{H}$ is the maximum value $\lambda$ such that
$G^{*}_{\lambda}[H](x^{*},y^{*})$ contains no negative cycle. Such
$\lambda^{*}_{H}$ can be computed via binary search or even in near-linear
strongly polynomial time using the planar maximum flow algorithm of [BK09,
Eri10] run on the dual of $G^{*}_{\lambda}[H](x^{*},y^{*})$. Unfortunately, we
cannot afford to apply preprocessing of Lemma 5.1 for all possible values
$\lambda$ so that all the required data is stored explicitly. Instead, we will
show that after $\widetilde{O}(|H|^{2})$ preprocessing we can access the
required data in $\widetilde{O}(1)$ time.

There are two challenges here. First, we need to be able to efficiently access
the edges of the dense distance graph
$\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$ for an arbitrary parameter
$\lambda$. Second, the partition of
$\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$ into Monge matrices might vary
for different values of $\lambda$. If we used Lemma 5.2 in a black-box way for
the latter task, we would need to spend a prohibitive time of
$\widetilde{\Omega}(|H|)$ on computing the partition. We will show that in our
case (assuming the $\widetilde{O}(|H|^{2})$ preprocessing), such a partition
can be computed faster, in $\widetilde{O}(|\partial{H}|)$ time, which is
sufficient for our needs.

Recall that the parameterized edges in $G^{*}_{\lambda}[H](x^{*},y^{*})$ form
a path $Q$ in the _dual_ of $G^{*}_{\lambda}[H](x^{*},y^{*})$. From the point
of view of $G^{*}_{\lambda}[H](x^{*},y^{*})$, $Q$ is a curve originating in
some hole $h_{Q}^{1}$ and ending in some hole $h_{Q}^{2}$ of
$G^{*}_{\lambda}[H](x^{*},y^{*})$ (possibly $h_{Q}^{1}=h_{Q}^{2}$), and not
crossing any other holes (in particular $h_{Q}^{1},h_{Q}^{2}$) of that graph.

For each of $O(1)$ pairs $h^{1},h^{2}$ of holes of $H$ (possibly
$h^{1}=h^{2}$), we will construct separate closest pair and near neighbor data
structures for a subgraph of
$D(H,x^{*},y^{*})=\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))$ containing
the edges between $V(h^{1})$ and $V(h^{2})$ (where we denote by $V(h^{i})$ the
boundary vertices of $H$ lying on $h^{i}$) with total update time
$\widetilde{O}\left(|V(h^{1})|+|V(h^{2})|\right)$ and query time
$\widetilde{O}(1)$. By Lemmas 3.2 and 3.5, this will yield the respective data
structures for $D(H,x^{*},y^{*})$.

Roughly speaking, for a pair $h^{1},h^{2}$, we will expose $O(1)$ partial999In
a partial Monge matrix, the Monge property is only satisfied if all the four
cells in the Monge property are defined, and the defined cells in every row
(column) lie in some number of consecutive columns (rows, resp.). Monge
matrices, whose element-wise minimum encodes the distances from $V(h^{1})$ to
$V(h^{2})$ in $G^{*}_{\lambda}[H](x^{*},y^{*})$, just as the decomposition of
Lemma 5.2 does. However, we will spend only
$\widetilde{O}\left(|V(h^{1})|+|V(h^{2})|\right)$ time on this.

####  6.6.1 The single-hole case

Let us first consider the easier case $h^{1}=h^{2}=h$. We will later reduce
the more involved case $h^{1}\neq h^{2}$ to that case.

Let us start with the following technical lemmas on the possible net number of
crossings of simple paths wrt. simple dual paths or cycles.

######  Lemma 6.9.

Let $G_{0}$ be a plane digraph. Let $P=u\to v$ be a simple path in $G_{0}$
such that both $u$ and $v$ lie on a single face $h$ of $G$. Let
$Q_{0}\subseteq G_{0}^{*}$ be either a simple path $f\to g$ such that $h\notin
V(Q_{0})\setminus\\{f,g\\}$, or a simple cycle in the dual $G_{0}^{*}$. Then
$\pi_{Q_{0}}(P)\in\\{-1,0,1\\}$.

###### Proof.

If $Q_{0}$ is a cycle, then by Fact 6.1 we have
$\pi_{Q_{0}}(P)=\pi_{P}(Q_{0})\in\\{-1,0,1\\}$. Otherwise, $Q_{0}$ is a simple
path in $G_{0}^{*}$ with at most one edge $z$ incident to $h$. Note that one
can embed an edge $vu$ inside $h$ so that it does not cross $z$. Since $P\cdot
vu$ is a simple directed cycle in $G_{0}+vu$ and $Q_{0}$ is a path in
$(G_{0}+vu)^{*}$, we have $\pi_{Q_{0}}(P\cdot vu)\in\\{-1,0,1\\}$ by Fact 6.1.
But, by construction, $vu,(vu)^{R}\notin E(Q_{0})$, so
$\pi_{Q_{0}}(P)=\pi_{Q_{0}}(P\cdot vu)$. ∎

######  Lemma 6.10.

For $u,v\in V(G_{0})$, let $P=u\to v$ be a path in $G_{0}$. Then:

  1. (a)

If $u$ and $v$ lie on a single face $h$ of $G$, and $P$ is simple, then

  2. (b)

If $f=g$, then $\pi(P)$ is uniquely determined by the respective sides of
endpoints $u,v$ wrt. $\mathcal{C}$.

###### Proof.

Now let us consider the latter claim. $\mathcal{C}$ partitions $G$ into two
connected parts $G_{1},G_{2}$ such that $G_{1}\cap G_{2}=\mathcal{C}$, and
$G_{1}$ is to the left of $\mathcal{C}$. Note that if both $u,v$ are in
$G_{i}$ for $i\in\\{1,2\\}$, then the crossing number of $P$ is $0$. If $u$ is
in $G_{1}$, and $v$ is in $G\setminus G_{1}$, then the crossing number
$\pi(P)$ is necessarily $1$. Similarly, if $u$ is in $G_{2}$, and $v$ is in
$G\setminus G_{2}$, $\pi(P)\equiv-1$. ∎

The next lemma provides a construction of a certain extension $G^{\prime}$ of
a plane digraph $G$, such that the shortest paths in $G^{\prime}$ encode the
shortest paths $R\subseteq G$ with a given crossing number wrt. a simple dual
path.

######  Lemma 6.11.

Let $G$ be a plane digraph with no negative cycles, and let $n=|V(G)|$. Let
$P^{*}=a\to b$ be some simple path in $G^{*}$ (in particular, $a\neq b$).
Then, in $O(n^{2})$ time one can construct another plane digraph $G^{\prime}$
with vertex set $V(G^{\prime})=\\{v_{j}:v\in V(G),j\in\\{-n,\ldots,n\\}\\}$
such that:

  1. 1.

For any $u,v\in V$, $j\in\\{-n,\ldots,n\\}$,
$\delta_{G^{\prime}}(u_{0},v_{j})$ equals the length of some $u\to v$ path
$R\subseteq G$ with $\pi_{P^{*}}(R)=j$,

  2. 2.