Simple and Efficient Bilayer Cross Counting

Barth, Wilhelm and Jünger, Michael and Mutzel, Petra (2002) Simple and Efficient Bilayer Cross Counting. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002 , pp. 130-141(Official URL:

This is the latest version of this item.

Full text not available from this repository.


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 drawn as distinct points on two parallel lines and the edges as straight line segments. 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(\vert E\vert\log\vert V_{\rm small}\vert)$ algorithm, where $V_{\rm 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 w ith these and other algorithms on a large collection of instances.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_13
Classifications: M Methods > M.500 Layered
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered

Available Versions of this Item

Actions (login required)

View Item View Item