(N x M) Diagramming Problem

Question

I need an algorithm to (efficiently) solve a problem that has come up in some diagramming software that I am writing.

I have two sets of nodes, N and M. Each node n0 in N has 0 to M connections to a unique (for n0) node in M. These sets of nodes are to be arranged on two parallel horizontal lines, with the N nodes in the line above the M nodes. The connections will be drawn as straight lines from N to M.

What I need to do is to rearrange the N and M nodes within their horizontal lines, to minimize crossings. Is their any way to do this that is more efficient than just naively enumerating all possible arrangements, which is O(N!*M!)? (actually, its considerably worse than that, since each connection has to be checked for crossing also).

References to relevant literature are welcome also, though an explanation as to why its relevant is desired.

---

As has been pointed out, in the general case this could be considered a bipartite graph (the sets N and M) planarization algorithm. However, this specific problem is considerably more restricted than that (which I hope can make it faster) and is required to produce additional information (which may make it slower), as follows:

1. the diagram's restrictions are that the connections must be drawn as straight lines from N to M. In graph theory, this practically means that the connections cannot go behind the nodes in N or M, only between them. Thus, the 2x2 case with four connectors can be planarized in the general Bipartite graph case, but cannot in the case of my diagram.

2. The additional information, is that if it cannot be planarized, I still need a minimal-crossing solution (or close to it). Generally, minimal-crossing algorithims are significantly different from those that only planarize.

Answer 1

Your problem can be solved with force graph alignment, as long as you don't require that the nodes keep a specific position on their lines (even if you do require that with some alteration you could pull it off)

The main thing you need to change is make force alignment 1D instead of 2D, only aligning the nodes on the X axes instead of aligning nodes on both X and Y.

The premise of the algorithm is that you have forces acting on the nodes, so the nodes have repulsion acting on them causing them to move further away from each other, however nodes that are connected to one another have attraction acting on them that is greater then the repulsion. In each loop you add the forces up causing the nodes that are attracted to one another to come in closer to one another while nodes that are not will repel, your alignment is done when you sum a total force thats lower then some threshold, something like 0.001.

http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)

Answer 2

The model you described is called bipartite graph, and what you request is a planarization algorythm. The best way to answer your question is to google a bit.

Answer 3

How large are N and M? There's a solution based on dynamic programming that runs in time O(min(N, M)! * 2**max(N, M) * poly(N, M)), but I'm not sure if that's a significant improvement over brute force in your view.

Answer 4

suddnely_me is right, but maybe you don't need a perfect solution. you could also try a really simple greedy algorithm. sorting all the nodes depending on the number of connections. then add one by one to the horizontal line.. didn't thought it through though.. but could lead to a simple approach..