Bimodal Crossing Minimization

Buchheim, Christoph and J√ľnger, Michael and Menze, Annette and Percan, Merijam (2006) Bimodal Crossing Minimization.
Published In: Computing and combinatorics : 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings, Lecture Notes in Computer Science. 4112 Springer 2006, pp. 497-506.


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.

Download: [img] Postscript - Preprinted Version
Download (483kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2005-493
Depositing User: Christoph Buchheim
Date Deposited: 30 Jul 2008 00:00
Last Modified: 12 Jan 2012 09:15