Counting edge crossings in a 2-layered drawing

Given a bipartite graph G = (V, W, E) with a bipartition {V, W} of a vertex set and an edge set E, a 2-layered drawing of G in the plane means that the vertices of V and W are respectively drawn as distinct points on two parallel lines and the edges as straight line segments. We consider the problem of counting the number of edge crossings. In this paper, we design two algorithms to this problem based on the dynamic programming and divide-and-conquer approaches. These algorithms run in O(n(1)n(2)) time and O(m) space and in O(min{n(1)n(2), \E\ log(min{\V\, \W\})}) time and O(m) space, respectively. Our algorithms outperform the previously fastest Theta(\E\log(min{\V\, \W\})) time algorithm for dense graphs. (C) 2004 Elsevier B.V. All rights reserved.