Minimizing number of crossings in a bipartite graph

Question

The following algorithm problem occurred to me while drawing a graph for something unrelated:

We have a plane drawing of a bipartite graph, with the disjoint sets arranged in columns as shown. How can we rearrange the nodes within each column so that the number of edge crossings is minimized? I know this problem is NP-hard for general graphs (link), but is there some trick considering that the graph is bipartite?

As a follow-up, what if there is a third column w, which only has edges to v? Or further?

Longmire

Do you want two columns (one for each subgraph) or can the nodes be placed in an arbitrary way? – Inoculum

do you want optimal solution or an approximation? (nice question btw) – Inoculum

@arturgrzesiak The nodes should still be in two columns. I'll edit the question to make that clearer. – Longmire

Either would be helpful. A human-computable algorithm (i.e. one that I can use while just drawing graphs by hand) would be especially nice. – Longmire

Answer 1

The paper On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi mentions that the original paper on the crossing number by Garey and Johnson also proved that minimising the number of edge crossings is NP-hard for bipartite graphs. In fact, it is still NP-hard even if you are told the optimal order for one column:

Given a bipartite graph, a 2-layered drawing consists of placing nodes in the first node set V on a straight line L1 and placing nodes in the second node set W on a parallel line L2. The problem of minimizing the number of crossings between arcs in a 2-layered drawing was first introduced by Harary and Schwenk. The one-sided crossing minimization problem asks to find an ordering of nodes in V to be placed on L1 so that the number of arc crossings is minimized (while the ordering of the nodes in W on L2 is given and fixed). Applications of the problem can be found in VLSI layouts and hierarchical drawings.

However, the two-sided and one-sided problems are shown to be NP-hard by Garey and Johnson and by Eades and Wormald , respectively.

Pangermanism

That paper looks like exactly what I'm looking for. Thanks! – Longmire

Answer 2

Peter de Rivaz pointed that it is NP-Hard, but still if you are fine with some approximation you can go with the following solution.

My initial thought was to use some force-based algorithm for graph layouting, but it can be bit tedious to implement. But hey, there is this wonderful program graphviz.org, that can make the whole work for you.

So after installing just prepare a file with your graph:

graph G{
   {rank=same A B C D E}
   {rank=same F G H K I J}

    A -- F;
    A -- G;
    A -- K;
    A -- I;
    A -- H;
    A -- J;

    B -- G;

    C -- G;
    C -- J;

    D -- K;
    D -- I;
}

Run: dot -Tpng yourgraph -o yourgraph.png

and get something like that for free :-):

Inoculum