CROSSING NUMBER IS NP-COMPLETE

CROSSING NUMBER IS NP-COMPLETE
复制标题

DOI：
10.1137/0604033
复制
发表时间：
1983-01-01
期刊：
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS
影响因子：
--
通讯作者：
JOHNSON, DS
JOHNSON, DS
中科院分区：
其他
文献类型：
--
作者：
GAREY, MR;JOHNSON, DS

文献摘要

被引文献

相似文献

本文讨论了一个与最优电路布局问题有关的问题：给定一个图或网络，我们如何将其嵌入到平面中以最小化边交叉的数量？我们证明了这个问题是NP完全的，因此不太可能有任何有效的方法来设计最优嵌入。
In this paper we consider a problem related to questions of optimal circuit layout: Given a graph or network, how can we embed it in a planar surface so as to minimize the number of edge-crossings? We show that this problem is NP-complete, and hence there is not likely to be any efficient way to design an optimal embedding.