  For an undirected $n$-vertex planar graph $G$ with non-negative edge-weights,
we consider the following type of query: given two vertices $s$ and $t$ in $G$,
what is the weight of a min $st$-cut in $G$? We show how to answer such queries
in constant time with $O(n\log^4n)$ preprocessing time and $O(n\log n)$ space.
We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly.
Previously, no subquadratic time algorithm was known for this problem. Since
all-pairs min cut and the minimum cycle basis are dual problems in planar
graphs, we also obtain an implicit representation of a minimum cycle basis in
$O(n\log^4n)$ time and $O(n\log n)$ space. Additionally, an explicit
representation can be obtained in $O(C)$ time and space where $C$ is the size
of the basis.
  These results require that shortest paths are unique. This can be guaranteed
either by using randomization without overhead, or deterministically with an
additional $\log^2 n$ factor in the preprocessing times.
