The complexity of planarity testing

Allender, Eric ; Mahajan, Meena (2004) The complexity of planarity testing Information and Computation, 189 (1). pp. 117-134. ISSN 0890-5401

[img] PDF

Official URL:

Related URL:


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 (logn) 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].

Item Type:Article
Source:Copyright of this article belongs to Elsevier B.V.
Keywords:Planar graphs; Symmetric logspace
ID Code:127980
Deposited On:14 Oct 2022 11:32
Last Modified:14 Oct 2022 11:32

Repository Staff Only: item control page