@techreport{R-89-11, TITLE = {An Efficient Parallel Algorithm for Planar Directed Reachability}, AUTHOR = {Andrzej Lingas}, YEAR = {1989}, NUMBER = {R-89-11}, INSTITUTION = ida, ADDRESS = idaaddr, ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-11+abstr}, ABSTRACT = {We present a preprocessing of planar digraphs which enables us to solve all the reachability problems for a distinguished vertex of a planar digraph in time O((log n)**2) using a CREW PRAM with O(n log n) processors. The preprocessing takes O((log n)**6) time using a CRCW PRAM with O((n**1.5)(log n)**2) processors. Employing it, we can find the transitive closure of a planar digraph in time O((log n)**6) using a CRCW PRAM with O((n**2)log n) processors.}, IDANR = {LiTH-IDA-R-89-11}