Lingas, A. (1989). An Efficient Parallel Algorithm for Planar Directed Reachability. Technical Report LiTH-IDA-R-89-11, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
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.
CS Dept TR Overview