最小化二分图中的交叉数

在为不相关的东西绘制图表时，我遇到了以下算法问题：

我们有一个二部图的平面图，其中不相交的集合按列排列，如图所示。我们如何重新排列每列内的节点以使边缘交叉的数量最小化？我知道这个问题对于一般图来说是 NP 困难的（link http://en.wikipedia.org/wiki/Crossing_number_%28graph_theory%29#Complexity），但是考虑到该图是二分图，是否有一些技巧？

作为后续，如果有第三列怎么办w，它只有边v？或者更进一步？

论文关于二分图中的单边交叉最小化 Hiroshi 的大学位 长持 http://www.sciencedirect.com/science/article/pii/S0304397504007911提到加里（Garey）关于交叉数的原始论文和 约翰逊还证明了最小化边缘交叉的数量 对于二分图来说是 NP 困难的。事实上，它仍然是NP困难的 即使您被告知一列的最佳顺序：

给定一个二部图，一个 2 层绘图由放置节点组成 在直线 L1 上的第一个节点集 V 中并将节点放置在 平行线L2上的第二节点集W。最小化问题 2层绘图中圆弧之间的交叉数为第一个 由 Harary 和 Schwenk 提出。单边交叉最小化 问题要求找到 V 中要放置在 L1 上的节点的顺序，因此 弧交叉的数量被最小化（同时 L2 上 W 中的节点是给定并固定的）。问题的应用 可以在 VLSI 布局和分层绘图中找到。

然而，双面和单面问题被证明是 NP 困难的 分别由 Garey 和 Johnson 以及 Eades 和 Wormald 撰写。