<p>See</p>

<ul>
<li>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.</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2016-08-11T22:34:03.553Z
2016-08-11T22:34:03.553Z
David Eppstein
<p><a href="http://portal.acm.org/citation.cfm?id=314500.314562" rel="nofollow noreferrer">Chong, Han and Lam</a> showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. </p>

<p>What is the best known parallel algorithm for <a href="http://en.wikipedia.org/wiki/St-connectivity" rel="nofollow noreferrer">st-connectivity</a> in directed planar graphs ?</p>

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

<p>This question is related to <a href="https://cstheory.stackexchange.com/questions/1558/parallel-algorithms-for-directed-st-connectivity">one</a> of my previous questions. My <a href="https://cstheory.stackexchange.com/questions/1558/parallel-algorithms-for-directed-st-connectivity">previous question</a> is about general directed graphs which are not necessarily planar.</p>

CC BY-SA 3.0
2011-09-07T23:02:00.117Z
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 ?
Suresh Venkat
CC BY-SA 3.0
2011-09-08T16:41:40.007Z
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….
Tsuyoshi Ito
<ds.algorithms><graph-theory><dc.parallel-comp>
Parallel algorithms for reachability in directed planar graphs
Shiva Kintali
# Parallel algorithms for reachability in directed planar graphs

(Asked by: username_0 on 2011-09-07)

[Chong, Han and Lam](http://portal.acm.org/citation.cfm?id=314500.314562) 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](http://en.wikipedia.org/wiki/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](https://cstheory.stackexchange.com/questions/1558/parallel-algorithms-for-directed-st-connectivity) of my previous questions. My [previous question](https://cstheory.stackexchange.com/questions/1558/parallel-algorithms-for-directed-st-connectivity) is about general directed graphs which are not necessarily planar.

**Tags:** ds.algorithms, graph-theory, dc.parallel-comp

> **Comments:**
> **username_1**: 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 ?  
> **username_2**: 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….  

---

## 1 answers

### Answer by username_3 on 2016-08-11. Score: 3

See

* 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.


---

