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

  3. 3.

For any $S\subseteq V(G)$ such that the vertices $S$ lie on a single face
$f\notin V(P^{*})\setminus\\{a,b\\}$ of $G$, and for any
$j\in\\{-n,\ldots,n\\}$ the vertices $S_{j}:=\\{s_{j}:s\in S\\}$ lie on a
single face of $G^{\prime}$. Moreover, the faces containing $S_{j}$ for
distinct $j$ are either equal or vertex-disjoint.

###### Proof.

The graph $G^{\prime}$ is defined similarly to the infinite _universal cover
graph_ from [Eri10, Section 2.4], albeit $G^{\prime}$ is finite. It is
obtained as follows: first obtain a graph $\tilde{G}$ by introducing an
auxiliary vertex wherever the curve $P^{*}$ crosses the embedding of $G$, and
connecting the neighboring auxiliary vertices on $P^{*}$ by auxiliary edges
embedded in a way that there is a path in $\tilde{G}$ embedded exactly as
$P^{*}$. Next, cut $\tilde{G}$ along the path $P^{*}$, so that the obtained
graph $\tilde{G}^{\prime}$ has two copies $P^{*}_{L}$ and $P^{*}_{R}$ of
$P^{*}$. Make $2n+1$ copies
$\tilde{G}^{\prime}_{-n},\ldots,\tilde{G}^{\prime}_{n}$ of the graph
$\tilde{G}^{\prime}$. Label the copy of a vertex $v$ in
$\tilde{G}^{\prime}_{i}$ with $v_{i}$. Connect the copies into a chain by
gluing the path $P^{*}_{L}$ of the copy $\tilde{G}^{\prime}_{i}$ with the path
$P^{*}_{R}$ of the copy $\tilde{G}^{\prime}_{i+1}$ for all $i=-n,\ldots,n-1$.
Finally, remove from the obtained graph all the (copies of) auxiliary vertices
and edges except those appearing on $P^{*}_{L}$ in $\tilde{G}^{\prime}_{-n}$
and on $P^{*}_{R}$ in $\tilde{G}^{\prime}_{n}$. See Figure 1.

Figure 1: Construction on the graph $G^{\prime}$ from Lemma 6.11. The gray
$u\to v$ path in $G$ is preserved in the graph $G^{\prime}$ in the bottom

By construction, every path $R^{\prime}=u_{0}\to v_{j}$ in $G^{\prime}$
corresponds to some path $R=u\to v$ in $G$ with $\pi_{P^{*}}(R)=j$. This
implies property $1$.

For a _simple_ path $R=u\to v$ in $G$, $R$ is preserved in $G^{\prime}$ for
the following reason. Suppose $R=e_{1}\ldots e_{k}$, where $e_{i}=x_{i}y_{i}$,
and denote by $c_{i}$, $i=0,\ldots,k$, the crossing number
$\pi_{P^{*}}(\\{e_{1},\ldots,e_{i}\\})$. That is, the $c_{i}$ is the number of
times $e_{1}\ldots e_{i}$ crosses $P^{*}$ left to right, minus the number of
times it crosses $P^{*}$ right to left. Note that we have $|c_{i}|\leq i$ and
$k\leq n$ since $R$ is simple. As a result, we have $|c_{i}|\leq n$ for all
$i$. It follows that a path
$R^{\prime}=u_{0}(y_{1})_{c_{1}}(y_{2})_{c_{2}}\ldots(y_{k})_{c_{k}}=u_{0}\to
v_{c_{k}}$ exists in $G^{\prime}$ and has the same length as $R$ in $G$. This
proves property 2.

Note that all the copies of vertices lying on faces $a$ or $b$ in $G$ lie on a
single face of $G^{\prime}$. If some face $f\notin\\{a,b\\}$ of $G$ is not an
intermediate vertex of $P^{*}$, then there are vertex-disjoint copies of $f$
in all parts $\tilde{G}^{\prime}_{i}$ of $G^{\prime}$. This proves property 3.
∎

If $h^{1}_{Q}=h^{2}_{Q}$, then $Q$ is a simple directed cycle in the dual. As
discussed earlier, the crossing number $\pi_{u,v}$ of _any_ path $u\to v$ path
in $G^{*}_{\lambda}[H](x^{*},y^{*})$ wrt. $Q$ is in $\\{-1,0,1\\}$ and is
uniquely determined by the positions (i.e., exterior or interior) of the
vertices $u,v$ wrt. $Q$. As a result, we have
$\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(u,v)=\delta_{G^{*}_{0}[H](x^{*},y^{*})}(u,v)+\pi_{u,v}\cdot\lambda$.
Consequently, the edge weights of $uv$ in $D(H^{*},x^{*},y^{*})$ for $u,v\in
V(h)$ can be accessed in $O(1)$ time by shifting the respective weight of
$\mathrm{DDG}(G^{*}_{0}[H](x^{*},y^{*}))$ by $\lambda\cdot\pi_{u,v}$. To
decompose $\mathrm{DDG}(G^{*}_{\lambda}[H](x^{*},y^{*}))[V(h)]$ into Monge
matrices, it is enough to use the decomposition of Lemma 5.2 $O(1)$ times, as
follows. Express $V(h)=A\cup B$ so that the sets $A$ and $B$ lie on different
sides of $Q$. Then, for each pair $(I,J)\in\\{A,B\\}^{2}$, we include in the
desired decomposition the decomposition of
$\mathrm{DDG}(G^{*}_{0}[H](x^{*},y^{*}))$ into Monge matrices but limited to
rows $I$ and columns $J$. For each such combination $(I,J)$, the value
$\pi_{u,v}$ is equal for all $(u,v)\in I\times J$. Therefore, for each Monge
matrix included in our decomposition all its entries get shifted by the same
value, which clearly preserves the Monge property. Observe that if
$h^{1}_{Q}=h^{2}_{Q}$, this strategy works even for the more involved case of
two distinct holes $h^{1}\neq h^{2}$, so we will neglect it later on in
Section 6.6.2.

Let us now assume $h^{1}_{Q}\neq h^{2}_{Q}$. Since $h^{1}_{Q}\neq h^{2}_{Q}$,
we can build a graph $Z^{\prime}$ from Lemma 6.11 for the graph
$G:=Z=G^{*}_{0}[H](x^{*},y^{*})$ and the dual path $P^{*}:=Q$. Using one of
the well-known methods, e.g. [EFL18], we enforce uniqueness of shortest paths
on the graph $Z^{\prime}$ by only manipulating its edge weights and so that
the original path weight can be recovered in $\widetilde{O}(1)$ time from the
transformed graph. For any face $f$ of $Z$, denote by $f_{j}$ the face of
$Z^{\prime}$ that contains the vertices $\\{v_{j}:v\in V(f)\\}$, where
$v_{j}\in V(Z^{\prime})$ is defined as in Lemma 6.11.

Next, we construct an MSSP data structure on $Z^{\prime}$ with a distinguished
face $h_{0}$ (that is, the $0$-th copy of the face $h$ whose vertices‘
pairwise distance are of our interest) in a way that allows accessing the
shortest path trees from the vertices on $h_{0}$ via a dynamic tree interface.
Note that computing $Z^{\prime}$ and the associated data structures takes
$\widetilde{O}(|Z^{\prime}|)=\widetilde{O}(|H|^{2})$ time.

In order to construct the part of $D(H,x^{*},y^{*})$ that is responsible for
encoding the distances between the vertices of $V(h)$, we use an auxiliary
graph $D_{h}=\left(V(h),\bigcup_{j\in\\{-1,0,1\\}}E_{h,j}\right)$, satisfying
the following. Each $E_{h,j}$ contains for every $u,v\in V(h)$ an edge $uv$
with weight $\delta_{Z^{\prime}}(u_{0},v_{j})+j\cdot\lambda$.

######  Lemma 6.12.

For any $u,v\in V(h)$,
$\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(u,v)=\delta_{D_{h}}(u,v)$.

###### Proof.

Since $G^{*}_{\lambda}[H](x^{*},y^{*})$ has no negative cycles, for any
$u,v\in V(h)$, there exists a shortest $u\to v$ path $P$ in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ that is simple. As a result, the length of
$P$ equals its length in $G^{*}_{0}[H](x^{*},y^{*})$ plus
$\lambda\cdot\pi_{Q}(P)$. Recall that the intermediate faces of $Q$ are not
holes of $H$. As a result, by Lemma 6.9, $P$ has crossing number $\pi_{Q}(P)$
in $\\{-1,0,1\\}$. Therefore, the distance from $u$ to $v$ in $D_{h}$ is no
more than $\delta_{Z^{\prime}}(u_{0},v_{\pi_{Q}(P)})+\pi_{Q}(P)\cdot\lambda$.
By Lemma 6.11, $\delta_{Z^{\prime}}(u_{0},v_{\pi_{Q}(P)})$ is no more than the
length of any simple $u\to v$ path in $G^{*}_{0}[H](x^{*},y^{*})$ with
crossing number $\pi_{Q}(P)$, in particular, it is no more than the length of
$P$ in $G^{*}_{0}[H](x^{*},y^{*})$. Hence, we indeed obtain
$\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(u,v)\geq\delta_{D_{h}}(u,v)$.

If we had $\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(u,v)>\delta_{D_{h}}(u,v)$
for some $u,v\in V(h)$ then there would exist an edge $wz$ in some $E_{h,j}$
with
$\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(w,z)>\delta_{Z^{\prime}}(w_{0},z_{j})+j\cdot\lambda$.
But then there would exist a (not necessarily simple) $w\to z$ path
$P\subseteq G^{*}_{0}[H](x^{*},y^{*})$ with $\pi_{Q}(P)=j$ such that its cost
in $G^{*}_{\lambda}[H](x^{*},y^{*})$ is less than
$\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(w,z)$. This is a contradiction in a
graph with no negative cycles. ∎

Of course, we cannot build the graph $D_{h}$ explicitly since its size may be
$\Theta(|\partial{H}|^{2})$. Note that for any $u,v\in V(h)$, the (minimum)
weight of an edge $uv$ in $D_{h}$ can be queried in $\widetilde{O}(1)$ time
using the MSSP data structure built on $Z^{\prime}$. However, in order to
allow building fast closest pair and near neighbor data structures on $D_{h}$,
we still need to efficiently express the edge weights matrix of $D_{h}$ using
Monge matrices. Recall that these edge weights encode (shifted) distances
between the face $h_{0}$ and faces $h_{-1},h_{0},h_{1}$ in the graph
$Z^{\prime}$. The distances between vertices of $h_{0}$ are easily decomposed
into Monge matrices with a total of $\widetilde{O}(|V(h_{0})|)$ rows and
columns (counted with multiplicity) based on the ordering of vertices on
$h_{0}$ exclusively, using the following fact.

######  Fact 6.13.

Let $A$ and $B$ be two non-interleaving (wrt. to a clockwise order) subsets of
vertices lying on a single face of a plane digraph. Let $\mathcal{M}$ be a
matrix encoding all-pairs distances from vertices $a\in A$ to vertices $b\in
B$. Then, $\mathcal{M}$ is a Monge matrix.

[FR06] apply the above fact a logarithmic number of times to decompose all-
pairs distances between $k$ vertices lying on a single face of a plane digraph
into Monge matrices with a total of $\widetilde{O}(k)$ rows/columns. These
rows/columns depend only on the ordering of the vertices on the face.

The distances between $h_{0}$ and $h_{j}$, if $h_{0}\neq h_{j}$, are more
tricky to decompose into an element-wise minimum of Monge matrices. [MW10]
deal with this problem by observing that from an arbitrary shortest paths tree
$T$ rooted at a vertex $s$ of $h_{0}$, one can choose two paths such that for
every two vertices $v_{1},v_{2}$ on the holes $h_{0},h_{j}$ respectively, some
shortest $v_{1}\to v_{2}$ path in $Z^{\prime}$ either does not cross the
former path or does not cross the latter. Cutting $Z^{\prime}$ along each of
these paths (separately) yields two graphs where $V(h_{0})$ and $V(h_{j})$
together lie on _a single face_ (and do not interleave) of the respective
graph. As a result, one can view distances between them as a single (full)
Monge matrix. The element-wise minimum of distances in the two graphs
represents distances between $h_{0}$ and $h_{j}$ in the original graph.
Unfortunately, finding the paths used for cutting, actually cutting the graph
explicitly, and preprocessing the obtained cut graphs would be too costly in
our case.

The following lemma shows a more efficient way to compute the partition of
distances between $h_{0}$ and $h_{j}$ into _partial_ Monge matrices, and thus
also an efficient construction of closest pair and near neighbor data
structures for a graph induced on the edges $E_{h,j}$. Recall that in a
partial Monge matrix the elements in each row and each columns are defined
only in a consecutive segment of columns or rows, respectively. As a result,
for a partial Monge matrix with rows $R$ and columns $C$, it takes only
$O(|R|+|C|)$ space to encode which elements are defined: one only needs to
encode the ordering of rows and columns, and a single segment in each row.
Below, when talking about decomposing into partial Monge matrices, we will
mean computing an encoding as defined above.

######  Lemma 6.14.

Suppose $h_{0}\neq h_{j}$. There exist closest pair and near neighbor data
structures for $D_{h}[E_{h,j}]$ with
$T_{\mathrm{cp}}(D_{h}[E_{h,j}]),T_{\mathrm{nn}}(D_{h}[E_{h,j}])\in\widetilde{O}(|V(h_{0})|+|V(h_{j})|)$,
and $Q_{\mathrm{nn}}(D_{h}[E_{h,j}])=\widetilde{O}(1)$.

###### Proof.

Recall from Lemma 6.11 that the faces $h_{0}$ and $h_{j}$ in $Z^{\prime}$ are
vertex-disjoint. First, pick such $s\in V(h_{0})$ and $t\in V(h_{j})$ that the
unique $s\to t$ shortest path $Y$ in $Z^{\prime}$ does not contain any other
vertices of $V(h_{0})\cup V(h_{j})$. This can be done in
$\widetilde{O}(|V(h_{0})|+|V(h_{j})|)$ time as follows. First pick any
$s^{*}\in V(h_{0})$. Then, pick such a $t\in V(h_{j})$ that has the lowest
depth in the shortest paths tree from $s^{*}$ stored in the MSSP data
structure – this can be done in $\widetilde{O}(|V(h_{j})|)$ time. Finally, on
the shortest $s^{*}\to t$ path, pick the deepest vertex $s\in V(h_{0})$ in a
similar way. By construction, the $s\to t$ subpath of the $s^{*}\to t$ path
contains no other vertices from $V(h_{0})\cup V(h_{j})$.

Fix some vertex $u\in V(h_{0})$. The shortest path $P_{t}=u\to t$ shares some
suffix $S$ with $Y$ (possibly only the vertex $t$) due to uniqueness and
cannot cross $Y$. Suppose wlog. that $P_{t}$ merges with $Y$ from the left
side of $Y$ (the other case is symmetric), and denote by $A$ the set of
vertices $u$ with this property (so $u\in A$).

Let us observe that for any $v\in V(h_{j})$, the shortest $u\to v$ path
$P_{v}$ _does not cross_ $Y$ right to left: indeed, if the crossing vertex $w$
was at the subpath $S$, this would contradict uniqueness of the $u\to w$
subpath of $P_{t}$. On the other hand, if the path $P_{v}$ crosses $Y$ at
vertex $w$ before the subpath $S$, then it would need to cross either
$P_{t}\setminus S$ or $Y\setminus S$ once more on the way to $w$, and thus
this would violate the uniqueness of $P_{t}$ or $Y$ respectively.

Let us embed an auxiliary vertex $u^{\prime}$ and an edge $u^{\prime}u$ inside
the face $h_{0}$ of $Z^{\prime}$ and call that edge the $0$-th _sentinel_ edge
of any shortest path $P_{x}=u\to x$. If $x\in V(h_{j})\setminus\\{t\\}$, then
let $e_{x}$ ($e_{x}^{\prime}$) be the earliest edge of the path $P_{x}$
($P_{t}$, resp.) that does not belong to $P_{t}$ ($P_{x}$, resp.). Note that
if $e_{x}$ emerges from the path $P_{t}$ to the left (that is, $e_{x}=ab$ lies
between $e_{x}^{\prime}$ and and the preceding edge of $e_{x}^{\prime}$ on
$P_{t}$ in the clockwise edge ring of $a$), then $P_{x}$ does not cross
$P_{t}$ and thus also does not cross $Y$ (it might still share some prefix
with $P_{t}$, and some subpath with $Y$, though). On the other hand, if
$e_{x}$ emerges from the path $P_{t}$ to the right, then the shortest $u\to x$
path has to cross $Y$ once. Let $\mathcal{L}_{u}\subseteq V(h_{j})$ contain
$t$ and the vertices $x\in V(h_{j})\setminus\\{t\\}$ such that $e_{x}$ emerges
from $P_{t}$ to the left. Similarly, let $\mathcal{R}_{u}\subseteq V(h_{j})$
contain the vertices $x$ of $h_{j}$ such that $e_{x}$ emerges from $P_{t}$
strictly to the right. Since the paths $P_{x}$ for $x\in V(h_{j})$ are
pairwise non-crossing, $\mathcal{L}_{u}$ and $\mathcal{R}_{u}$ constitute
consecutive fragments of $V(h_{j})$ as ordered on the face $h_{j}$. Moreover,
the border between $\mathcal{L}_{u}$ and $\mathcal{R}_{u}$ can be computed via
binary search on the vertices $x\in V(h_{j})$: whether $x\in\mathcal{L}_{u}$
or $x\in\mathcal{R}_{u}$ can be decided using an LCA query and a level
ancestor query on the shortest path tree from $u$. If we make MSSP use the top
tree [AHdLT05] for dynamic tree operations, these queries are supported in
polylogarithmic time.

As $Y$ is a unique $s\to t$ shortest path, it is a simple path. Consider a
graph $Z^{\prime}_{s,t}$ obtained from $Z^{\prime}$ by cutting $Z$ along the
path $Y$ (that is, the vertices and edges of $Y$ appear in $Z^{\prime}_{s,t}$
in two copies). Now, let $Z^{\prime\prime}_{s,t}$ be obtained by gluing two
copies of $Z^{\prime}_{s,t}$ along one of the copies of $Y$ (that is,
$Z^{\prime\prime}_{s,t}$ contains three copies of $Y$). Denote by
$Z^{\prime\prime}_{s,t,L}$ ($Z^{\prime\prime}_{s,t,R}$) the copy of
$Z^{\prime}_{s,t}$ to the left (to the right, resp.) of the path $Y$ used for
gluing the two copies into $Z^{\prime\prime}_{s,t}$. Note that the graph
$Z^{\prime\prime}_{s,t}$ contains two copies of each vertex in
$V(h_{0})\setminus\\{s\\}$ and $V(h_{j})\setminus\\{t\\}$. For each such
vertex $x$, denote by $x_{L},x_{R}$ the copies in the respective parts
$Z^{\prime\prime}_{s,t,L}$, $Z^{\prime\prime}_{s,t,R}$. Moreover,
$Z^{\prime\prime}_{s,t}$ contains three copies of $s$ and $t$. For
$x\in\\{s,t\\}$, set both $x_{L},x_{R}$ to be the ’’middle‘‘ copy on the copy
of path $Y$ used for gluing.

Impose a natural clockwise order starting at $s$ of $V(h_{0})$ on the face
$h_{0}$ of $Z^{\prime}$. Similarly, impose a counter-clockwise order on
$V(h_{j})$ starting at $t$ on the face $h_{j}$ of $Z^{\prime}$. For
$W\subseteq V(Z^{\prime})$, let $W_{L}=\\{w_{L}:w\in W\\}$ and similarly
define $W_{R}$. Note that the vertices $V(h_{0})_{L}$, $V(h_{0})_{R}$,
$V(h_{j})_{L}$, $V(h_{j})_{R}$ all lie on a _single face_ $f$ of
$Z^{\prime\prime}_{s,t}$ in the clockwise order
$V(h_{0})_{L},V(h_{0})_{R},V(h_{j})_{R},V(h_{j})_{L}$, where each of this sets
is ordered using the order imposed on the respective original set $V(h_{0})$,
$V(h_{j})$.

Observe that every path in $Z^{\prime\prime}_{s,t}$ naturally corresponds to
some path in $Z^{\prime}$ (after projecting the copies of vertices to
respective original vertices of $Z^{\prime}$). As a result, if some vertices
$u^{\prime},v^{\prime}$ of $Z^{\prime\prime}_{s,t}$ are copies of $u,v$
respectively in $Z^{\prime}$, then
$\delta_{Z^{\prime\prime}_{s,t}}(u^{\prime},v^{\prime})\geq\delta_{Z^{\prime}}(u,v)$.
Moreover, for a shortest path $P_{u,v}=u\to v$ in $Z^{\prime}$, if $u\in A$
and $v\in\mathcal{L}_{u}$, there is a path $u_{L}\to v_{L}$ in
$Z^{\prime\prime}_{s,t,L}$ corresponding to $P_{u,v}$. Consequently,
$\delta_{Z^{\prime}}(u,v)=\delta_{Z^{\prime\prime}_{s,t}}(u_{L},v_{L})$.
Similarly, if $u\in A$ and $v\in\mathcal{R}_{u}$, there is a path $u_{L}\to
v_{R}$ in $Z^{\prime\prime}_{s,t}$ corresponding to $P_{u,v}$, and we obtain
$\delta_{Z^{\prime}}(u,v)=\delta_{Z^{\prime\prime}_{s,t}}(u_{L},v_{R})$.

Consider a matrix $\mathcal{M}$ with rows $A$ and columns $V(h_{j})_{R}\cup
V(h_{j})_{L}$ such that in a row $u\in A$, the elements are defined only for
columns $(\mathcal{R}_{u})_{R}\cup(\mathcal{L}_{u})_{L}$. If
$k^{\prime}\in(\mathcal{R}_{u})_{R}\cup(\mathcal{L}_{u})_{L}$ is a copy of
$k\in V(h_{j})$, then we put
$\mathcal{M}_{a,k^{\prime}}=\delta_{Z^{\prime}}(a,k)$. Note that if the
columns of $\mathcal{M}$ are ordered as in the clockwise order on the face $f$
of $Z^{\prime\prime}_{s,t}$, then
$(\mathcal{R}_{u})_{R}\cup(\mathcal{L}_{u})_{L}$ constitutes a contiguous
segment of columns of $\mathcal{M}$.

We now argue that for each column $k^{\prime}$ (such that $k^{\prime}$ is a
copy of vertex $k$) of $\mathcal{M}$, the defined elements of that column lie
in a consecutive segment of rows of $\mathcal{M}$. Suppose wlog. that
$k^{\prime}\in V(h_{j})_{L}$. Then, for $a,b\in A$, the elements
$\mathcal{M}_{a,k^{\prime}}$ and $\mathcal{M}_{b,k^{\prime}}$ are both defined
iff the shortest paths $P_{a,k}$ and $P_{b,k}$ both do not cross $Y$ in
$Z^{\prime}$. Clearly, for any $c\in A$ that lies between $a$ and $b$ in the
clockwise order of $V(h_{0})$, the path $P_{c,k}$ is weakly contained in a
cycle consisting of $P_{a,k},P_{b,k}$, and the $a\to b$ part of the enclosing
cycle of $V(h_{0})$ that does not contain $s$. As a result, since $P_{a,k}$
and $P_{b,k}$ do not cross $Y$, indeed $P_{c,k}$ does not cross $Y$ and we
conclude that $\mathcal{M}_{c,k^{\prime}}$ is defined as well.

Since the rows and columns of $\mathcal{M}$ are non-interleaving subsets of
vertices on a single face $f$ of $Z_{s,t}^{\prime\prime}$, from Fact 6.13 we
conclude that $\mathcal{M}$ is indeed a partial Monge matrix. Note that
(values of) the defined elements of $\mathcal{M}$ do not depend on the choice
of $s,t$ – they constitute distances in $Z^{\prime}$ and thus can be accessed
in $\widetilde{O}(1)$ time using the MSSP data structure that we have built
upon $Z^{\prime}$. Any partial $m_{1}\times m_{2}$ Monge matrix can be
decomposed into a collection $D$ of full Monge matrices with
$\widetilde{O}(m_{1}+m_{2})$ rows and columns (counted with multiplicities).
For an intuition and proof, see [GMW20, Lemma 5.1, Theorem 5.5, and Figures
3,4,5].

The defined entries of $\mathcal{M}$ do not quite correspond to the weights of
edges $E_{h,j}\cap(A\times V(h_{j}))$: the columns of $\mathcal{M}$ include
two copies of each vertex of $V(h_{j})$. However, we can easily obtain a graph
$G_{h,j}$ whose $A\times V(h_{j})$ distances are equal to the weights of
$E_{h,j}\cap(A\times V(h_{j}))$. Let the vertices of $G_{h,j}$ be $A\cup
V(h_{j})_{L}\cup V(h_{j})_{R}\cup V(h_{j})$. $G_{h,j}$ contains a subgraph
$G_{\mathcal{M}}$ with edges between $A$ and $V(h_{j})_{L}\cup V(h_{j})_{R}$
corresponding to the defined elements of $\mathcal{M}$, and $2|V(h_{j})|$
auxiliary edges $u_{L}u,u_{R}u$ of weight $0$ for all $u\in V(h_{j})$.
Similarly as in the proof of Lemma 5.1, we can use the data structure of
[MNW18, Lemma 1] and the Monge heap to obtain (via Lemmas 3.5 and 3.2 applied
to the decomposition $D$ of $\mathcal{M}$ into full Monge matrices) near
neighbor and closest pair data structures for $G_{\mathcal{M}}$ with total
update time $\widetilde{O}(|V(h_{0})|+|V(h_{j})|)$ and query time
$\widetilde{O}(1)$. To obtain the desired closest pair and near neighbor data
structures for $G_{h,j}$ (which, as argued above, can serve as the respective
data structures for $D_{h}[E_{h,j}]$) we simply apply Lemmas 3.2 and 3.5 once
again to the data structures for $G_{\mathcal{M}}$ and the trivial data
structures for $G_{h,j}\setminus G_{\mathcal{M}}$ which contain
$\widetilde{O}(|V(h_{0})|+|V(h_{j})|)$ auxiliary non-structured edges.

We proceed symmetrically with the distances from $V\setminus A$ to $V(h_{j})$.
Finally, we merge the obtained data structure for graphs representing
distances $A\times V(h_{j})$ and $(V\setminus A)\times V(h_{j})$, resp. into a
single one with asymptotically same time bounds using Lemmas 3.2 and 3.5. ∎

With the data structures of Lemma 6.14 in hand, we can again apply Lemmas 3.5
and 3.2 to get the desired data structures for $D_{h}=D_{h}[E_{h,-1}]\cup
D_{h}[E_{h,0}]\cup D_{h}[E_{h,1}]$ with total update time
$\widetilde{O}\left(|V(h)|\right)=\widetilde{O}(|\partial{H}|)$ and query time
$\widetilde{O}(1)$. This way, we achieve our goal for the case $h^{1}=h^{2}$.

####  6.6.2 The case of two distinct holes

The primary difference between the case $h^{1}\neq h^{2}$ and the single-hole
case is that it is no longer the case that the crossing number of a path from
$h^{1}$ to $h^{2}$ has wrt. $Q$ is necessarily in $\\{-1,0,1\\}$. We will
nevertheless prove the following. Recall that we have already handled the case
$h^{1}_{Q}=h^{2}_{Q}$, so below we assume $h^{1}_{Q}\neq h^{2}_{Q}$.

######  Lemma 6.15.

Let $s\in V(h^{1})$, $t\in V(h^{2})$, where $h^{1}\neq h^{2}$. Suppose there
exists a _simple_ shortest ${s\to t}$ path $P$ in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ such that $V(P)\cap(V(h^{1})\cup
V(h^{2}))=\\{s,t\\}$ with crossing number $\pi_{Q}(P)$. Then, for any
$(u,v)\in V(h^{1})\times V(h^{2})$, there exists some shortest $u\to v$ path
in $G^{*}_{\lambda}[H](x^{*},y^{*})$ with crossing number wrt. $Q$ in
$[\pi_{Q}(P)-4,\pi_{Q}(P)+4]$.

###### Proof.

Since $P$ is a shortest path that is simple, there exists some simple shortest
path $S=u\to v$ that does not cross $P$ more than once (either from left to
right or right to left). Let us focus on the case when $P$ and $S$ have at
least one vertex in common, and $S$ indeed crosses $P$ once, wlog. left to
right. The other cases, when $P$ and $S$ are completely disjoint or when they
have a common part, but do not cross, are easier to handle, and can by
considered analogously.

Since $P$ and $S$ have a vertex in common, one can write $P=P_{1}RP_{2}$,
$S=S_{1}RS_{2}$, where $x\to y=R\subseteq P$ is a possibly empty (i.e.,
containing zero edges) maximal common subpath of $P$ and $S$, and
$S_{1},S_{2}$ can share only endpoints with $V(P)$.

Let $G^{+}$ be the graph obtained from $G^{*}_{\lambda}[H](x^{*},y^{*})$ by
cutting it along $P$, so that $G^{+}$ has two copies of the vertices and edges
of $P$. Denote by $P_{L},P_{R}$ the left and right copies of $P$ respectively,
and by $w_{L},w_{R}$ the respective left and right copies of a vertex $w\in
V(P)$. For all $w\in V(H)\setminus V(P)$, set $w_{L}=w_{R}=v$. In this graph,
the vertices $(V(h^{1})\setminus\\{s\\})\cup(V(h^{2})\setminus\\{t\\})$ lie on
a single face $f$, and each of the two sets comprising this union forms a
segment of consecutive vertices on $f$. The other vertices on $f$ come from
the two copies of $P$. These sets also form contiguous segments on $f$, and
one can easily see that the ordering of vertices on $f$ can be wlog. assumed
to be $V(h^{1}),V(P_{L}),V(h^{2}),V(P_{R})$, where $V(P_{L})$ starts with
$s_{L}$, and $V(P_{R})$ starts with $t_{R}$.

Note that for $S_{1}=u\to x$, there exists a _unique_ corresponding path
$S_{1}^{+}=u_{L}\to x_{L}$ in $G^{+}$. Similarly, for $S_{2}=y\to v$, there
exists a unique corresponding path $S_{2}^{+}=y_{R}\to v_{R}$ in $G^{+}$. Let
$P_{1}^{+}$ be the $s_{L}\to x_{L}$ subpath of $P_{L}$, and let $P_{2}^{+}$ be
the $y_{R}\to t_{R}$ subpath of $P_{R}$ in $G^{+}$.

Consider the effect that cutting along $P$ has on the dual path $Q$. Express
$Q$ as$Q_{1}\cdot e_{1}\cdot Q_{2}\cdot e_{2}\cdot\ldots\cdot e_{k-1}\cdot
Q_{k}$ such that $P$ and $Q$ cross at edges $e_{1},\ldots,e_{k-1}$. Let
$i\in\\{2,\ldots,k-1\\}$. In $G^{+}$, each subpath $e_{i-1}\cdot Q_{i}\cdot
e_{i}$ of $Q$ corresponds to a simple curve $Q_{i}^{+}$ with both its
endpoints inside the face $f$, and intersecting the bounding cycle of $f$ at
copies of edges $e_{i-1},e_{i}$. As a result, each such $Q_{i}^{+}$ crosses
$f$ at some two points of $f$ that lie on the segments spanned by either
$V(P_{L})$ or $V(P_{R})$ on $f$. See Figure 2 for better understanding.
Regardless of which segments $Q_{i}^{+}$ crosses, every path from
$V(h^{1})\setminus\\{s\\}\cup\\{s_{L}\\}$ to some other fixed vertex $w$ on
$f$ in $G^{+}$ has the same crossing number wrt. $Q_{i}^{+}$ because
$V(h^{1})$ lies entirely on one side of the dual cycle $Q_{i}^{+}\subseteq
G^{+}$. For an analogous reason, every path from some fixed vertex $w$ on $f$
to a vertex of $V(h^{2})\setminus\\{t\\}\cup\\{t_{R}\\}$ has the same crossing
number wrt. $Q_{i}^{+}$. So the crossing numbers of $P_{j}^{+}$ and
$S_{j}^{+}$ (for $j=1,2$) wrt. $Q_{i}^{+}$ are equal.

Figure 2: Illustration for the proof of Lemma 6.15.

On the other hand, observe that the crossing number of $P_{j}$ wrt. $Q$, for
$j=1,2$, equals the sum of crossing numbers of $P_{j}^{+}$ wrt.
$Q_{2}^{+},\ldots,Q_{k-1}^{+}$. This is because the crossing number of $P_{j}$
wrt. each $Q_{l}$, where $l=1,\ldots,k$ is $0$ (by the definition of $Q_{l}$),
and the crossing number of $P_{j}$ wrt. some $e_{l}$, where $l=1,\ldots,k-1$,
contributes to precisely one of the crossing numbers of $P_{j}^{+}$ wrt.
$Q^{+}_{i}$. Moreover, the crossing number of $S_{j}$ wrt. $e_{1}\cdot
Q_{2}\cdot e_{2}\cdot\ldots\cdot Q_{k-1}\cdot e_{k-1}$, equals the sum of
crossing numbers of $S_{j}^{+}$ wrt. $Q_{2}^{+},\ldots,Q_{k-1}^{+}$. To see
this, recall that $S_{j}$, disjoint with $P$, has crossing number $0$ with all
$e_{l}$. But we have proved that the crossing numbers of $P_{j}^{+}$ and
$S_{j}^{+}$ wrt. each $Q_{i}^{+}$ are equal, and thus we conclude that the
crossing number of $P_{j}$ wrt. $Q$ equals the crossing number of $S_{j}$ wrt.
$Q\setminus Q_{1}\setminus Q_{k}$.

We now argue that the crossing number of $S_{j}$ wrt. $Q_{1}$ or $Q_{k}$ is in
$\\{-1,0,1\\}$. It will follow that the crossing number of $P_{j}$ wrt. $Q$
can deviate by at most $2$ from the crossing number of $S_{j}$ wrt. $Q$. Let
us focus on the crossing number wrt. $Q_{1}$, as the other case is analogous.
Since $Q_{1}$ is preserved in $G^{+}$, and $S_{j}$ is preserved in $G^{+}$ as
$S_{j}^{+}$, the crossing number of $S_{j}$ wrt. $Q_{1}$ in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ equals the crossing number of $S_{j}^{+}$
wrt. $Q_{1}$ in $G^{+}$. But the endpoints of the simple path $S_{j}^{+}$ lie
on a single face $f$ of $G^{+}$, and no intermediate vertex of $Q_{j}$ (seen
as a dual path in $G^{+}$) equals $f$, so the crossing number of $Q_{j}$ wrt.
$S_{j}^{+}$ is in $\\{-1,0,1\\}$ by Lemma 6.9.

To summarize, the crossing numbers of $P_{j}$ and $S_{j}$ wrt. $Q$ may differ
by at most $2$. We conclude that the crossing numbers of $P=P_{1}RP_{2}$ and
$S=S_{1}RS_{2}$ wrt. $Q$ can differ by at most $4$. ∎

######  Lemma 6.16.

Let the holes $h^{1},h^{2}$, where $h^{1}\neq h^{2}$, be fixed. In
$\widetilde{O}(|H|^{2})$ time one can build a data structure answering queries
of the following form in $\widetilde{O}(1)$ time. Given
$\lambda\in[0,\lambda^{*}]$, find some two vertices $s\in V(h^{1})$, $t\in
V(h^{2})$ and a number $k$ such that there exists a _simple_ shortest $s\to t$
path $P$ in $G^{*}_{\lambda}[H](x^{*},y^{*})$ with $V(P)\cap(V(h^{1})\cup
V(h^{2}))=\\{s,t\\}$ and the crossing number of $P$ wrt. $Q$ is $k$.

###### Proof.

Consider the graph $Z^{\prime}$ (built using Lemma 6.11) from Section 6.6.1.
Recall that for each vertex $v$ of $G^{*}_{0}[H](x^{*},y^{*})$, $Z^{\prime}$
has $2n+1$ copies $v_{-n},\ldots,v_{n}$ of $v$ so that a path from any $u_{0}$
to $v_{j}$ corresponds to an $u\to v$ path in $G^{*}_{0}[H](x^{*},y^{*})$ with
crossing number $j$ wrt. $Q$.

Pick any $s^{\prime}\in V(h^{1})$ and $t^{\prime}\in V(h^{2})$. Compute a
shortest paths tree $T$ from $s^{\prime}_{0}$ in $Z^{\prime}$. This takes
$O(|Z^{\prime}|)=O(|H|^{2})$ time. Denote by $T[v_{j}]$ the $s^{\prime}_{0}\to
v_{j}$ path in that tree, and by $\ell(T[v_{j}])$ its length.

Similarly as in Lemma 6.11, one can prove that $T[t^{\prime}_{j}]$ corresponds
to some $s^{\prime}\to t^{\prime}$ path in $G^{*}_{0}[H](x^{*},y^{*})$ with
crossing number wrt. $Q$ exactly $j$ and not longer than the shortest _simple_
$s^{\prime}\to t^{\prime}$ path in that graph with crossing number $j$.
Consequently, by proceeding as in the proof of Lemma 6.12, we obtain that the
length of the shortest $s^{\prime}\to t^{\prime}$ path in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ equals

$\min_{j\in\\{-n,\ldots,n\\}}\\{\ell(T[t^{\prime}_{j}])+\lambda\cdot j\\},$

and if some $j$ minimizes the above for a given $\lambda$, then the path
$T[t_{j}^{\prime}]$ can be projected to an $s^{\prime}\to t^{\prime}$ path in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ with cost precisely
$\ell(T[t^{\prime}_{j}])+\lambda\cdot j$, that is, a shortest $s^{\prime}\to
t^{\prime}$ path.

In order to be able to compute a minimizer $j$ given some $\lambda$, we apply
the following preprocessing. We want to compute a minimum of $2n+1=O(|H|)$
linear functions at coordinate $\lambda$. It is well-known that such a minimum
is the lower envelope of these functions and can be described using $k\leq 2n$
breakpoints $\lambda_{1},\ldots,\lambda_{k}$ and numbers $j_{1},\ldots,j_{k}$,
$j_{1}\geq\ldots\geq j_{k}$, such that for every $i=0,\ldots,k$, the minimum
at $\lambda\in[\lambda_{i},\lambda_{i+1})$ equals
$\ell(T[t^{\prime}_{j_{i}}])+\lambda\cdot j_{i}$ (where $\lambda_{0}=-\infty$
and $\lambda_{k+1}=\infty$). The lower envelope can be easily computed in
linear time. With the breakpoints, locating the path $T[t^{\prime}_{j^{*}}]$
that achieves the minimum for a given $\lambda$ can be done using binary
search in $\widetilde{O}(1)$ time.

The last problem is that the projection of $T[t^{\prime}_{j^{*}}]$ might not
correspond to a simple path in $G^{*}_{\lambda}[H](x^{*},y^{*})$, and it may
contain more than two vertices of $V(h^{1})\cup V(h^{2})$. To deal with this
problem, we make another preprocessing step on the tree $T$ so that to any
$T[v_{j}]$ with $v\in V(h^{2})$ we assign a simple path
$P^{*}_{v_{j}}\subseteq G^{*}_{0}[H](x^{*},y^{*})$ from $V(h^{1})$ to
$V(h^{2})$ such that $P^{*}_{v_{j}}$ is a projection of a subpath of
$T[v_{j}]\subseteq Z^{\prime}$ onto $G^{*}_{0}[H](x^{*},y^{*})$. Note that if
(the projection of) $T[t^{\prime}_{j^{*}}]$ is a shortest $s^{\prime}\to
t^{\prime}$ path in $G^{*}_{\lambda}[H](x^{*},y^{*})$, then
$P^{*}_{t^{\prime}_{j^{*}}}$, being a projection of a subpath of
$T[t^{\prime}_{j^{*}}]$, is also a shortest path in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ that meets the desired requirements. Recall
that we are only asked to return the endpoints of such a path, and its
crossing number wrt. $Q$.

We process the vertices $T$ in pre-order. On the way, we maintain a data
structure $\mathcal{D}$. We maintain the following invariant: before the
processing of $v_{j}$ (whose parent is $p_{l}$) starts, and also after it
finishes, $\mathcal{D}$ stores some simple $s^{\prime}\to p$ path $P_{p}$ in
$G^{*}_{0}[H](x^{*},y^{*})$ that is a projection of a subpath of $T[p_{l}]$.
We will first describe how the data structure is used, and explain how its
operations are implemented later.

Let $e_{v_{j}}$ be the parent edge of $v_{j}$ in $T$, and let $e_{v}$ be the
corresponding edge in $G^{*}_{0}[H](x^{*},y^{*})$. To process the vertex
$v_{j}$, we first check whether the path $P_{p}$ contains $v$. Since $P_{p}$
is simple, it might contain at most one occurrence of $v$. Suppose
$P_{p}=R_{1}R_{2}$, where $R_{1}=s^{\prime}\to v$. In this case, the path
$R_{1}$ forms a simple $s^{\prime}\to v$ path $P_{v}$ that is a projection of
a subpath of $T[p_{l}]$, so we may set $P_{v}:=R_{1}$. On the other hand, if
$P_{p}$ does not contain $v$, we may simply set $P_{v}:=P_{p}\cdot e_{v}$ and
achieve the same. We update the data structure $\mathcal{D}$ so that it stores
$P_{v}$. If $v\in V(h^{2})$, we use $\mathcal{D}$ to find the first vertex
$t_{v}\in V(h^{2})$ on $P_{v}$ (if exists), and then the latest vertex
$s_{v}\in V(h^{1})$ on $P_{v}$ that precedes the occurrence $t_{v}$. Note that
the $s_{v}\to t_{v}$ subpath of $P_{v}$ is simple, does not contain any other
vertices of $V(h^{1})\cup V(h^{2})$ apart from the endpoints $s_{v},t_{v}$,
and is a projection of a subpath of $T[v_{j}]$. We thus let $P^{*}_{v_{j}}$
equal that $s_{v}\to t_{v}$ subpath of $P_{v}$. We then record the endpoints
$s_{v},t_{v}$ of $P^{*}_{v_{j}}$ and its crossing number wrt. $Q$. Afterwards,
we process the children of $v$ recursively. Note that the invariant posed on
$\mathcal{D}$ is met. When all the children of $v$ are processed, we revert
changes to $\mathcal{D}$ so that it again stores $P_{p}$ instead of $P_{v}$.

We now explain how to implement the data structure $\mathcal{D}$ storing a
simple path $P$ in $G^{*}_{0}[H](x^{*},y^{*})$. First of all, $\mathcal{D}$
stores two arrays $A,I$, and the number of edges $q$ of the stored path $P$.
The array $A$ stores the subsequent vertices of $P$ at positions $1,\ldots,q$.
$I$ is indexed with vertices of $H$: the vertex $v$ might appear on $P$ only
at position $I[v]$ (if such a position exists). It might still hold that
$A[I[v]]\neq v$; then $P$ does not contain the vertex $v$.

Moreover, we store the positions of vertices from $V(h^{1})$ on the path $P$
in an array $L$. More precisely, if the vertices of $V(h^{1})$ appear on
positions $l_{1},\ldots,l_{g}$ on $P$, then $L[i]=l_{i}$ for all
$i=1,\ldots,g$. We also maintain the first occurrence of a vertex from
$V(h^{2})$ on the path $P$.

Finally, we also store the crossing numbers of all prefixes of $P$ in an array
$S$. That is, if $i\leq q$, then $S[i]$ is the crossing number of the subpath
$s^{\prime}\to A[i]$ of $P$. Storing prefix crossing numbers allows us to
compute the crossing number of any subpath of $P$ in $O(1)$ time by
subtracting two crossing numbers of path prefixes.

Suppose once again we start processing a vertex $v_{j}$ with parent $p_{l}$.
The array $I$ can locate the occurrence of $v$ on $P_{p}$, if it exists. To
make $\mathcal{D}$ store $P_{v}$, we either simply decrease $q$ (to $I[v]$) if
$P_{p}$ contains $v$ or increase $q$ by one and update $A[q]$, $S[q],I[v]$ in
$O(1)$ time. If $v\in V(h^{1})$, we also update $L$ if no occurrence of $v$
has been found in $P_{p}$, as follows. We find the first $L[i]$ with
$L[i]\geq\ell$ (via binary search) and set $L[i]:=v$. Updating the first
occurrence of a vertex from $V(h^{2})$ is trivial. It is easy to check that
this update process is correct and all the invariants are satisfied. Moreover,
it takes $O(\log{n})$ time, and involves updating $O(1)$ values in the worst
case. As a result, after descending down the tree recursively, we can
efficiently revert all the updates to $\mathcal{D}$ in $O(1)$ time so that
after the processing of a vertex $v_{j}$ ends, $\mathcal{D}$ stores $P_{p}$
again.

To find the subpath $s_{v}\to t_{v}$ of $P_{v}$, it is enough to binary search
for the latest position in $L$ that is smaller than $I[t_{v}]$. Note that this
only happens if $v\in V(h^{2})$, so $t_{v}$ is well-defined here, and the
requested position can be found since $L[1]=1$. The crossing number of the
$P^{*}_{v_{j}}=s_{v}\to t_{v}$ can be read from the array $S$.

We conclude that finding the required endpoints and crossing numbers of
$P_{v_{j}}^{*}$ for all $v_{j}$ can be done using additional
$\widetilde{O}(|T|)=\widetilde{O}(|Z^{\prime}|)=\widetilde{O}(|H|^{2})$
preprocessing time, as desired. ∎

Equipped with Lemmas 6.15 and 6.16, obtaining the closest pair and near
neighbor data structures for the subgraph of $D(H,x^{*},y^{*})$ encoding the
distance between $V(h^{1})$ and $V(h^{2})$ is relatively easy. First, during
preprocessing, we compute the data structure of Lemma 6.16. Given some
$\lambda$, in $\widetilde{O}(1)$ time we can find such $s\in V(h^{1})$, $t\in
V(h^{2})$ that some simple shortest $s\to t$ path $P$ in
$G^{*}_{\lambda}[H](x^{*},y^{*})$ has crossing number $k$, and
$V(P)\cap(V(h^{1})\cup V(h^{2}))=\\{s,t\\}$. By Lemma 6.15, for every
$(u^{\prime},v^{\prime})\in V(h^{1})\times V(h^{2})$, some shortest
$u^{\prime}\to v^{\prime}$ path in $G^{*}_{\lambda}[H](x^{*},y^{*})$ has
crossing number between $k-4$ and $k+4$.

Similarly as in Section 6.6.1, we consider an auxiliary graph

$D_{h^{1},h^{2}}=\left(V(h^{1})\cup
V(h^{2}),\bigcup_{j\in[k-4,k+4]}E_{h^{1},h^{2},j}\right),$

where each $E_{h^{1},h^{2},j}$ contains, for each $(u,v)\in V(h^{1})\times
V(h^{2})$, an edge $uv$ with weight
$\delta_{Z^{\prime}}(u_{0},v_{j})+j\cdot\lambda$.

Analogously as in Lemma 6.12, from the definition of $k$, one can prove that
for all ${(u,v)\in V(h^{1})\times V(h^{2})}$,
$\delta_{G^{*}_{\lambda}[H](x^{*},y^{*})}(u,v)=\delta_{D_{h^{1},h^{2}}}(u,v)$.
Finally, observe that the proof of Lemma 6.14 is valid not only for the graphs
$D_{h}[E_{h,j}]$ from Section 6.6.1, but also for each of the graphs
$D_{h^{1},h^{2}}[E_{h^{1},h^{2},j}]$. Indeed, there, the goal was to decompose
distances between the distinct faces $h_{0}$ and $h_{j}$ of $Z^{\prime}$. The
proof goes through without any changes if we replace $h_{0}$ with $h^{1}_{0}$,
and $h_{j}$ with $h^{2}_{j}$. Consequently, we obtain data structures with
$T_{\mathrm{cp}}(D_{h^{1},h^{2}}[E_{h^{1},h^{2},j}]),T_{\mathrm{nn}}(D_{h^{1},h^{2}}[E_{h^{1},h^{2},j}])\in\widetilde{O}(|V(h^{1})|+|V(h^{2})|)=\widetilde{O}(|\partial{H}|)$,
and $Q_{\mathrm{nn}}(D_{h^{1},h^{2}}[E_{h^{1},h^{2},j}])=\widetilde{O}(1)$. By
combining those for $O(1)$ required values $j\in[k-4,k+4]$ as previously, we
obtain that
$T_{\mathrm{cp}}(D_{h^{1},h^{2}}),T_{\mathrm{nn}}(D_{h^{1},h^{2}})\in\widetilde{O}(|V(h^{1})|+|V(h^{2})|)=\widetilde{O}(|\partial{H}|)$,
and $Q_{\mathrm{nn}}(D_{h^{1},h^{2}})=\widetilde{O}(1)$. This concludes the
proof of Lemma 6.8.

##  7 Flows, circulations, and negative cycle detection

Let $G_{0}=(V,E_{0})$ be the input directed graph. Let $n=|V|$ and
$m=|E_{0}|$. Define $G=(V,E)$ to be a _flow network_ , i.e., a multigraph such
that $E=E_{0}\cup E_{0}^{\mathrm{R}}$, $E_{0}\cap
E_{0}^{\mathrm{R}}=\emptyset$, where $E_{0}^{\mathrm{R}}$ is the set of
_reverse edges_. For any $uv=e\in E$, there is an edge $e^{\mathrm{R}}\in E$
such that $e^{\mathrm{R}}=vu$ and $(e^{\mathrm{R}})^{\mathrm{R}}=e$. We have
$e\in E_{0}$ iff $e^{\mathrm{R}}\in E_{0}^{\mathrm{R}}$.

Let $u:E_{0}\to\mathbb{Z}_{+}\cup\\{\infty\\}$ be an integral _capacity
function_. A _flow_ is a function $f:E\to\mathbb{R}$ such that for any $e\in
E$ $f(e)=-f(e^{\mathrm{R}})$ and for each $e\in E_{0}$, $0\leq f(e)\leq u(e)$.
These conditions imply that for $e\in E_{0}$, $-u(e)\leq f(e^{\mathrm{R}})\leq
0$. We extend the function $u$ to $E$ by setting $u(e^{\mathrm{R}})=0$ for all
$e\in E_{0}$. Then, for all edges $e\in E$ we have $-u(e^{\mathrm{R}})\leq
f(e)\leq u(e)$.

The _excess_ $\mathrm{exc}_{f}(v)$ of a vertex $v\in V$ is defined as
$\sum_{uv=e\in E}f(e)$. Due to anti-symmetry of $f$, $\mathrm{exc}_{f}(v)$ is
equal to the amount of flow going into $v$ by the edges of $E_{0}$ minus the
amount of flow going out of $v$ by the edges of $E_{0}$. The vertex $v\in V$
is called an _excess vertex_ if $\mathrm{exc}_{f}(v)>0$ and a _deficit vertex_
if $\mathrm{exc}_{f}(v)<0$. Let $X$ be the set of excess vertices of $G$ and
let $D$ be the set of deficit vertices. Define the _total excess_ $\Psi_{f}$
as the sum of excesses of the excess vertices, i.e., $\Psi_{f}=\sum_{v\in
X}\mathrm{exc}_{f}(v)=\sum_{v\in D}-\mathrm{exc}_{f}(v).$

A flow $f$ is called a _circulation_ if there are no excess vertices, or
equivalently, $\Psi_{f}=0$.

Let $c:E_{0}\to\mathbb{R}$ be the input _cost_ function. We extend $c$ to $E$
by setting $c(e^{\mathrm{R}})=-c(e)$ for all $e\in E_{0}$. The _cost_ $c(f)$
of a flow $f$ is defined as $\frac{1}{2}\sum_{e\in E}f(e)c(e)=\sum_{e\in
E_{0}}f(e)c(e)$.

_To send a unit of flow_ through $e\in E$ means to increase $f(e)$ by $1$ and
simultaneously decrease $f(e^{\mathrm{R}})$ by $1$. By sending a unit of flow
through $e$ we increase the cost of flow by $c(e)$. _To send a unit of flow
through a path $P$_ means to send a unit of flow through each edge of $P$. In
this case we also say that we _augment flow $f$ along path $P$_.

The _residual network_ $G_{f}$ of $f$ is defined as $(V,E_{f})$, where
$E_{f}=\\{e\in E:f(e)<u(e)\\}$. The capacity of an edge $e\in E_{f}$ in the
residual network $G_{f}$ is defined as $u(e)-f(e)$.

For any $v\in V$, let us define:

$\lambda_{v}=\min\left(\sum_{uv=e\in E}u(e),\sum_{vw=e\in E}u(e)\right).$

For example, if $G$ is a unit-capacitated network, then $\lambda_{v}$ equals
the minimum of the indegree and the outdegree of $v$ in the underlying network
$G_{0}$. Let us also put

$\Lambda:=\sum_{v\in V}\lambda_{v}.$

In the following we will assume that $\Lambda\geq n$, as vertices with
$\lambda_{v}=0$ are of no use in the minimum-cost circulation problem.

Moreover, we will assume that $\Lambda$ is finite. Observe that finite
$\Lambda$ implies that any circulation has finite flow values. As a result,
the cost of a minimum-cost circulation is finite as well.

Let us partition $E_{0}$ into $E_{\mathrm{fin}}\cup E_{\infty}$ so that for
all $e\in E_{\infty}$, $u(e)=\infty$, and $E_{\mathrm{fin}}=E_{0}\setminus
E_{\infty}$. Let us put $G_{\infty}:=G\setminus E_{\mathrm{fin}}$ and
$m_{\mathrm{fin}}=|E_{\mathrm{fin}}|$. Let $C=\max(2,\max\\{-c(e):e\in
E_{0}\\})$.

In Section 8 we prove:

######  Theorem 7.1.

Suppose closest pair and near neighbor data structures have been preprocessed
for $G_{\infty}$. Let $f^{*}$ be a min-cost circulation in $G$. Then, an
_integral_ circulation $f_{\delta}$ satisfying

$c(f^{*})\leq c(f_{\delta})\leq c(f^{*})+\delta$

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).$

Within the same bounds, a price function $\pi$ satisfying
$c_{\pi}(e)\geq-\delta/\Lambda$ for all $e\in E(G_{f_{\delta}})$ is produced.

Before proving Theorem 7.1, let us deduce Theorem 3.6 from it. See 3.6

###### Proof.

We use a reduction similar to that of [Gab85, GT89]. Consider a flow network
$G^{\prime}$ obtained from $G$ by converting weights to costs, setting all
capacities to $\infty$, vertex splitting, and subsequently adding, for each
$u\in V$, an edge $u_{\textrm{in}}u_{\textrm{out}}$ of capacity $1$ and cost
$0$. Note that for $G^{\prime}$, $\Lambda=n$ holds.

Observe that the subgraph of infinite-capacity edges $G_{\infty}$ of
$G^{\prime}$ satisfies
$T_{\mathrm{cp}}(G_{\infty})=\widetilde{O}(T_{\mathrm{cp}}(G))$ by Lemma 4.6.
Moreover, we have $T_{\mathrm{nn}}(G_{\infty})=O(T_{\mathrm{nn}}(G))$ and
$Q_{\mathrm{nn}}(G_{\infty})=O(Q_{\mathrm{nn}}(G))$ by Observation 4.5.

Clearly, $G$ has a negative cycle if and only if $G^{\prime}$ has a negative
cycle. Let us now argue that $G^{\prime}$ has a negative cycle if and only if
the minimum-cost circulation $f^{*}$ in $G^{\prime}$ has negative cost.
Observe that a zero circulation (i.e., where the flow on each edge is $0$) is
a valid circulation of cost $0$. As a result, we have $c(f^{*})\leq 0$.

Suppose $G^{\prime}$ has a negative cycle. Then, by sending a unit of flow
through that cycle, we obtain a valid circulation of negative cost, i.e., we
conclude $c(f^{*})<0$.

Now suppose that $c(f^{*})<0$. It is well-known (see e.g. [AMO93]) that any
circulation – in particular $f^{*}$ – can be decomposed into cycles in
$G^{\prime}$ of positive flow. Since the sum of costs of these cycles is
negative, at least one of them has to have a negative cost.

Since the costs and capacities are integral or infinite, and $\Lambda$ is
finite for $G^{\prime}$, $c(f^{*})$ is integral. As a result, $c(f^{*})<0$
implies $c(f^{*})\leq-1$. Hence, if we invoke Theorem 7.1 to compute an
integer circulation $f_{\delta}$ with $\delta\leq\frac{1}{2}$, to be set
later, then $c(f_{\delta})\leq-1+\delta\leq-\frac{1}{2}<0$. We conclude that
$c(f^{*})<0$ implies $c(f_{\delta})<0$. Since $f^{*}$ is an optimal
circulation, $c(f_{\delta})<0$ trivially implies $c(f^{*})<0$. As a result,
$G$ has a negative cycle iff $c(f_{\delta})<0$. For the graph $G^{\prime}$ we
have $\Lambda=n$, and $G^{\prime}$ has $O(n)$ finite-capacity edges, so
computing $f_{\delta}$ takes

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

time by Theorem 7.1. Note that if one decomposes the circulation $f_{\delta}$
into cycles of positive flow, at least one of them will be negative. Such a
cycle in $G^{\prime}$ can be easily converted to a simple negative cycle in
$G$.

However, if $c(f^{*})=0$, i.e., $G$ has no negative cycle, we still need to
produce a feasible price function of $G$. To this end we need the feasible
price function $\pi$ produced by Theorem 7.1 when computing $f_{\delta}$. Note
that $c(f_{\delta})\leq\delta\leq\frac{1}{2}$ implies $c(f_{\delta})=0$ by
integrality of $f_{\delta}$.

Since $f_{\delta}$ is a circulation, it can be decomposed into a collection of
$j\geq 0$ simple cycles $C_{1},\ldots,C_{j}$, of positive flow (in fact, a
unit flow). In fact, each of these cycles has to have $0$ cost, as otherwise
at least one of them would have negative cost. Consider one of the cycles
$C_{i}$. Since $C_{i}$ is a simple cycle, it has at most $2n$ edges (recall
that vertex splitting doubles the number of vertices). Consider any edge
$uv\in C_{i}$. Clearly, since $f_{\delta}(uv)=1$, $vu\in
G^{\prime}_{f_{\delta}}$ and thus

$-c(uv)-\pi(v)+\pi(u)=c(vu)-\pi(v)+\pi(u)=c_{\pi}(vu)\geq-\frac{\delta}{n}$

by Theorem 7.1. Equivalently, $c(uv)-\pi(u)+\pi(v)\leq\frac{\delta}{n}$.
Suppose we have $c(xy)-\pi(x)+\pi(y)<-2\delta$ for some edge $xy\in C_{i}$.
Then the sum

$\sum_{uv\in C_{i}}(c(uv)-\pi(u)+\pi(v))$

has terms no more than $\frac{\delta}{n}$, and at least one term less than
$-2\delta$, so it is less than ${\frac{(2n-1)\delta}{n}-2\delta<0}$. But since
$C_{i}$ is a cycle, the prices $\pi(\cdot)$ in the above sum cancel out, so we
actually obtain $\sum_{uv\in C_{i}}c(uv)<0$ which contradicts that $C_{i}$ has
zero cost. Therefore, we conclude that for any edge $uv\in C_{i}$ we have:

$c(uv)-\pi(u)+\pi(v)\geq-2\delta.$ (8)

Suppose that for some $v$ we have
$f_{\delta}(v_{\textrm{in}}v_{\textrm{out}})=1$. Then
$v_{\textrm{in}}v_{\textrm{out}}$ lies on some cycle $C_{i}$ of the
decomposition and thus by (8) we have:

$-\pi(v_{\textrm{in}})+\pi(v_{\textrm{out}})=c(v_{\textrm{in}}v_{\textrm{out}})-\pi(v_{\textrm{in}})+\pi(v_{\textrm{out}})\geq-2\delta.$

As a result $\pi(v_{\textrm{in}})\leq\pi(v_{\textrm{out}})+2\delta$ in this
case.

If $f_{\delta}(v_{\textrm{in}}v_{\textrm{out}})=0$, then
$v_{\textrm{in}}v_{\textrm{out}}\in G_{f_{\delta}}^{\prime}$, so we can also
conclude $\pi(v_{\textrm{in}})\leq\pi(v_{\textrm{out}})+2\delta$ from
$c(v_{\textrm{in}}v_{\textrm{out}})-\pi(v_{\textrm{in}})+\pi(v_{\textrm{out}})\geq-\delta/n$.

Now consider some original edge $uv$ of $G$. There are two cases. If
$f_{\delta}(u_{\textrm{out}}v_{\textrm{in}})=1$, then
$u_{\textrm{out}}v_{\textrm{in}}$ lies on some cycle $C_{i}$ and therefore by
(8) we know that

$c(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{out}})+\pi(v_{\textrm{in}})\geq-2\delta$

Observe that in this case the edge $u_{\textrm{in}}u_{\textrm{out}}$ also
necessarily lies on $C_{i}$, so again by (8) we have
$-\pi(u_{\textrm{out}})-2\delta\leq-\pi(u_{\textrm{in}})$. From that, we
conclude:

$w_{G}(uv)-\pi(u_{\textrm{in}})+\pi(v_{\textrm{in}})=c(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{in}})+\pi(v_{\textrm{in}})\geq
c(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{out}})+\pi(v_{\textrm{in}})-2\delta\geq-4\delta.$

Now assume $f_{\delta}(u_{\textrm{out}}v_{\textrm{in}})=0$. Then
$u_{\textrm{out}}v_{\textrm{in}}\in G_{f_{\delta}}^{\prime}$ and by
$\pi(u_{\textrm{out}})\geq\pi(u_{\textrm{in}})-2\delta$ we have:

$w_{G}(uv)-\pi(u_{\textrm{in}})+\pi(v_{\textrm{in}})\geq
c(u_{\textrm{out}}v_{\textrm{in}})-\pi(u_{\textrm{out}})+\pi(v_{\textrm{in}})-2\delta\geq-\frac{\delta}{n}-2\delta\geq-4\delta.$

We conclude that a price function $p(v):=\pi(v_{\textrm{in}})$ satisfies
$w_{G}(uv)-p(u)+p(v)\geq-4\delta$ for all original edges $uv\in E(G)$.

Finally, consider the graph $G^{\prime\prime}$ obtained from $G$ by adding,
for an arbitrarily chosen vertex $s\in V(G)$, the $n-1$ edges $st$, for all
$t\in V\setminus\\{s\\}$, of weight $\lceil\max(nC,p(s)-p(t))\rceil$. We have
$T_{\mathrm{cp}}(G^{\prime\prime})=\widetilde{O}(T_{\mathrm{cp}}(G))$ by Fact
3.3 and Lemma 3.5. Now, let $G^{+}$ be obtained from $G^{\prime\prime}$ by
increasing all the edge weights by $4\delta$. Note that $p$ is a feasible
price function of $G^{+}$. As a result, by an easy modification of Dijkstra‘s
algorithm implementation behind Lemma 3.4 (it is enough to add $4\delta$ to
the right-hand side of (1)), one can compute distances
$\delta_{G^{+}}(s,\cdot)$ in
$\widetilde{O}(T_{\mathrm{cp}}(G^{\prime\prime}))=\widetilde{O}(T_{\mathrm{cp}}(G))$
time. Since $G^{+}$ was obtained by increasing edge weights of
$G^{\prime\prime}$ by $4\delta$, for any $t\in V(G)$ we have:

$\delta_{G^{\prime\prime}}(s,t)\leq\delta_{G^{+}}(s,t)<\delta_{G^{\prime\prime}}(s,t)+4n\delta.$

In particular, if $\delta=\frac{1}{4n}$, then we have
$\delta_{G^{\prime\prime}}(s,t)\leq\delta_{G^{+}}(s,t)<\delta_{G^{\prime\prime}}(s,t)+1$.
But since $G$ has integral weights, all $\delta_{G^{\prime\prime}}(s,t)$ are
integral. As a result, for $\delta=\frac{1}{4n}$ we can obtain
$\delta_{G^{\prime\prime}}(s,\cdot)$ by simply rounding the respective
distances in $G^{+}$ down to the nearest integers. To finish the proof, recall
that $-\delta_{G^{\prime\prime}}(s,\cdot)$ is a feasible price function of
$G^{\prime\prime}$ (and thus of $G\subseteq G^{\prime\prime}$) if
$G^{\prime\prime}$ has no negative cycles.

We conclude that the running time of the algorithm is indeed

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

##  8 Min-cost circulation algorithm

In this section we prove Theorem 7.1. We first need the following technical
lemma.

######  Lemma 8.1.

Let $f$ be any flow. For any $v\in V$, the sum of $|f(e)|$ over incoming edges
$e=zv$ (or outgoing edges $e=vz$) is at most
$|\mathrm{exc}_{f}(v)|+2\lambda_{v}$.

###### Proof.

For each $v$, let $\lambda^{\textrm{in}}_{v}=\sum_{xv=e\in E}u(e)$, and
$\lambda^{\textrm{out}}_{v}=\sum_{vy=e\in E}u(e)$. Recall that
$\lambda_{v}=\min(\lambda^{\textrm{in}}_{v},\lambda^{\textrm{out}}_{v})$.

Let $p_{v}=\sum_{zv=e\in E}|f(e)|$. We have

$\mathrm{exc}_{f}(v)=\sum_{\begin{subarray}{c}e=zv\\\ f(e)\neq
0\end{subarray}}f(e)=\ \sum_{\begin{subarray}{c}e=zv\\\
f(e)>0\end{subarray}}|f(e)|-\sum_{\begin{subarray}{c}e=zv\\\
f(e)<0\end{subarray}}|f(e)|=p_{v}-2\cdot\sum_{\begin{subarray}{c}e=zv\\\
f(e)<0\end{subarray}}|f(e)|=-p_{v}+2\cdot\sum_{\begin{subarray}{c}e=zv\\\
f(e)>0\end{subarray}}|f(e)|,$

and thus

$\displaystyle p_{v}$
$\displaystyle=\mathrm{exc}_{f}(v)+2\cdot\sum_{\begin{subarray}{c}e=zv\\\
f(e)<0\end{subarray}}|f(e)|=\mathrm{exc}_{f}(v)+2\cdot\sum_{\begin{subarray}{c}e=vz\\\
f(e)>0\end{subarray}}f(e)\leq\mathrm{exc}_{f}(v)+2\lambda^{\textrm{out}}_{v}.$
$\displaystyle p_{v}$
$\displaystyle=-\mathrm{exc}_{f}(v)+2\cdot\sum_{\begin{subarray}{c}e=zv\\\
f(e)>0\end{subarray}}|f(e)|\leq-\mathrm{exc}_{f}(v)+2\lambda^{\textrm{in}}_{v}.$

Hence for any $v\in V$ we have:

$\displaystyle p_{v}$
$\displaystyle\leq\min(-\mathrm{exc}_{f}(v)+2\lambda^{\textrm{in}}_{v},\mathrm{exc}_{f}(v)+2\lambda^{\textrm{out}}_{v})$
$\displaystyle\leq\min(|\mathrm{exc}_{f}(v)|+2\lambda^{\textrm{in}}_{v},|\mathrm{exc}_{f}(v)|+2\lambda^{\textrm{out}}_{v})$
$\displaystyle=|\mathrm{exc}_{f}(v)|+2\lambda_{v}.$

The proof that the sum of $|f(e)|$ over edges $e=vz$ is at most
$|\mathrm{exc}_{f}(v)|+2\lambda_{v}$ is completely analogous. ∎

Since in circulations, all vertex excesses are zero, we obtain the following.

######  Corollary 8.2.

If $f$ is a circulation, then $\sum_{e\in E}|f(e)|\leq 2\Lambda$.

###  8.1 Scaling framework for minimum-cost circulation.

######  Fact 8.3 ([SB65]).

Let $f$ be a circulation. Then $c(f)$ is minimum iff $G_{f}$ has no negative
cycles.

It follows that a circulation $f$ is minimum if there exists a feasible price
function of the residual network $G_{f}$.

######  Definition 8.4 ([BT88, GT90, Tar85]).

A flow $f$ is $\epsilon$-optimal wrt. price function $p$ if for any $uv=e\in
E_{f}$, $c(e)-p(u)+p(v)\geq-\epsilon.$

The above notion of $\epsilon$-optimality allows us, in a sense, to measure
the optimality of a circulation: the smaller $\epsilon$, the closer to the
optimum a circulation $f$ is. In particular, we have the following:

######  Lemma 8.5.

Let $f^{*}$ be a min-cost circulation. Let $f$ be an $\epsilon$-optimal
circulation wrt $p$. Then:

$c(f)-c(f^{*})\leq 2\epsilon\cdot\Lambda.$

###### Proof.

We have

$c_{p}(f)-c_{p}(f^{*})=\frac{1}{2}\sum_{e\in E}(f(e)-f^{*}(e))c_{p}(e).$

If $f(e)>f^{*}(e)$, then $e^{\mathrm{R}}\in E_{f}$ and hence
$c_{p}(e^{\mathrm{R}})\geq-\epsilon$, and thus $c_{p}(e)\leq\epsilon$.
Otherwise, if $f(e)<f^{*}(e)$ then $e\in E_{f}$ and $c_{p}(e)\geq-\epsilon$.
In both cases
$(f(e)-f^{*}(e))c_{p}(e)\leq|f(e)-f^{*}(e)|\cdot\epsilon\leq(|f(e)|+|f^{*}(e)|)\cdot\epsilon$.
This ultimate inequality also holds if $f(e)=f^{*}(e)$. As a result, by Lemma
8.1, we have

$\displaystyle c_{p}(f)-c_{p}(f^{*})$
$\displaystyle\leq\frac{1}{2}\epsilon\cdot\left(\sum_{e\in E}|f(e)|+\sum_{e\in
E}|f^{*}(e)|\right)$
$\displaystyle\leq\frac{1}{2}\epsilon\cdot\left(\sum_{v\in V}\sum_{zv=e\in
E}|f(e)|+\sum_{v\in V}\sum_{zv=e\in E}|f^{*}(e)|\right)$
$\displaystyle\leq\frac{1}{2}\epsilon\cdot\left(\sum_{v\in
V}|\mathrm{exc}_{f}(v)|+|\mathrm{exc}_{f^{*}}(v)|+4\lambda_{v}\right).$

But for circulation all the excesses are zero, and thus we obtain
$c_{p}(f)-c_{p}(f^{*})\leq 2\epsilon\sum_{v\in
V}\lambda_{v}=2\epsilon\Lambda.$

Finally, observe that the price functions do not influence the costs of
circulations. As a result, $c(f)=c_{p}(f)$ and $c(f^{*})=c_{p}(f^{*})$ and
thus $c(f)-c(f^{*})\leq 2\epsilon\Lambda$. ∎

Recall that $C$ equals minus the most negative edge cost. Observe that a zero
circulation is $C$-optimal wrt. a zero price function. Suppose we have a
procedure $\textsc{Refine}(G,f_{0},p_{0},\epsilon)$ that, given an _integral_
circulation $f_{0}$ in $G$ that is $2\epsilon$-optimal wrt. $p_{0}$, computes
a pair $(f^{\prime},p^{\prime})$ such that $f^{\prime}$ is an _integral_
circulation in $G$, and it is $\epsilon$-optimal wrt. $p^{\prime}$. We use the
general _successive approximation_ framework, due to Goldberg and Tarjan
[GT90], as given in Algorithm 1. Therefore, if we implement Refine to run in
$T(n,m)$ time, by Lemma 8.5 we can compute a $\delta$-additive approximation
of the minimum cost circulation in $G$ in $O(T(n,m)\log{(C\Lambda/\delta)})$
time.

1:procedure MinimumCostCirculation($G$)

2: $f(e):=0$ for all $e\in G$

3: $p(v):=0$ for all $v\in V$

4: $\epsilon:=C/2$

5: while $\epsilon>\frac{\delta}{2\Lambda}$ do$\triangleright$ $f$ is
$2\epsilon$-optimal wrt. $p$

6: $(f,p):=\textsc{Refine}(G,f,p,\epsilon)$

7: $\epsilon:=\epsilon/2$

8: return $f$ $\triangleright$ $f$ is circulation
$\frac{\delta}{2\Lambda}$-optimal wrt. $p$, i.e., a $\delta$-additive
approximation

Algorithm 1 Scaling framework for min-cost circulation.

###  8.2 Refinement

We now describe our implementation of
$\textsc{Refine}(G,f_{0},p_{0},\epsilon)$. A significant part of the analysis
is based on the successive shortest paths-based unit-capacity min-cost flow
algorithm described in [KS19], and is also inspired by the analysis in
[GHKT17]; however, the details of the refinement procedure are different.

The first step is to adjust $p_{0}$ as follows:

  * •

for each $v\in V$ with
$\lambda^{\textrm{in}}_{v}\leq\lambda^{\textrm{out}}_{v}$, decrease $p_{0}(v)$
by $\epsilon$,

  * •

for each $v\in V$ with $\lambda^{\textrm{in}}_{v}>\lambda^{\textrm{out}}_{v}$,
increase $p_{0}(v)$ by $\epsilon$.

######  Lemma 8.6.

After the adjustment, $p_{0}$ satisfies the following:

  1. 1.

$f_{0}$ is $4\epsilon$-optimal wrt. $p_{0}$.

  2. 2.

The total capacity of edges $e\in G_{f_{0}}$ with $c_{p_{0}}(e)<0$ is no more
than $3\Lambda$.

###### Proof.

First, for each $uv=e\in G_{f_{0}}$, $c_{p_{0}}(e)$ can decrease by at most
$2\epsilon$, so item (1) follows by $2\epsilon$-optimality of the initial
price function $p_{0}$.

Now consider item (2). If $e\in E_{0}$, then the capacity of $e^{\mathrm{R}}$
in $G_{f_{0}}$ is
$u(e^{\mathrm{R}})-f_{0}(e^{\mathrm{R}})=-f_{0}(e^{\mathrm{R}})=f_{0}(e)=|f_{0}(e)|$.
As a result, the total capacity of the edges from $E_{0}^{\mathrm{R}}\cap
E_{f_{0}}$ is no more than $\sum_{e\in E_{0}}|f_{0}(e)|\leq\sum_{e\in
E}|f_{0}(e)|\leq 2\Lambda$, by Corollary 8.2.

Now suppose $e\in E_{0}$. An edge $uv=e\in G_{f_{0}}$ can only satisfy
$c_{p_{0}}(e)<0$ after the adjustment if either $p_{0}(u)$ was increased or
$p_{0}(v)$ was decreased, since otherwise $c_{p_{0}}(e)$ grows by $2\epsilon$.

The capacity of $e$ in $G_{f_{0}}$ is at most $u(e)$. If $p_{0}(u)$ was
increased, then, $\lambda_{u}=\lambda^{\textrm{out}}_{u}$, so we can charge
the capacity of $e$ to $\lambda_{u}$. If $p_{0}(v)$ was decreased, then
$\lambda_{v}=\lambda^{\textrm{in}}_{v}$, so we can charge the capacity of $e$
to $\lambda_{v}$. Observe that this way, the total charge is $\sum_{v\in
V}\lambda_{v}=\Lambda$, so the total capacity of edges $E_{0}\cap E_{f_{0}}$
in $G_{f_{0}}$ is $\leq\Lambda$. Finally, the total capacity of $(E_{0}\cup
E_{0}^{\mathrm{R}})\cap E_{f_{0}}=E_{f_{0}}$ is at most $3\Lambda$. ∎

The second step is setting $c(e):=c(e)-p_{0}(u)+p_{0}(v)$ for all $e\in E$ for
further convenience. After the refinement completes, i.e., when we have a
circulation $f^{\prime}$ that is $\epsilon$-optimal wrt. some $p^{\prime}$,
(assuming costs reduced with $p_{0}$, as above), we will return
$(f^{\prime},p^{\prime}+p_{0})$ instead. Therefore, from now on we assume that
$c(e)\geq-4\epsilon$ for all $e\in E_{f_{0}}$.

Let $f_{1}$ be the flow initially obtained from $f_{0}$ by sending a unit of
flow through each edge $e\in E_{f_{0}}$ such that $c(e)<0$. Note that $f_{1}$
is $\epsilon$-optimal (in fact $0$-optimal), but it need not be a circulation.
Note that by Lemma 8.6, the total excess $\Psi_{f_{1}}$ after this step is
integral and bounded by $3\Lambda$.

We denote by $f$ the _current flow_ , initialized with $f_{1}$, which we will
gradually transform into a circulation. Recall that $X$ is the set of excess
vertices of $G$ and $D$ is the set of deficit vertices (wrt. to the current
flow $f$). A well-known method of finding the min-cost circulation exactly
[BG60, Iri60, Jew62] is to repeatedly send flow through shortest $X\to D$
paths in $G_{f}$. The sets $X$ and $D$ only shrink in time. However, doing
this on $G_{f}$ exactly would be too costly. Instead, we will gradually
convert $f$ into a circulation, by sending flow from vertices of $X$ to
vertices of $D$ but only using approximate (in a sense) shortest paths.

For any $e\in E$, let us set

$c^{\prime}(e)=\begin{cases}c(e)&\text{ if }e\in E_{0},\\\
c(e)+\epsilon&\text{ if }e\in E_{0}^{\mathrm{R}}.\end{cases}$

Note that for any $e\in E$ we have
$c^{\prime}(e)+c^{\prime}(e^{\mathrm{R}})=c(e)+c(e^{\mathrm{R}})+\epsilon=\epsilon$.

We define $G_{f}^{\prime}$ to be the ’’approximate‘‘ graph $G_{f}$ with the
costs given by $c^{\prime}$ instead of $c$. Observe that $c(e)\geq
c^{\prime}(e)-\epsilon$, so if $p$ is a feasible price function of
$G_{f}^{\prime}$, then $f$ is $\epsilon$-optimal wrt. $p$ (in $G$).

For convenience, let us also define an extended version $G_{f}^{\prime\prime}$
of $G_{f}^{\prime}$ to be $G_{f}^{\prime}$ with two additional vertices $s$ (a
super-excess-vertex) and $t$ (a super-deficit-vertex) added.

We also add to $G_{f}^{\prime\prime}$ the following _auxiliary_ edges
$E_{\mathrm{aux}}$:

  1. 1.

an edge $sx$ with $c^{\prime}(sx)=0$ and capacity $\mathrm{exc}_{f_{1}}(x)$
for all $x\in X$.

  2. 2.

an edge $dt$ with $c^{\prime}(dt)=$ and capacity $-\mathrm{exc}_{f_{1}}(d)$
for all $d\in D$.

Clearly, $\delta_{G_{f}^{\prime\prime}}(s,t)=\delta_{G_{f}^{\prime}}(X,D)$.

Set $M$ to be larger than the cost of any simple path in $G_{f}^{\prime}$,
e.g., $M=n\cdot(C+2\max_{v\in V}|p_{0}(v)|+\epsilon)$. Let $A$ be a graph on
$V$ with an edge $sv$ with $c^{\prime}(sv)=M$ for all $v\in V$.

Now we describe the _main loop_ of the refinement procedure. Start with
$f=f_{1}$ and zero price function $p$ on $G_{f}^{\prime\prime}$. Maintain an
invariant the $p$ is a feasible price function on $G_{f}^{\prime\prime}$.
While $X\neq\emptyset$:

  1. (1)

Compute distances $d(v)=\delta_{G_{f}^{\prime\prime}\cup A}(s,v)$ from $s$ in
$G_{f}^{\prime\prime}\cup A$ with the help of $p$.

  2. (2)

Set $p(v):=-d(v)$ for all $v\in V(G_{f}^{\prime\prime})$.

  3. (3)

Repeatedly send unit flow through $X\to D$ paths $P\subseteq G_{f}$ consisting
solely of _nearly tight_ edges $uv=e$ satisfying
$c^{\prime}(e)-p(u)+p(v)<\epsilon/2$, until $\Psi_{f}=0$ or there are no such
paths left.

Whenever $X\neq\emptyset$, let us denote by
$\Delta=\delta_{G_{f}^{\prime\prime}}(s,t)=\delta_{G_{f}}(X,D)$.

We now state some crucial properties of the refinement procedure that hold
regardless of how the steps (1) and (3) are implemented. The proofs of Lemmas
8.7 and 8.10 are deferred to Section 8.5.

######  Lemma 8.7.

If $X\neq\emptyset$, then there exists an $X\to D$ path in $G_{f}$ (or equiv.,
in $G_{f}^{\prime}$), i.e., $\Delta<\infty$.

Equivalently, if $X\neq\emptyset$, an $s\to t$ path exists in
$G_{f}^{\prime\prime}$.

######  Lemma 8.8.

At all times, $p$ remains a feasible price function of $G_{f}^{\prime\prime}$.

###### Proof.

This is clearly satisfied at the very beginning. If $p$ is changed to
$-\delta_{G_{f}^{\prime\prime}\cup A}(s,\cdot)$ in step (2), then it is a
feasible price function of $G_{f}^{\prime\prime}$ since $G_{f}^{\prime\prime}$
has no negative cycles (by the feasibility of $p$ before step (2)), and minus
distance from $s$ function is a feasible price function.

Now let us argue that $p$ remains a feasible price function after sending flow
through some path $P$ in $G_{f}$ consisting of nearly tight edges. Let $f_{2}$
be the flow $f$ after augmenting along $P$. We clearly have
$c^{\prime}_{p}(e)\geq 0$ for all edges in $E(G_{f}^{\prime\prime})\cap
E(G_{f_{2}}^{\prime\prime})$. Each edge $uv=e\in
E(G_{f_{2}}^{\prime\prime})\setminus E(G_{f}^{\prime})$ is such that $e\notin
E_{\mathrm{aux}}$ and $e^{\mathrm{R}}=vu$ belongs to the path $P$. As a
result, we have

$c^{\prime}(e)-p(u)+p(v)=(-c^{\prime}(e^{\mathrm{R}})+\epsilon)-p(u)+p(v)=\epsilon-(c^{\prime}(e^{\mathrm{R}})-p(v)+p(u))>\epsilon-\epsilon/2=\epsilon/2,$

so indeed $p$ is a feasible price function after augmenting the flow. ∎

######  Lemma 8.9.

$\Delta$ increases by at least $\epsilon/2$ as a result of completing step (3)
of the main loop.

###### Proof.

Note that immediately before some fixed step (3), $G_{f}^{\prime\prime}$ has
no negative cycles by Lemma 8.8, so $p(s)$ is reset to $0$ and $p(t)$ is reset
to $-\Delta$. Suppose $X\neq\emptyset$ immediately after that step (3) and let
$f_{2}$ be the flow at that time. Let
$\Delta_{2}=\delta_{G_{f_{2}}^{\prime}}(X,D)=\delta_{G_{f_{2}}^{\prime\prime}}(s,t)$
and consider some path $s\to t=P=e_{1}\ldots e_{k}$ in
$G_{f_{2}}^{\prime\prime}$ with minimum cost $\Delta_{2}$. We have:

$\Delta_{2}=\delta_{G_{f_{2}}^{\prime\prime}}(s,t)=\sum_{i=1}^{k}c^{\prime}(e_{i})=p(s)-p(t)+\sum_{i=1}^{k}c^{\prime}_{p}(e_{i})=\Delta+\sum_{i=1}^{k}c^{\prime}_{p}(e_{i}).$

Since $p$ is a feasible price function of $G_{f_{2}}^{\prime\prime}$, every
term $c_{p}^{\prime}(e_{i})$ in the sum above is non-negative. However, the
step (3) has completed, so for at least one edge $e_{j}$ we have
$c_{p}^{\prime}(e_{j})\geq\epsilon/2$, as otherwise more flow could be sent
through $P$ in that step (3). As a result,
$\sum_{i=1}^{k}c^{\prime}_{p}(e_{i})\geq\epsilon/2$ and thus
$\Delta_{2}\geq\Delta+\epsilon/2$, as desired. ∎

######  Lemma 8.10.

At all times, we have $\Psi_{f}\cdot\Delta\leq 48\epsilon\cdot\Lambda$.

######  Lemma 8.11.

The main loop is performed $O(\sqrt{\Lambda})$ times.

###### Proof.

Since $G_{f_{1}}$ has only non-negative-cost edges, $\Delta$ is initially non-
negative. By Lemma 8.7, $\Delta$ remains finite as long as $\Psi_{f}>0$. Note
that $\Delta$ can only change when $f$ evolves, i.e., in step (3). By Lemma
8.9, it grows by at least $\epsilon/2$ after each iteration of the main loop.
Thus, there can be no more than $O(\sqrt{\Lambda})$ augmentations until
$\Delta\geq\epsilon\cdot\sqrt{\Lambda}$. But then, by Lemma 8.10, we have
$\Psi_{f}\leq 48\epsilon\Lambda/\Delta\leq 48\sqrt{\Lambda}$. Each iteration
of step (3) decreases the total excess by at least one, so there can be at
most $O(\sqrt{\Lambda})$ additional iterations of that step, and thus also of
the main loop. ∎

###  8.3 Computing distances

In this section we discuss how step (1) is implemented. Note that
$G_{\infty}\subseteq G_{f}^{\prime\prime}$ at all times, since for all $e\in
E_{0}\cap E_{\infty}$ we have $c^{\prime}(e)=c(e)$ and we always have
$f(e)<u(e)=\infty$.

######  Lemma 8.12.

The number of edges in $E(G_{f}^{\prime\prime})\setminus E_{\infty}$ is
$O(m_{\mathrm{fin}}+\Lambda)$.

###### Proof.

Consider any edge $e\in E(G_{f}^{\prime\prime})\setminus E_{\infty}$. Then we
either have (1) $e\in E_{\mathrm{fin}}\cup E_{\mathrm{fin}}^{\mathrm{R}}$ or
(2) $e\in E_{\infty}^{\mathrm{R}}$, or (3) $e\in E_{\mathrm{aux}}$. There are
clearly only $O(m_{\mathrm{fin}})$ edges of the first kind. On the other hand,
if $e\in E_{\infty}^{\mathrm{R}}$, then $f(e^{\mathrm{R}})\geq 1$. But by
Lemma 8.1, the number of such edges is at most $\sum_{e\in
E_{\infty}^{\mathrm{R}}}f(e^{\mathrm{R}})\leq\sum_{e\in E}|f(e)|\leq
2(\Psi_{f}+\Lambda)$. However, as argued before, $\Psi_{f}\leq\Psi_{f_{1}}\leq
3\Lambda$. As a result, the number of edges of type (2) is no more than
$8\Lambda$. Finally, there are clearly $O(n)=O(\Lambda)$ edges of the third
type. ∎

From the above we conclude that $G_{f}^{\prime\prime}$ can be seen as
$G_{\infty}$ augmented with $O(m_{\mathrm{fin}}+\Lambda)$ edges.

Note that by combining the closest pair data structure for $G_{\infty}$ that
we already have preprocessed, with $O(m_{\mathrm{fin}}+n+\Lambda)$ single-edge
data structures of Fact 3.3, by Lemma 3.5 we obtain that
$T_{\mathrm{cp}}(G_{f}^{\prime\prime})=\widetilde{O}(T_{\mathrm{cp}}(G_{\infty})+m_{\mathrm{fin}}+\Lambda)$
without any additional preprocessing.

Since $p$ is a feasible price function of $G_{f}^{\prime\prime}$, by using
Dijkstra‘s algorithm implementation of Lemma 3.4, we obtain:

######  Lemma 8.13.

Step (1) of the main loop takes
$\widetilde{O}(T_{\mathrm{cp}}(G_{\infty})+\Lambda+m_{\mathrm{fin}})$ time.

###  8.4 Sending flow efficiently

In this section we discuss how step (3) is implemented.

######  Observation 8.14.

During step (3), nearly tight edges are only deleted from
$G_{f}^{\prime\prime}$, and never added. Moreover, only the edges
$E(G_{f}^{\prime\prime})\setminus E_{\infty}$ can be deleted.

###### Proof.

An edge $e=uv$ can only be added to $G_{f}^{\prime}$ if flow is sent through
$e^{\mathrm{R}}$. But then $e^{\mathrm{R}}$ has to be nearly tight, so
$c^{\prime}(e^{\mathrm{R}})-p(v)+p(u)<\epsilon/2$. We get:

$c^{\prime}(e)-p(u)+p(v)=c^{\prime}(e)+c^{\prime}(e^{\mathrm{R}})-(c^{\prime}(e^{\mathrm{R}})-p(v)+p(u))>c^{\prime}(e)+c^{\prime}(e^{\mathrm{R}})-\epsilon/2=\epsilon/2,$

so $e$ is not nearly tight.

An edge $e$ can only be deleted from $E_{f}$ if $f(e)=u(e)$, but this never
happens for the edges $e\in E_{\infty}$ since $\sum_{e\in E}|f(e)|$ is
$O(\Lambda)$. ∎

Denote by $H$ the subgraph of $G_{f}^{\prime\prime}$ consisting of nearly
tight edges. By the above observation, during step (3) $H$ is decremental in
time, and the edges of $E(H)\cap E_{\infty}$ are never deleted from $H$.

We will actually not only send flow through paths, but also through cycles. It
is only important that we do not introduce more excess, which sending through
cycles satisfies. Note that our analysis up to this point did not really
depend on the fact that the flow is pushed through a path. We only used the
fact that flow is pushed through nearly-tight edges.

In order to efficiently find paths/cycles, we will reuse some of the
information from previous searches. We will maintain a set $S$ of vertices
$v\in V(G_{f}^{\prime\prime})$ for which we are still unsure whether no more
$v\to t$ paths consisting solely of nearly-tight edges exist in
$G_{f}^{\prime\prime}$. Initially, $S=V(G_{f}^{\prime\prime})$. The set $S$
will only shrink. Moreover, for each vertex $v\in V(G_{f}^{\prime\prime})$ we
will maintain a set $F_{v}=\\{vz=e\in E(H)\setminus E_{\infty}:z\in S\\}$.

By Lemma 8.12, the initial size of sets $F_{v}$ is
$O(m_{\mathrm{fin}}+\Lambda)$ and these sets can be easily initialized within
this time bound. Moreover, since both sets $S$ and $E(H)\setminus E_{\infty}$
only shrink, so do the sets $F_{v}$. Observe that the sets $F_{v}$ can be also
easily maintained subject to deletions issued to the sets $S$ and
$E(H)\setminus E_{\infty}$ in $O(m_{\mathrm{fin}}+\Lambda)$ total time.

Finally, whenever we enter step (3), we initialize a near neighbor data
structure for $G_{\infty}$ with price function $p$ and thresholds
$\tau(u)=p(u)+\epsilon/2$, so that any returned edge $e=uv$ satisfies
$w(e)+p(v)<\tau(u)=p(u)+\epsilon/2$, that is $w(e)-p(u)+p(v)<\epsilon/2$. The
set $T$ of that data structure is identified with $S\cap V$ and all deletions
to $S\cap V$ are passed to that data structure immediately. The total update
time of this data structure is $T_{\mathrm{nn}}(G_{\infty})$ per single step
(3) run.

On the way to finding new paths/cycles, we store a (possibly empty) simple
_incomplete path_ $Q=s\to q$ in $H[S]$ for some $q\in
V(G_{f}^{\prime\prime})\setminus\\{t\\}$. Initially $Q=\emptyset$.

Given all the required data structures, the implementation of step (3) is very
simple. While $s\in S$, we do the following. While $q\notin t$, we take any
edge $e=qz\in E(H)$ with $z\in S$. If $F_{q}$ is non-empty, $e$ can be
extracted from $F_{q}$ in $O(1)$ time. Otherwise, such an edge has to come
from $G_{\infty}$. But then we can find such edge using a single query to the
near neighbor data structure in $Q_{\mathrm{nn}}(G_{\infty})$ time. If this
fails as well, by the definition of $S$, the nearly tight edges originating in
$q$ only lead to vertices $V\setminus S$ for which we already know that cannot
reach $t$ in $H$. So if finding a desired $e$ fails, we remove $q$ from $S$
and also remove the last edge of $Q$.

However, if $e$ has been found, we append $e$ to $Q$. Since $Q$ was a simple
path, this might cause some suffix $Q^{\prime}$ of $Q$ now form a cycle of
nearly tight edges. In such a case we send a unit of flow through the cycle
$Q^{\prime}$ and cut the suffix $Q^{\prime}$ off $Q$. On the other hand, if
$z\notin V(Q)$, we extend $Q$ with $e$. If it happens that $z=t$, we send flow
through $Q[V]$ and reset $Q$ to be an empty path.

In the above, whenever flow is sent through a path or a cycle, $H$ (and thus
the sets $F_{v}$) are updated accordingly due to some edges whose flow has
reached their capacity being dropped from $G_{f}$. This update time can be
charged to the number of edges of that path/cycle.

Note that when the entire procedure ends we have $Q=\emptyset$ since an
invariant $Q\subseteq H[S]$ is maintained. To analyze the total time, we first
observe that every insertion of an edge to the end of $Q$ can be charged to
its later deletion. Moreover, every deletion can be charged to either removing
some vertex from $S$ or increasing a flow on an edge in $H$. As a result, we
can bound the total number of insertions or deletions to $Q$ by $O(n+\Phi)$,
where $\Phi$ is the total flow pushed _through all edges_ of $H$ in the
process. Since every step of the algorithm can be charged to either a deletion
or insertion of an edge to $Q$, the total time needed to execute step (3) can
be bounded by

$O(T_{\mathrm{nn}}(G_{\infty})+m_{\mathrm{fin}}+\Lambda+Q_{\mathrm{nn}}(G_{\infty})\cdot(n+\Phi)).$

######  Lemma 8.15.

We have $\Phi=O(\Lambda)$.

###### Proof.

Let $f^{\prime}$ be the flow $f$ at the beginning of the run of step (3) of
our interest. Similarly, let $f^{\prime\prime}$ be the flow $f$ at the end of
that run.

Consider some edge $e$ of that undergoes a unit flow increase during the run
of step (3). Recall that $f(e)$ can only increase during that run since
$e^{\mathrm{R}}$ is not nearly tight if $e$ is. As a result, the number of
times $f(e)$ increases is exactly $f^{\prime\prime}(e)-f^{\prime}(e)$. The
total flow $\Phi$ sent through all edges in that run of step (3) can be thus
bounded using Lemmas 8.1 and 8.6 as follows:

$\Phi\leq\sum_{e\in E}|f^{\prime\prime}(e)-f^{\prime}(e)|\leq\sum_{e\in
E}|f^{\prime\prime}(e)|+\sum_{e\in
E}|f^{\prime}(e)|\leq(\Psi_{f^{\prime}}+2\Lambda)+(\Psi_{f^{\prime\prime}}+2\Lambda)\leq
10\Lambda.\qed$

Since $\Lambda\geq n$, we can thus conclude the following.

######  Lemma 8.16.

Step (3) of the main loop takes
$O(T_{\mathrm{nn}}(G_{\infty})+m_{\mathrm{fin}}+Q_{\mathrm{nn}}(G_{\infty})\cdot\Lambda)$
time.

By combining Lemmas 8.11, 8.13 and 8.16, we obtain that the refinement
procedure can be implemented to run in
$\widetilde{O}\left(\sqrt{\Lambda}\cdot\left(T_{\mathrm{cp}}(G_{\infty})+T_{\mathrm{nn}}(G_{\infty})+m_{\mathrm{fin}}+\Lambda\cdot
Q_{\mathrm{nn}}(G_{\infty})\right)\right)$ time, which immediately yields
Theorem 7.1.

###  8.5 Proof of Lemma 8.10

In this section we prove the following key bound. On the way, we also prove
Lemma 8.7. See 8.10

First suppose that $\Delta\leq 12\epsilon$. Since we also have
$\Psi_{f}\leq\Psi_{f_{1}}\leq 3\Lambda$, the desired inequality follows
immediately. So in the following let us assume $\Delta>12\epsilon$.

Inspired by the unit-capacity min-cost flow analysis of [GHKT17], we will
consider the following auxiliary graph. Define $G^{+}_{f}=(V,E^{+}_{f})$,
where $E^{+}_{f}=\\{e\in E:f(e)<f_{0}(e)\\}.$ For $e\in E^{+}_{f}$, set
$u^{+}(e)=f_{0}(e)-f(e)$ and let us treat $u^{+}(e)$ as the capacity of $e$ in
$G_{f}^{+}$.

######  Lemma 8.17.

For any $S\subseteq V$ we have:

$\sum_{v\in S}\mathrm{exc}_{f}(v)\leq\sum\\{u^{+}(e):ab=e\in E^{+}_{f},a\in
S,b\notin S\\}.$

###### Proof.

Indeed, by antisymmetry we have

$\sum_{v\in S}\sum_{\begin{subarray}{c}wv=e\in E\\\ w\in
S\end{subarray}}f(e)=0,$

and thus

$\displaystyle\sum_{v\in S}\mathrm{exc}_{f}(v)$ $\displaystyle=\sum_{v\in
S}\sum_{wv=e\in E}f(e)$ $\displaystyle=\sum_{v\in
S}\sum_{\begin{subarray}{c}wv=e\in E\\\ w\in S\end{subarray}}f(e)+\sum_{v\in
S}\sum_{\begin{subarray}{c}wv=e\in E\\\ w\in V\setminus S\end{subarray}}f(e)$
$\displaystyle=-\sum_{v\in S}\sum_{\begin{subarray}{c}vw=e\in E\\\ w\in
V\setminus S\end{subarray}}f(e).$

Applying the same transformation to $f_{0}$, and by the fact that circulations
have zero vertex excesses:

$0=\sum_{v\in V}\mathrm{exc}_{f_{0}}(v)=-\sum_{v\in
S}\sum_{\begin{subarray}{c}vw=e\in E\\\ w\in V\setminus
S\end{subarray}}f_{0}(e)$

By subtracting the obtained equations, and skipping non-positive terms, we
get:

$\sum_{v\in S}\mathrm{exc}_{f}(v)=\sum_{v\in
S}\sum_{\begin{subarray}{c}vw=e\in E\\\ w\in V\setminus
S\end{subarray}}(f_{0}(e)-f(e))\leq\sum_{v\in
S}\sum_{\begin{subarray}{c}vw=e\in E^{+}_{f}\\\ w\in V\setminus
S\end{subarray}}(f_{0}(e)-f(e))=\sum_{v\in S}\sum_{\begin{subarray}{c}vw=e\in
E^{+}_{f}\\\ w\in V\setminus S\end{subarray}}u^{+}(e).$

∎

Using Lemma 8.17, we can prove: See 8.7

###### Proof.

Note that $E_{f}^{+}\subseteq E_{f}$, so $G_{f}^{+}\subseteq G_{f}$. As a
result, it is enough to prove that a path $X\to D$ exists in $G_{f}^{+}$.
Consider the set $Z$ of vertices reachable from $X$ in $G_{f}^{+}$ (via edges
with $u^{+}(e)>0$), and suppose, for contradiction, that $Z\cap D=\emptyset$.
By the definition of $Z$ and Lemma 8.17, the total capacity of edges $ab=e\in
E^{+}_{f}\cap Z\times(V\setminus Z)$ is at least $\sum_{z\in
Z}\mathrm{exc}_{f}(z)\geq\Psi_{f}>0$. So there exists an edge $ab=e\in
E^{+}_{f}\cap Z\times(V\setminus Z)$ with $u^{+}(e)>0$. But $b\notin Z$
contradicts the definition of $Z$. ∎

Now define, for any $v\in V$, $\lambda^{+\textrm{out}}_{v}=\sum_{vw=e\in
E^{+}}u^{+}(e)$ and, symmetrically, $\lambda^{+\textrm{in}}_{v}=\sum_{wv=e\in
E^{+}}u^{+}(e)$. Set
$\lambda^{+}_{v}=\min(\lambda^{+\textrm{out}}_{v},\lambda^{+\textrm{in}}_{v})$.

######  Lemma 8.18.

For any $v\in V$, $\lambda^{+}_{v}\leq 2\lambda_{v}$.

###### Proof.

We show that $\lambda^{+\textrm{out}}_{v}\leq 2\lambda^{\textrm{in}}_{v}$ and
$\lambda^{+\textrm{in}}_{v}\leq 2\lambda^{\textrm{out}}_{v}$. This will give
$\lambda^{+}_{v}=\min(\lambda^{+\textrm{out}}_{v},\lambda^{+\textrm{in}}_{v})\leq\min(2\lambda^{\textrm{in}}_{v},2\lambda^{\textrm{out}}_{v})=2\lambda_{v}$
as desired.

We have

$\displaystyle\lambda^{+\textrm{out}}_{v}$ $\displaystyle=\sum_{vw=e\in
E_{f}^{+}}u^{+}(e)$ $\displaystyle=\sum_{vw=e\in E_{f}^{+}\cap
E_{0}}u^{+}(e)+\sum_{vw=e\in E_{f}^{+}\cap E_{0}^{\mathrm{R}}}u^{+}(e)$
$\displaystyle\leq\sum_{vw=e\in E_{f}^{+}\cap E_{0}}f_{0}(e)+\sum_{vw=e\in
E_{f}^{+}\cap E_{0}^{\mathrm{R}}}(-f(e))$ $\displaystyle\leq\sum_{vw=e\in
E_{0}}f_{0}(e)+\sum_{vw=e\in E_{0}^{\mathrm{R}}}(-f(e)).$

By the fact that $f_{0}$ is a circulation (and so $\mathrm{exc}_{f_{0}}(v)=0$)
and antisymmetry:

$\displaystyle\lambda^{+\textrm{out}}_{v}$ $\displaystyle\leq\sum_{vw=e\in
E_{0}^{\mathrm{R}}}-f_{0}(e)+\sum_{wv=e\in E_{0}}f(e)$
$\displaystyle\leq\sum_{wv=e\in E_{0}}f_{0}(e)+\sum_{wv=e\in E_{0}}f(e)$
$\displaystyle\leq 2\sum_{wv=e\in E_{0}}u(e)$
$\displaystyle=2\Lambda^{\textrm{in}}_{v}$

The proof that $\lambda^{+\textrm{in}}_{v}\leq 2\lambda^{\textrm{out}}_{v}$ is
symmetric. ∎

Consider some moment of the algorithm‘s runtime. For convenience, put
$\delta(v):=\delta_{G_{f}^{\prime\prime}}(s,v)=-p(v)$. Recall that
$\delta(x)\leq 0$ for all $x\in X$ and and $\delta(d)\geq\Delta$ for all $d\in
D$.

For any $uv=e\in E_{f}^{+}\subseteq E_{f}$ we have

$\delta(v)-\delta(u)=p(u)-p(v)\leq c(e)+\epsilon=-c(e^{\mathrm{R}})+\epsilon,$

but since $e^{\mathrm{R}}\in E_{f_{0}}$, $-c(e^{\mathrm{R}})\leq 4\epsilon$,
and thus we have

$\delta(v)-\delta(u)\leq 5\epsilon.$

For a number $z$, define $L(z)=\\{w\in V:\delta(w)<z\\}$. We have $X\subseteq
L(z)$ for any $z>0$ and $D\cap L(z)=\emptyset$ for any $z\leq\Delta$.
Consequently, for any $0<z\leq\Delta$ we have

$\sum_{v\in L(z)}\mathrm{exc}_{f}(v)=\sum_{v\in
X}\mathrm{exc}_{f}(v)=\Psi_{f}.$

Moreover, let $S(z)=\\{w\in V:\delta(w)\in[z,z+5\epsilon]\\}$ and
$q=\left\lfloor\frac{\Delta-6\epsilon}{\epsilon}\right\rfloor\geq\lfloor\Delta/(2\epsilon)\rfloor\geq\Delta/(4\epsilon)$
(here, we have used the assumption $\Delta\geq 12\epsilon$). Consider the sets

$S(\epsilon),S(2\cdot\epsilon),\ldots,S(q\cdot\epsilon).$

Note that each vertex $w\in V$ belongs to at most $6$ of the above sets.

As a result, using Lemma 8.18, we get:

$\sum_{i=1}^{q}\sum_{w\in S(i\cdot\epsilon)}\lambda_{w}^{+}\leq\sum_{w\in
V}6\lambda_{w}^{+}\leq\sum_{w\in V}12\lambda_{w}\leq 12\Lambda.$

Observe that there exists such an index $j\in\\{1,\ldots,q\\}$ that

$\sum_{w\in
S(j\cdot\epsilon)}\lambda_{w}^{+}\leq\frac{12\Lambda}{q}\leq\frac{48\epsilon\Lambda}{\Delta}.$

Now consider the set

$A=L(j\cdot\epsilon)\cup\\{w\in
S(j\cdot\epsilon):\lambda_{w}^{+}=\lambda_{w}^{+\textrm{out}}\\}.$

Observe that $X\subseteq L(\epsilon)\subseteq L(j\cdot\epsilon)\subseteq A$,
and so $\sum_{w\in A}\mathrm{exc}_{f}(w)=\Psi_{f}$. We now show that
$\sum_{w\in A}\mathrm{exc}_{f}(w)$ can be bounded by $\sum_{w\in
S(j\cdot\epsilon)}\lambda_{w}^{+}\leq\frac{48\epsilon\Lambda}{\Delta}$. By
Lemma 8.17, it is enough to show that

$\sum\\{u^{+}(e):e=ab\in E^{+}_{f},a\in A,b\in V\setminus A\\}\leq\sum_{w\in
S(j\cdot\epsilon)}\lambda_{w}^{+}.$ (9)

Take any edge $e=ab\in E_{f}^{+}$, $a\in A,b\in V\setminus A$. Recall that
$\delta(b)-\delta(a)\leq 5\epsilon$, so if $a\in L(j\cdot\epsilon)$, then
$b\in(V\setminus A)\cap S(j\cdot\epsilon)=\\{y\in
S(j\cdot\epsilon):\lambda_{y}^{+}<\lambda^{+\textrm{out}}_{y}\\}$. In
particular, we have $\lambda_{b}^{+}=\lambda_{b}^{+\textrm{in}}$. As a result,
the total sum of $u^{+}(e)$ over all considered edges $e$ with $a\in
L(j\cdot\epsilon)$ is no more than $\sum_{b\in(V\setminus A)\cap
S(j\cdot\epsilon)}\lambda_{b}^{+}$.

Note that the total sum of $u^{+}(e)$ over all edges $e=ab$ with $a\in A\cap
S(j\cdot\epsilon)$ is clearly no more than $\sum_{a\in A\cap
S(j\cdot\epsilon)}\lambda_{a}^{+\textrm{out}}=\sum_{a\in A\cap
S(j\cdot\epsilon)}\lambda_{a}^{+}$. Combining the two cases yields the desired
bound (9).

##  9 Omitted proofs for graph near-neighbor and closest-pair data structures

See 3.1

###### Proof.

For each $v$ we simply maintain a pointer to the first edge $e=vu$ in the list
of incident edges of $v$ that we have not yet detected that either $u\notin T$
or $w(e)+p(u)\geq\tau(v)$. When answering a query about $v$, we possibly
advance the pointer at $v$ in the list until we reach an edge that can be
returned. Since all the pointers only move forward, the total update time is
$O(m+n)$. The amortized query time is clearly $O(1)$. ∎

See 3.2

###### Proof.

To initialize the data structure, initialize individual near neighbor data
structures $\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$. Denote by
$T_{1},\ldots,T_{k}$ the respective sets $T$ of the data structures. We
maintain the invariant that $T_{i}=T\cap V_{i}$: upon deactivation of $v\in
T$, it is passed to all $\mathcal{D}_{i}$, where $v\in V_{i}$ (equiv. $v\in
T_{i}$).

Note that if one issues a query about vertex $x$ to $\mathcal{D}_{i}$ and no
edge within the threshold $\tau(v)$ is found, every subsequent query to
$\mathcal{D}_{i}$ about $x$ will fail as well.

Let $X_{v}:=\\{i:v\in V_{i}\\}$. To handle queries, for each vertex $u\in V$
we maintain an index $z_{u}\in X_{u}\cup\\{\infty\\}$, satisfying the
following invariant: for all $i\in X_{u}$ such that $i<z_{u}$ we have
$w_{G_{i}}(e)+p(v)\geq\tau(v)$ for all edges $uv=e\in E_{i}\cap(V_{i}\times
T_{i})$. Initially, we set $z_{u}=\min X_{u}$.

Upon query, we first check whether $z_{u}=\infty$. If so, by the invariant, no
such ’’near neighbor‘‘ edge exists and we return $\perp$. Otherwise, we repeat
the following until $z_{u}=\infty$ or we find some desired edge $uv$. Issue a
query to $\mathcal{D}_{z_{u}}$. If that query fails (i.e., returns $\perp$),
advance $z_{u}$ to the succeeding element of $X_{u}\cup\\{\infty\\}$. If the
query produces an edge, return that edge and stop.

Note that immediately before $z_{u}$ advances, a query to
$\mathcal{D}_{z_{u}}$ is made. The total cost of such queries is $\sum_{i\in
X_{u}}Q_{\mathrm{nn}}(G_{i})$. Through all $u$, we have

$\sum_{u\in V}\sum_{i\in
X_{u}}Q_{\mathrm{nn}}(G_{i})=\sum_{i=1}^{k}|V_{i}|\cdot
Q_{\mathrm{nn}}(G_{i}).$

We charge the above queries issued to the ’’local‘‘ data structures to the
total update time of the ’’global‘‘ data structure. Each query $u$ to the data
structure for $\bigcup_{i=1}^{k}G_{i}$ results in at most one query to some
$\mathcal{D}_{i}$ that does not advance $z_{u}$. We charge this query to the
query time of the global data structure which leads to the bound
$Q_{\mathrm{nn}}(\bigcup_{i=1}^{k}G_{i})=\max_{i=1}^{k}\\{Q_{\mathrm{nn}}(G_{i})\\}+O(1)$.
All the work that has not been charged can be easily seen to be
$\sum_{i=1}^{k}O(|V_{i}|)$. ∎

See 3.5

###### Proof.

Let $S,T\subseteq\bigcup_{i=1}^{k}V_{i}$. The combined data structure
$\mathcal{D}$ for $G_{1}\cup\ldots\cup G_{k}$ does no additional
preprocessing, and, upon initialization, sets up separate closest pair data
structures $\mathcal{D}_{i}$ for each of the graphs $G_{i}$. Denote by
$e_{i}^{*},S_{i},T_{i},\alpha_{i},\beta_{i},d_{i}$ the respective parameters
of $\mathcal{D}_{i}$. In the $i$-th data structure we maintain that
$S_{i}=S\cap V$, $T_{i}=T\cap V$, and $\alpha_{i},\beta_{i}$ naturally match
$\alpha,\beta$ respectively.

We also store the indices $i=1,\ldots,k$ in a priority queue $H$ so that the
key of $i$ equals $d_{i}(e_{i}^{*})$ and $H$ prioritizes smallest keys.
Whenever some $\mathcal{D}_{i}$ changes $e_{i}^{*}$, which happens at most
$O(|V_{i}|)$ times, the key of $i$ is updated in $H$ accordingly. As a result,
maintaining $H$ requires $O\left(\sum_{i=1}^{k}|V_{i}|\log{k}\right)$ time.
Moreover, since each edge of $G$ is contained in some $G_{i}$, if $j$ is the
top key of $H$, then $e_{j}^{*}=st$ minimizes
$w_{G}(e_{j}^{*})+\alpha(s)+\beta(t)$ over all edges of $G$.

The activations and extractions of vertices $v$ are simply passed to the
relevant data structures $\mathcal{D}$ such that $v\in V_{i}$. Consequently,
the total update time is
$\sum_{i=1}^{k}T_{\mathrm{cp}}(G_{i})+\sum_{i=1}^{k}O(|V_{i}|\log{k})$. ∎

Below, for any $X\subseteq V$, we use the notation
$X_{\textrm{in}}:=\\{x_{\textrm{in}}:x\in X\\}$,
$X_{\textrm{out}}:=\\{x_{\textrm{out}}:x\in X\\}$. See 4.5

###### Proof.

Suppose we need a near neighbor data structure $\mathcal{D}^{\prime}$ for
$G^{\prime}$ initialized with $T^{\prime}$, price function $p$, and thresholds
$\tau^{\prime}(u)$. Since the vertices $V_{\textrm{out}}$ have no incoming
edges, we can put $T^{\prime}:=T^{\prime}\cap V_{\textrm{in}}$. Moreover,
since the vertices $V_{\textrm{in}}$ have no outgoing edges, the near neighbor
queries for vertices in $V_{\textrm{in}}$ always fail. We thus focus on near
neighbor queries for vertices in $V_{\textrm{out}}$.

We simply use a near neighbor data structure $\mathcal{D}$ for $G$ initialized
with $T=\\{v:v_{\textrm{out}}\in T\\}$, price function
$p(u):=p^{\prime}(u_{\textrm{in}})$, and thresholds
$\tau(v):=\tau^{\prime}(v_{\textrm{out}})$. A query about vertex
$x_{\textrm{out}}$ on $\mathcal{D}^{\prime}$ is translated to a query about
$x$ in $\mathcal{D}$. ∎

See 4.6

###### Proof.

Let us identify $V$ with the numbers $\\{1,\ldots,n\\}$. For each
$b=1,\ldots,{\lfloor\log_{2}{n}\rfloor+1}$ and ${i\in\\{0,1\\}}$, denote by
$A_{b,i}$ be the subset of numbers of $\\{1,\ldots,n\\}$ whose $b$-th bit in
the binary representation equals $i$.

Let $S,T,\alpha,\beta$ be the parameters of the desired data structure for
$G^{\prime}$. Let $T_{0}$ be the initial set $T$. For each
$b=1,\ldots,{\lfloor\log_{2}{n}\rfloor+1}$ and $i\in\\{0,1\\}$, we set up a
closest pair data structure $\mathcal{D}_{b,i}$ for $G$ with the respective
parameters $S_{b,i},T_{b,i},\alpha_{b,i},\beta_{b,i}$. We maintain the
invariants: $S_{b,i}=S\cap A_{b,i}$, $T_{b,i}=T\setminus A_{b,i}$,
$\alpha_{b,i}(u)=\alpha(u_{\textrm{out}})$ for $u\in A_{b,i}$, and
$\beta_{b,i}(v)=\beta(v_{\textrm{in}})$ for $v\in T_{0}\setminus A_{b,i}$.

By the definition of vertex splitting, we can focus on activations of vertices
$V_{\textrm{out}}$ and extractions of vertices $V_{\textrm{in}}$ and assume
$S\subseteq V_{\textrm{out}}$ and $T\subseteq V_{\textrm{in}}$.

For each activation of some $u_{\textrm{out}}$ with
$\alpha(u_{\textrm{out}})$, we pass the activation of $u$ only to data
structures $\mathcal{D}_{b,i}$ satisfying $u\in A_{b,i}$. Similarly, if some
$v_{\textrm{in}}$ is extracted, we pass that extraction only to data
structures $\mathcal{D}_{b,i}$ satisfying $v\in T_{b,i}$. As a result, the
data structure $\mathcal{D}_{b,i}$ can be effectively seen as simulating a
closest pair data structure of the graph

$G^{\prime}[E^{\prime}\cap((A_{b,i})_{\textrm{out}}\times(V\setminus
A_{b,i})_{\textrm{in}})]=G^{\prime}[E^{\prime}\cap((A_{b,i})_{\textrm{out}}\times(A_{b,1-i})_{\textrm{in}})].$

Note that for each edge $uv$ in $G$, $u\neq v$, there exists such $(b,i)$ that
$u\in A_{b,i}$ and ${v\in V\setminus A_{b,i}}=A_{b,1-i}$: indeed, $u$ and $v$
differ at some bit in their binary representations. Therefore, the
$O(\log{n})$ sets $E^{\prime}\cap((A_{b,i})_{\textrm{out}}\times(V\setminus
A_{b,i})_{\textrm{in}})]$ actually cover the set
$E^{\prime}\cap(V_{\textrm{out}}\times V_{\textrm{in}})=E^{\prime}$, so by
Lemma 3.5 applied with $k=O(\log{n})$, there exists a closest pair data
structure for $G^{\prime}$ with total update time
$T_{\mathrm{cp}}(G^{\prime})=O(T_{\mathrm{cp}}(G)\log{n}+|V|\log{n}\log\log{n})$
that requires no additional preprocessing. The lemma follows by the assumption
$T_{\mathrm{cp}}(G)=\Omega(|V|)$. ∎

##  10 Dealing with non-simple or non-disjoint holes

###  10.1 Removing the assumption from Section 5

If a piece has $P$ has non-simple holes, by repeatedly splitting its boundary
vertices that are repeated on some hole, one can convert it into a piece
$P^{\prime}$ with simple holes exclusively of size
$|P|+O(|\partial{P}|)=|P|+O(\sqrt{r})$, plus a graph $P^{\prime\prime}$
consisting of $O(\sqrt{r})$ $0$-weight auxiliary edges with endpoints in
$\partial{P^{\prime}}$ such that (1)
$\partial{P}\subseteq\partial{P^{\prime}}$ and (2) for any
$u,v\in\partial{P}$, $\delta_{P^{\prime}\cup
P^{\prime\prime}}(u,v)=\delta_{P}(u,v)$. This is described in detail in
[KMNS17, Section 5.1]. Any feasible price function on $P$ can be trivially
converted into a feasible price function on $P^{\prime}\cup P^{\prime\prime}$
by setting the price of every copy to that of the original vertex.

By Lemmas 3.2, 3.5 and 5.1, there exist closest pair and near neighbor data
structures with total update time $\widetilde{O}(\sqrt{r})$ for the graph
$P^{\prime}\cup P^{\prime\prime}$. This is asymptotically no worse than we
could have if $P$ had no non-simple holes. The only property that we required
from $P^{\prime}\cup P^{\prime\prime}$ is that it preserves distances in $P$
between the vertices $\partial{P}$.

###  10.2 Removing the assumption from Section 6

Recall that in Section 6, we require a recursive decomposition
$\mathcal{T}(G^{*})$ of $G^{*}$ such that all pieces have simple and pairwise
vertex-disjoint holes. Let us call such a decomposition _simple_.

First of all, we can assume that $G^{*}$ is constant-degree: this can be
achieved easily by simply triangulating the faces of $G$ using $0$-capacity
edges at the very beginning.

In [IKLS17b, IKLS17a] it is shown, for a constant-degree plane graph $G_{0}$,
how a fixed recursive decomposition using cycle separators
$\mathcal{T}(G_{0})$, as described n Section 6, can be converted into a simple
recursive decomposition $\mathcal{T}(G_{1})$ of a certain augmented graph
$G_{1}$ in $O(n\log{n})$ time. The decomposition is of the same shape, i.e.,
there is a 1-1 correspondence between the pieces of $\mathcal{T}(G_{0})$ and
$\mathcal{T}(G_{1})$. In the graph $G_{1}$, each vertex $v\in V(G_{0})$
corresponds to a strongly connected induced subgraph $G_{1}[S_{v}]$ of
$G_{1}$, and each edge $e=uv$ of $G_{0}$ is replaced with a bunch of edges
connecting the subsets $S_{u}$ and $S_{v}$ in $G_{1}$.

For each piece $H_{1}\in\mathcal{T}(G_{1})$ corresponding to
$H_{0}\in\mathcal{T}(G_{0})$, the faces of $H_{1}$ can be split into
’’natural‘‘ faces, holes, and auxiliary faces. The auxiliary faces are created
when splitting original vertices of $G_{0}$ into subgraphs, or edges into
bunches of edges. Importantly, there is a 1-1 correspondence between the holes
of $H_{0}$ and the holes of $H_{1}$, and a 1-1 correspondence between the
natural faces of $H_{0}$ and ’’natural‘‘ faces of $H_{1}$. Every two
’’natural‘‘ faces or holes of $H_{1}$ are fully separated (i.e., do not share
vertices in $H_{1}$) with auxiliary faces and that‘s why they are all simple
and vertex-disjoint. The piece $H_{1}$ is only constant-factor larger than
$H_{0}$, and similarly the boundary size $|\partial{H_{1}}|$ is only constant-
factor larger than $|\partial{H_{0}}|$.

The transformation that $G_{0}$ needs to undergo on the way to becoming
$G_{1}$ can be described using a sequence of either (a) vertex-splits
(splitting a vertex $v$ into two adjacent vertices or into a triangle, with
embedding-respecting partition of edges $v$ among the resulting vertices) or
(b) parallel edge introductions.

We apply the conversion procedure of [IKLS17b, IKLS17a] to the decomposition
$\mathcal{T}(G^{*})$ of our dual graph $G^{*}$. Vertex splits in $G^{*}$
corresponds to introducing auxiliary vertices inside some of the faces of $G$
– we set the capacities of newly created edges to $0$ so that the cut/flow
values are preserved. Introducing parallel edges in $G^{*}$, in turn,
corresponds to splitting an edge of $G$ into two sequentially connected edges
– to preserve the cut/flow values, the parallel edge needs to inherit the
capacity/weight of the original edge.

Since the transformations that $G^{*}$ needs to undergo to have a simple
recursive decomposition do not change the flow/cut values, and the original
vertices of $G$ (original faces of $G^{*}$) are preserved in a 1-1
correspondence after the transformations, we conclude that indeed the
assumptions about the holes of Section 6 can be dropped.

## References

  * [ABC+23] Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, and Hsin-Hao Su.  Parallel and distributed exact single-source shortest paths with negative edge weights.  CoRR, abs/2303.00811, 2023.
  * [AES99] Pankaj K. Agarwal, Alon Efrat, and Micha Sharir.  Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications.  SIAM J. Comput., 29(3):912–953, 1999.
  * [AHdLT05] Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup.  Maintaining information in fully dynamic trees with top trees.  ACM Trans. Algorithms, 1(2):243–264, 2005.
  * [AKL+22] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi.  Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 884–895. IEEE, 2022.
  * [AKLR20] Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, and Sharath Raghvendra.  A faster algorithm for minimum-cost bipartite perfect matching in planar graphs.  ACM Trans. Algorithms, 16(1):2:1–2:30, 2020.
  * [AKM+87] Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber.  Geometric applications of a matrix-searching algorithm.  Algorithmica, 2:195–208, 1987.
  * [AKT21] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.  Subcubic algorithms for gomory-hu tree in unweighted graphs.  In STOC ‘21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1725–1737. ACM, 2021.
  * [AKT22] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.  Friendly cut sparsifiers and faster gomory-hu trees.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 3630–3649. SIAM, 2022.
  * [AMO93] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.  Network flows - theory, algorithms and applications.  Prentice Hall, 1993.
  * [AWY18] Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu.  Matching triangles and basing hardness on an extremely popular conjecture.  SIAM J. Comput., 47(3):1098–1122, 2018.
  * [BCF23] Karl Bringmann, Alejandro Cassis, and Nick Fischer.  Negative-weight single-source shortest paths in near-linear time: Now faster!  CoRR, abs/2304.05279, 2023.
  * [Bel58] Richard Bellman.  On a routing problem.  Quarterly of applied mathematics, 16(1):87–90, 1958.
  * [BG60] Robert G Busacker and Paul J Gowen.  A procedure for determining a family of minimum-cost network flow patterns.  Technical report, RESEARCH ANALYSIS CORP MCLEAN VA, 1960.
  * [BK09] Glencora Borradaile and Philip N. Klein.  An _O_(_n_ log _n_) algorithm for maximum _st_ -flow in a directed planar graph.  J. ACM, 56(2):9:1–9:30, 2009.
  * [BKM+17] Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen.  Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time.  SIAM J. Comput., 46(4):1280–1303, 2017.
  * [BNW22] Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen.  Negative-weight single-source shortest paths in near-linear time.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 600–611. IEEE, 2022.
  * [BSW15] Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen.  Min _st_ -cut oracle for planar graphs with near-linear preprocessing time.  ACM Trans. Algorithms, 11(3):16:1–16:29, 2015.
  * [BT88] Dimitri P. Bertsekas and Paul Tseng.  Relaxation methods for minimum cost ordinary and generalized network flow problems.  Operations Research, 36(1):93–114, 1988.
  * [CCE13] Sergio Cabello, Erin W. Chambers, and Jeff Erickson.  Multiple-source shortest paths in embedded graphs.  SIAM J. Comput., 42(4):1542–1571, 2013.
  * [CE01] Timothy M. Chan and Alon Efrat.  Fly cheaply: On the minimum fuel consumption problem.  J. Algorithms, 41(2):330–337, 2001.
  * [Cha20] Timothy M. Chan.  Dynamic generalized closest pair: Revisiting eppstein‘s technique.  In 3rd Symposium on Simplicity in Algorithms, SOSA 2020, pages 33–37. SIAM, 2020.
  * [CKL+22] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 612–623. IEEE, 2022.
  * [DGG+22] Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Guanghao Ye.  Nested dissection meets ipms: Planar min-cost flow in nearly-linear time.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 124–153. SIAM, 2022.
  * [EFL18] Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren.  Holiest minimum-cost paths and flows in surface graphs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1319–1332. ACM, 2018.
  * [EK72] Jack Edmonds and Richard M. Karp.  Theoretical improvements in algorithmic efficiency for network flow problems.  J. ACM, 19(2):248–264, 1972.
  * [Eri10] Jeff Erickson.  Maximum flows and parametric shortest paths in planar graphs.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pages 794–804, 2010.
  * [ET75] Shimon Even and Robert Endre Tarjan.  Network flow and testing graph connectivity.  SIAM J. Comput., 4(4):507–518, 1975.
  * [FJ56] Lester R Ford Jr.  Network flow theory.  Technical report, Rand Corp Santa Monica Ca, 1956.
  * [FR06] Jittat Fakcharoenphol and Satish Rao.  Planar graphs, negative weight edges, shortest paths, and near linear time.  J. Comput. Syst. Sci., 72(5):868–889, 2006.
  * [Fre87] Greg N. Frederickson.  Fast algorithms for shortest paths in planar graphs, with applications.  SIAM J. Comput., 16(6):1004–1022, 1987.
  * [Gab85] Harold N. Gabow.  Scaling algorithms for network problems.  J. Comput. Syst. Sci., 31(2):148–168, 1985.
  * [GH61] Ralph E Gomory and Tien Chung Hu.  Multi-terminal network flows.  Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961.
  * [GHKT17] Andrew V. Goldberg, Sagi Hed, Haim Kaplan, and Robert E. Tarjan.  Minimum-cost flows in unit-capacity networks.  Theory Comput. Syst., 61(4):987–1010, 2017.
  * [GK18] Pawel Gawrychowski and Adam Karczmarz.  Improved bounds for shortest paths in dense distance graphs.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pages 61:1–61:15, 2018.
  * [GMW20] Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Submatrix maximum queries in monge and partial monge matrices are equivalent to predecessor search.  ACM Trans. Algorithms, 16(2):16:1–16:24, 2020.
  * [GMWW18] Pawel Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen.  Better tradeoffs for exact distance oracles in planar graphs.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 515–529, 2018.
  * [GN80] Zvi Galil and Amnon Naamad.  An o(evlog2v) algorithm for the maximal flow problem.  J. Comput. Syst. Sci., 21(2):203–217, 1980.
  * [Gol95] Andrew V. Goldberg.  Scaling algorithms for the shortest paths problem.  SIAM J. Comput., 24(3):494–504, 1995.
  * [GR98] Andrew V. Goldberg and Satish Rao.  Beyond the flow decomposition barrier.  J. ACM, 45(5):783–797, 1998.
  * [GT89] Harold N. Gabow and Robert Endre Tarjan.  Faster scaling algorithms for network problems.  SIAM J. Comput., 18(5):1013–1036, 1989.
  * [GT90] Andrew V. Goldberg and Robert E. Tarjan.  Finding minimum-cost circulations by successive approximation.  Math. Oper. Res., 15(3):430–466, 1990.
  * [HKRS97] Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian.  Faster shortest-path algorithms for planar graphs.  J. Comput. Syst. Sci., 55(1):3–23, 1997.
  * [HRT15] Jacob Holm, Eva Rotenberg, and Mikkel Thorup.  Planar reachability in linear space and constant time.  In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 370–389. IEEE Computer Society, 2015.
  * [IKLS17a] Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Piotr Sankowski.  Decremental single-source reachability in planar digraphs.  CoRR, abs/1705.11163, 2017.
  * [IKLS17b] Giuseppe F. Italiano, Adam Karczmarz, Jakub Lącki, and Piotr Sankowski.  Decremental single-source reachability in planar digraphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1108–1121, 2017.
  * [IKP21] Giuseppe F. Italiano, Adam Karczmarz, and Nikos Parotsidis.  Planar reachability under single vertex or edge failures.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 2739–2758. SIAM, 2021.
  * [INSW11] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.  Improved algorithms for min cut and max flow in undirected planar graphs.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 313–322, 2011.
  * [Iri60] Masao Iri.  A new method of solving transportation-network problems.  1960\.
  * [Jew62] William S. Jewell.  Optimal flow through networks with gains.  Operations Research, 10(4):476–499, 1962.
  * [JV83] Donald B. Johnson and Shankar M. Venkatesan.  Partition of planar flow networks (preliminary version).  In 24th Annual Symposium on Foundations of Computer Science, pages 259–263, 1983.
  * [Kar84] Narendra Karmarkar.  A new polynomial-time algorithm for linear programming.  Comb., 4(4):373–396, 1984.
  * [Kar21] Adam Karczmarz.  Fully dynamic algorithms for minimum weight cycle and related problems.  In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 83:1–83:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [Kle05] Philip N. Klein.  Multiple-source shortest paths in planar graphs.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 146–155, 2005.
  * [KMNS17] Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir.  Submatrix maximum queries in monge matrices and partial monge matrices, and their applications.  ACM Trans. Algorithms, 13(2):26:1–26:42, 2017.
  * [KMS13] Philip N. Klein, Shay Mozes, and Christian Sommer.  Structured recursive separator decompositions for planar graphs in linear time.  In Symposium on Theory of Computing Conference, STOC‘13, pages 505–514, 2013.
  * [KMW10] Philip N. Klein, Shay Mozes, and Oren Weimann.  Shortest paths in directed planar graphs with negative lengths: A linear-space _O_(_n_ log${}^{\mbox{2}}$ _n_)-time algorithm.  ACM Trans. Algorithms, 6(2):30:1–30:18, 2010.
  * [KS19] Adam Karczmarz and Piotr Sankowski.  Min-cost flow in unit-capacity planar graphs.  In 27th Annual European Symposium on Algorithms, ESA 2019, volume 144 of LIPIcs, pages 66:1–66:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [KS21] Adam Karczmarz and Piotr Sankowski.  A deterministic parallel APSP algorithm and its applications.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 255–272. SIAM, 2021.
  * [KT18] Robert Krauthgamer and Ohad Trabelsi.  Conditional lower bounds for all-pairs max-flow.  ACM Trans. Algorithms, 14(4):42:1–42:15, 2018.
  * [ŁNSW12] Jakub Łącki, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.  Single source - all sinks max flows in planar digraphs.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 599–608, 2012.
  * [LPS21] Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak.  A nearly optimal all-pairs min-cuts algorithm in simple graphs.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 1124–1134. IEEE, 2021.
  * [LR19] Nathaniel Lahn and Sharath Raghvendra.  A faster algorithm for minimum-cost bipartite matching in minor-free graphs.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 569–588, 2019.
  * [Mil84] Gary L. Miller.  Finding small simple cycle separators for 2-connected planar graphs.  In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pages 376–382. ACM, 1984.
  * [MN95] Gary L. Miller and Joseph Naor.  Flow in planar graphs with multiple sources and sinks.  SIAM J. Comput., 24(5):1002–1017, 1995.
  * [MNW18] Shay Mozes, Yahav Nussbaum, and Oren Weimann.  Faster shortest paths in dense distance graphs, with applications.  Theor. Comput. Sci., 711:11–35, 2018.
  * [MW10] Shay Mozes and Christian Wulff-Nilsen.  Shortest paths in planar graphs with real lengths in _O_(_n_ log${}^{\mbox{2}}$_n_ /loglog _n_) time.  In Algorithms - ESA 2010, 18th Annual European Symposium, pages 206–217, 2010.
  * [Nus14] Yahav Nussbaum.  Network flow problems in planar graphs.  PhD thesis, 2014.
  * [SA12] R. Sharathkumar and Pankaj K. Agarwal.  Algorithms for the transportation problem in geometric settings.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pages 306–317. SIAM, 2012.
  * [SB65] Thomas L Saaty and Robert G Busacker.  Finite graphs and networks: An introduction with applications.  McGraw-Hill Book Company, 1965.
  * [ST83] Daniel Dominic Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  J. Comput. Syst. Sci., 26(3):362–391, 1983.
  * [Tar85] Éva Tardos.  A strongly polynomial minimum cost circulation algorithm.  Combinatorica, 5(3):247–256, 1985.
  * [vdBCK+23] Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford.  A deterministic almost-linear time algorithm for minimum-cost flow.  CoRR, abs/2309.16629, 2023.
  * [vdBLL+21] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.  Minimum cost flows, mdps, and $l$${}_{\mbox{1}}$-regression in nearly linear time for dense instances.  In STOC ‘21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 859–869. ACM, 2021.
  * [Zha22] Tianyi Zhang.  Faster Cut-Equivalent Trees in Simple Graphs.  In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 109:1–109:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.