（N x M）图解问题

我需要一种算法来（有效地）解决我正在编写的一些图表软件中出现的问题。 我有两组节点，N和M.N中的每个节点n0与M中的唯一（对于n0）节点有0到M个连接。这些节点集将被安排在两个平行的水平线上，N个节点在M节点上方的行中。连接将绘制为从N到M的直线。 我需要做的是重新排列水平线内的N和M节点，以尽量减少交叉。他们以任何方式做到这一点比只是天真地列举所有可能的安排更有效率，即O（N！* M！）？ （实际上，它比这要糟糕得多，因为每个连接都必须检查交叉）。 尽管有关为什么需要相关文献的解释，但也欢迎参考相关文献。 如已经指出的，在一般情况下，这可以被认为是二分图（集合N和M）平面化算法。但是，这个特定的问题比那个（我希望可以使它更快）受到更多的限制，并且需要产生额外的信息（可能会使它变慢），如下所示： 图的限制是必须将连接绘制为从N到M的直线。在图论中，这实际上意味着连接不能在N或M中的节点后面，仅在它们之间。因此，具有四个连接器的2x2情况可以在一般的二分图情况下进行平面化，但在我的图中不能。 附加信息是，如果它不能平面化，我仍然需要一个最小交叉解决方案（或接近它）。通常，最小交叉算法与仅平面化的算法明显不同。