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).
翻译:我们证明很难决定图形是否为 6 apex 图形的正方。 这显示平方根问题对于稀有图形的正方形( 甚至是来自适当小封闭类的图形) 来说是无法被分割的 。