AN EFFICIENT PARALLEL ALGORITHM FOR THE GENERAL PLANAR MONOTONE CIRCUIT VALUE PROBLEM

A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR gates. Goldschlager, Cook & Dymond and others have developed NC² algorithms to evaluate a special layered form of a PMC. These algorithms require a large number of processors ( (n^6), where n is the size of the input circuit). Yang, and more recently, Delcher & Kosaraju have given NC algorithms for the general planar monotone circuit value problem. These algorithms use at least as many processors as the algorithms for the layered case. This paper gives an efficient parallel algorithm that evaluates a general PMC of size n in polylog time using only a linear number of processors on an EREW PRAM. This parallel algorithm is the best possible to within a polylog factor, and is a substantial improvementover the earlier algorithms for the problem. The algorithm uses several novel techniques to perform the evaluation, including the use of the dual of the plane embedding of the circuit to determine the propagation ofvalues within the circuit