An NC algorithm for the general planar monotone circuit value problem

A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in a plane and that has only AND and OR gates. Although a special case of the planar monotone circuit value problem (PMCVP) has been shown to be in NC², it was not known whether the general PMCVP is in NC. In the paper, the author first gives an NC² algorithm to evaluate a layered one-input-face PMC using straight-line code parallel evaluation technique. He then applies the algorithm to a less restrictive one-input-face PMC. Finally, he gives an NC³ algorithm for the general PMCVP