MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.