A generalization of Spira's theorem and circuits with small segregators or separators

As a corollary, we show that the Boolean Circuit Value problem for circuits with constant size segregators is in deterministic SPACE(log2⁡n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE(nlog⁡n); and that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE(n).