论文标题
几乎平面图的平方根
Square roots of nearly planar graphs
论文作者
论文摘要
我们证明，确定图形是否是6-apex图的平方是NP-HARD。这表明，对于稀疏图的平方（甚至是适当的次要类别的图形），平方根问题是无法处理的。
We prove that it is NP-hard to decide whether a graph is the square of a 6-apex graph. This shows that the square root problem is not tractable for squares of sparse graphs (or even graphs from proper minor-closed classes).
