Universität zu Köln

Barth, Wilhelm, Mutzel, Petra ORCID: 0000-0001-7621-971X and Jünger, Michael (2004). Simple and Efficient Bilayer Cross Counting (Journal Version). Journal of Graph Algorithms and Applications, 8 (21). pp. 179-194. Brown University.

Preview

PDF zaik2003-449.pdf - Draft Version Download (680kB) | Preview

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|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. 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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Barth, Wilhelm UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED orcid.org/0000-0001-7621-971X UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548717
Journal or Publication Title:	Journal of Graph Algorithms and Applications
Volume:	8
Number:	21
Page Range:	pp. 179-194
Date:	2004
Publisher:	Brown University
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54871