"Bimodal Crossing Minimization"
Article by Christoph Buchheim, Michael Jünger, Annette Menze, Merijam Percan, available as BibTeX Source, postscript file and compressed postscript file.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2005-493
Keywords:	bioinformatics, crossing minimization, directed edges, graph drawing
MSC codes:	05C20, 05C85, 92-08
This article is to appear in "Computing and Combinatorics (COCOON 2006)".
Abstract:	We consider the problem of drawing a directed graph in two dimensions with a small or minimum number of crossings such that for every node the incoming (and hence the outgoing) edges appear consecutively in the cyclic adjacency lists. We show how to adapt the planarization method and the recently devised exact crossing minimization approach in a simple way. We report experimental results on the increase in the number of crossings involved by this additional restriction on the set of feasible drawings. It turns out that this increase is negligible for most practical instances.