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((logn)³) parallel time using O(n⁴) processors or O((logn)²) parallel time using O(n⁶) 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((logn)²) time using O(n³) processors. No efficient parallel algorithm is known for the maximum flow problem in general networks.