Reachability in digraphs

Question

I have a problem that is reducible to (efficiently) determining the reachability of a node in a fully dynamic planar digraph.

I'm aware of "A fully dynamic data structure for reachability in planar digraphs" which provides $O(n^{2/3} \log n)$ query with a $O(n)$-space data structure.

Can this be / has this been bettered?

If all my queries have the same source node, is there a more efficient (in time/space/both) way?

Are there any other related literature that deals with more efficient queries albeit with more restrictions imposed on the digraph?

Thanks!

Answer 1

Another paper on this topic that you may find useful is Mikkel Thorup's Compact oracles for reachability and approximate distances in planar digraphs, J. ACM 51 (2004), no. 6, 993-1024. The abstract says:

It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an $O(\log n)$ space label for each vertex and then we can determine if one vertex can reach another considering their two labels only. The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from $\lbrace 0, \ldots, N\rbrace$, it approximates distances within a factor $(1+\epsilon)$ in $O(\log \log(nN) + 1/\epsilon)$ time. Our scheme can be extended to find and route along correspondingly short dipaths.