We re-examine the complexity of evaluating monotone planar circuits MPCVP, with special attention to circuits with cylindrical embeddings. MPCVP is known to be in NC^3, and for the special case of upward stratified circuits, it is known to be in LogDCFL. We characterize cylindricality, which is stronger than planarity but ...
more >>>