Bipartite layout algorithms

[Gábor Csárdi]

E.g. http://www.iplab.cs.tsukuba.ac.jp/paper/.../ito_hcii2009.pdf is a more sophisticated algorithm, for 2d and 3d.

A simple algorithm would be to place the vertices in two columns and then minimize the edge crossings.

[Tamás Nepusz (ntamas)]

The current implementation of the Sugiyama layout would do as a simple first approach.

[Gábor Csárdi (gabor.csardi)]

Isn't that overkill here? I would just top vertices on the left, bottom vertices on the right, and then edges are from left to right. In this simple case it might be even possible to minimize the edge crossings analytically. But I might be wrong.

[Tamás Nepusz (ntamas)]

The Sugiyama layout uses a very similar approach (minimizing edge crossings using a simple heuristic), the only difference is that it does a lot of extra legwork to ensure that every edge spans only one layer -- this is achieved by inserting dummy nodes etc. If you only have two layers, the Sugiyama layout will not insert any extra nodes, it will just try to order the vertices in the top and bottom (left and right) layers in order to minimize the number of edge crossings. So I still think that it is enough to call igraph_layout_sugiyama with a predefined layering (from the vertex types). Maybe we can create a wrapper on top of igraph_layout_sugiyama that hides the unneeded arguments.

[Gábor Csárdi (gabor.csardi)]

OK, I'll try that.

[Gábor Csárdi (gabor.csardi)]

I have added the simple two-row (or two-column) layout in revision #2942 (0.7-main).

[Gábor Csárdi (gabor.csardi)]

The simple Sugiyama layout will do for version 0.6.1, so I'll reschedule the rest for 0.7

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/235