Abstract
We clarify the computational complexity of planarity testing, by showing that planarity testing is hard for
L
, and lies in
SL
. This nearly settles the question, since it is widely conjectured that
L=
SL
. The upper bound of
SL
matches the lower bound of
L
in the context of (nonuniform) circuit complexity, since
L
/poly is equal to
SL
/poly. Similarly, we show that a planar embedding, when one exists, can be found in
FL
SL
. Previously, these problems were known to reside in the complexity class
AC
1
, via the O(log
n) time CRCW PRAM algorithm of Ramachandran and Reif, although planarity checking for degree-three graphs had been shown to be in
SL
[Chicago J. Theoret. Comput. Sci. (1995); J. ACM 31 (2) (1984) 401].