Parallel algorithms for minimum cuts and maximum flows in planar networks

Algorithms are given that compute maximum flows in planar directed networks either in O ((log n ) 3 ) parallel time using O ( n 4 ) processors or O ((log n ) 2 ) parallel time using O ( n 6 ) processors. The resource consumption of these algorithms is dominated by the cost of finding the value of a maximum flow. When such a value is given, or when the computation is on an undirected network, the bound is O ((log n ) 2 ) time using O ( n 3 ) processors. No efficient parallel algorithm is known for the maximum flow problem in general networks.