Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors.

What is the best known parallel algorithm for st-connectivity in directed planar graphs ?

Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial).

This question is related to one of my previous questions. My previous question is about general directed graphs which are not necessarily planar.

  • 4
    $\begingroup$ it took me some clicking back and forth to realize that the difference was planarity. can you clarify that when you mention the previous question ? $\endgroup$ Sep 7, 2011 at 23:02
  • 3
    $\begingroup$ I did the same thing as Suresh, and I took the liberty of editing the last sentence. The word “general” is not very informative when the reader does not know what it is contrasted to (“planar” in this case). I hope you do not mind…. $\endgroup$ Sep 8, 2011 at 16:41

1 Answer 1



  • Kao, Ming-Yang; Klein, Philip N. (1993), Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, J. Comput. System Sci. 47 (1993), no. 3, 459–500.

Their Theorem 10 gives a deterministic CRCW algorithm for $st$-reachability in planar digraphs with $O(n)$ processors and $O(\log^3 n)$ time. Searching Google scholar for other papers that cited theirs, I didn't see anyone else with improvements to this.


This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .