Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002
DOI: 10.7155/jgaa.00088
Simple and Efficient Bilayer Cross Counting
Vol. 8, no. 2, pp. 179-194, 2004. Regular paper.
Abstract 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 directly to an O(|E|log|V|) algorithm based on merge
sorting. We present an even simpler O(|E|log|Vsmall|)
algorithm, where Vsmall is the smaller cardinality node set
in the bipartition of the node set V of the graph. This algorithm
is very easy to implement. Our computational experiments on a large
collection of instances show that it performs well in comparison to
previously published algorithms, which are much more complicated to
understand and implement.
|
Journal Supporters
|