On the planar monotone computation of boolean functions

AbstractA criterion for testing whether a given monotone boolean function f is planar monotone computable from the sequence of inputs x1, x2,…, xn is developed in conjunction with an algorithm which (in principle) can construct a planar monotone circuit for f whenever one exists. Both the algorithm and the criterion require precomputation of the prime implicants and clauses of f;.As an application of the theory, it is shown that monotone boolean functions whose prime implicants and clauses contain configurations of a particular type cannot be computed by planar monotone circuits. Moreover, a monotone boolean function of n inputs which is computable by a planar monotone circuit can be computed by a planar monotone circuit with 16n4+O(n3) gates. All monotone boolean functions on four (or fewer) inputs are shown to be planar monotone computable