The complexity of planarity testing
The complexity of planarity testing
复制标题
DOI：
10.1016/j.ic.2003.09.002
复制
发表时间：
2004-02-25
影响因子：
1
通讯作者：
Mahajan, M
中科院分区：
文献类型：
--
作者：
Allender, E;Mahajan, M
我们澄清了平面性测试的计算复杂性，通过显示，平面性测试是很难的L，并在于SL。这几乎解决了这个问题，因为人们普遍认为L = SL。SL的上限在（非均匀）电路复杂度的上下文中匹配L的下限，因为L/poly等于SL/poly。同样，我们表明，平面嵌入，当一个存在，可以发现在FLSL。以前，这些问题被认为是复杂度类AC（1），通过Ramachandran和Reif的O（log n）时间CRCW-PRAM算法，尽管三度图的平面性检查已被证明是在SL中。(C)2003年爱思唯尔公司All rights reserved.
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 (non-uniform) circuit complexity, since L/poly is equal to SL/poly. Similarly, we show that a planar embedding, when one exists, can be found in FLSL. 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. (C) 2003 Elsevier Inc. All rights reserved.