Re: [igraph] Minimizing Number of Crossing Links in Bipartite Network Plot

[Tamas Nepusz]

Dear Lorenzo,

The short answer is: no, there aren't any news, igraph still doesn't
support this method directly.

The long answer is: the problem itself is NP-complete even when the
graph instances are sparse. However, there is a plethora of heuristics
that try to approximate the optimal solution, the most popular being the
barycenter method [1] and the median heuristic [2]. These both solve the
"one layer free" problem, i.e. the ordering of nodes in one of the
groups is fixed and it tries to find an optimal ordering for the
other group, but you can iterate the method by switching the fixed with
the non-fixed group in every step until convergence.

[1] Sugiyama K, Tagawa S and Toda M: Methods for visual understanding of
hierarchical system structures. IEEE Trans Syst Man Cyber 11(2):109-125,
1981.

[2] Eades P and Wormald NC: Edge crossings in drawings of bipartite
graphs. Algorithmica 11:379-403, 1994.

-- 
T.

On Wed, Jul 21, 2010 at 11:27:16AM +0200, Lorenzo Isella wrote:
> Dear All,
> I happened to ask something along these lines some time ago, so I am
> just wondering if there is any news.
> Suppose that you are given a bipartite graph (let us say that the nodes
> are either blue or red).
> This is what I would like to do: plot the graph placing the red nodes on
> top, the blue nodes at the bottom and (here comes the tricky bit)
> minimize the number of crossing links.
> Maybe this is doable by resorting to some minimization method (probably
> it all boils down to minimizing the total length of the links [meant
> here as segments]), but I am sure somebody else must have had this
> problem before me.
> Is there any implementation of this method for igraph/R?
> Many thanks
> 
> Lorenzo
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help