Crossing Minimization in Linear Embeddings of Graphs
Crossing Minimization in Linear Embeddings of Graphs
复制标题
图线性嵌入中的交叉最小化
DOI：
10.1109/12.46286
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
T. Fujisawa
中科院分区：
文献类型：
--
作者：
S. Masuda;K. Nakajima;T. Kashiwabara;T. Fujisawa
在一些电路布局问题中，出现了以最少的边交叉数将图嵌入平面的问题。一般来说，它是NP难的。最近，在书籍嵌入领域，这个问题被证明是NP-难的，即使顶点被放置在直线l上。作者表明，该问题仍然是NP难的，即使除了这些限制，l上的顶点的位置是预先确定的。>
The problem of embedding a graph in the plane with the minimum number of edge crossings arises in some circuit layout problems. It has been known to be NP-hard in general. Recently, in the area of book embedding, this problem was shown to be NP-hard even when the vertices are placed on a straight line l. The authors show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on l are predetermined. >