A contraction procedure for planar directed graphs
Stephen Guattery, Gary Lee Miller · 1992
We show that testing reachability in a planar DAG can be performed in parallel in O(log n log n) time (O(log n) time using randomization) using O(n) processors. In general we give a paradigm for contracting a planar DAG to a point and then expanding it back. This paradigm is developed from a property of planar directed graphs we refer to as the Poincar'e index formula. Using this new paradigm we then "overlay" our application in a fashion similar to parallel tree contraction [MR85, MR89]. We also discuss some of the changes needed to extend the reduction procedure to work for general planar digraphs. Using the strongly-connected components algorithm of Kao [Kao91] we can compute multiple-source reachability for general planar digraphs in O(log 3 n) time using O(n) processors. This improves the results of Kao and Klein [KK90] who showed that this problem could be performed in O(log 5 n) time using O(n) processors. This work represents initial results of an effort to develop effi...