  We show how to combine two techniques for efficiently computing shortest
paths in directed planar graphs. The first is the linear-time shortest-path
algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is
Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm
on the dense distance graph (DDG). A DDG is defined for a decomposition of a
planar graph $G$ into regions of at most $r$ vertices each, for some parameter
$r < n$. The vertex set of the DDG is the set of $\Theta(n/\sqrt r)$ vertices
of $G$ that belong to more than one region (boundary vertices). The DDG has
$\Theta(n)$ arcs, such that distances in the DDG are equal to the distances in
$G$. Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG
(nicknamed FR-Dijkstra) runs in $O(n\log(n) r^{-1/2} \log r)$ time, and is a
key component in many state-of-the-art planar graph algorithms for shortest
paths, minimum cuts, and maximum flows. By combining these two techniques we
remove the $\log n$ dependency in the running time of the shortest-path
algorithm, making it $O(n r^{-1/2} \log^2r)$.
  This work is part of a research agenda that aims to develop new techniques
that would lead to faster, possibly linear-time, algorithms for problems such
as minimum-cut, maximum-flow, and shortest paths with negative arc lengths. As
immediate applications, we show how to compute maximum flow in directed
weighted planar graphs in $O(n \log p)$ time, where $p$ is the minimum number
of edges on any path from the source to the sink. We also show how to compute
any part of the DDG that corresponds to a region with $r$ vertices and $k$
boundary vertices in $O(r \log k)$ time, which is faster than has been
previously known for small values of $k$.
