Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization
Matthias F. M. Stallmann, F. Brglez, Debabrata Kumar Ghosh · ACM Journal of Experimental Algorithmics · 2001
The bigraph crossing problem, embedding the two node sets of a bipartite graph along two parallel lines so that edge crossings are minimized, has applications to circuit layout and graph drawing. Experimental results for several previously known and two new heuristics suggest continued exploration of the problem, particularly sparse instances. We emphasize careful design of experimental subject classes and present novel views of the results. All source code, data, and scripts are available on-line