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 strictly generalizes upward planarity, and make the
characterization partially constructive. We use this construction,
and four key reduction lemmas, to obtain several improvements. We
show that stratified cylindrical monotone circuits can be
evaluated in LogDCFL, arbitrary cylindrical
monotone circuits can be evaluated in AC^1(LogDCFL), while
monotone circuits with one-input-face planar embeddings can be
evaluated in LogCFL. For monotone circuits with focused
embeddings, we show an upper bound of AC^1(LogDCFL).
We re-examine the NC^3 algorithm for general MPCVP, and note that it
is in AC^1(LogCFL) = SAC^2. Finally, we show
that monotone circuits with toroidal embeddings can, given such an
embedding, be evaluated in NC. Also, special kinds of arbitrary
genus circuits can also be evaluated in NC.