Simple and Efficient Bilayer Cross Counting - Barth, Wilhelm; Mutzel, Petra; Jünger, Michael (Journal of Graph Algorithms and Applications, 2004)
We consider the problem of counting the interior edge crossings whena bipartite graph G=(V,E) with node set V and edge set E isdrawn such that the nodes of the two shores of the bipartition aredrawn as distinct points on two parallel lines and the edges asstraight line segments. The efficient solution of this problem isimportant in layered graph drawing. Our main observation is that itcan be reduced to counting the inversions of a certain sequence.This leads directly to an O(|E|log|V|) algorithm based on mergesorting. We present an even simpler O(|E|log|Vsmall|)algorithm, where Vsmall is the smaller cardinality node setin the bipartition of the node set V of the graph. This algorithmis very easy to implement. Our computational experiments on a largecollection of instances show that it performs well in comparison topreviously published algorithms, which are much more complicated tounderstand and implement. <!---->