  We study the maximum $s,t$-flow oracle problem on planar directed graphs
where the goal is to design a data structure answering max $s,t$-flow value (or
equivalently, min $s,t$-cut value) queries for arbitrary source-target pairs
$(s,t)$. For the case of polynomially bounded integer edge capacities, we
describe an exact max $s,t$-flow oracle with truly subquadratic space and
preprocessing, and sublinear query time. Moreover, if
$(1-\epsilon)$-approximate answers are acceptable, we obtain a static oracle
with near-linear preprocessing and $\tilde{O}(n^{3/4})$ query time and a
dynamic oracle supporting edge capacity updates and queries in
$\tilde{O}(n^{6/7})$ worst-case time.
  To the best of our knowledge, for directed planar graphs, no (approximate)
max $s,t$-flow oracles have been described even in the unweighted case, and
only trivial tradeoffs involving either no preprocessing or precomputing all
the $n^2$ possible answers have been known.
  One key technical tool we develop on the way is a sublinear (in the number of
edges) algorithm for finding a negative cycle in so-called dense distance
graphs. By plugging it in earlier frameworks, we obtain improved bounds for
other fundamental problems on planar digraphs. In particular, we show: (1) a
deterministic $O(n\log(nC))$ time algorithm for negatively-weighted SSSP in
planar digraphs with integer edge weights at least $-C$. This improves upon the
previously known bounds in the important case of weights polynomial in $n$, and
(2) an improved $O(n\log{n})$ bound on finding a perfect matching in a
bipartite planar graph.

Data Structures and Algorithms