Simple and Efficient Bilayer Cross Counting

Barth, Wilhelm and Jünger, Michael and Mutzel, Petra (2002) Simple and Efficient Bilayer Cross Counting.
Published In: Graph drawing : 10th international symposium, GD 2002, Irvine, CA, USA, August 26 - 28, 2002 ; revised papers, Lecture notes in computer science. 2528 Springer 2002, pp. 331-360.


We consider the problem of counting the interior edge crossings when a bipartite graph G=(V,E) with node set V and edge set E is drawn such that the nodes of the two shores of the bipartition are on two parallel lines and the edges are straight lines. The efficient solution of this problem is important in layered graph drawing.Our main observation is that it can be reduced to counting the inversions of a certain sequence. This leads to an O(|E|+|C|) algorithm, where C denotes the set of pairwise interior edge crossings, as well as to a simple O(|E|log|V_{m small}|) algorithm, where V_{m small} is the smaller cardinality node set in the bipartition of the node set |V| of the graph. We present the algorithms and the results of computational experiments with these and other algorithms on a large collection of instances.

Download: [img] Postscript - Preprinted Version
Download (324kB) | Preview
Download: [img] PDF - Preprinted Version
Download (221kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2002-433
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 08 May 2003 00:00
Last Modified: 12 Jan 2012 11:54