图的网格可扩张性的有效识别

按照Garey和Johnson的说法,识别图的网格可嵌入性是一个很难的问题。直到现在都没有发现有效的算法。然而,这篇文章为节点的劈对的数目与阶相比充分小的图的网格可嵌入性的更有效的识别提供了一个理论根据。事实上,由本文的结果可以建立图的网格可扩张性识别和求一个图的平面嵌入的网格扩张的有效算法。