1-1hit |
We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.