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 [
25]. 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 a O(log n) time CRCW PRAM algorithm [22], although planarity checking for degree-three graphs had been shown to be in SL [23, 20].
Supported in part by NSF grant CCR-9734918.
Part of this work was done when this author was supported by the NSF grant CCR-9734918 on a visit to Rutgers University during
summer 1999.