Universität zu Köln

Barth, Wilhelm, Jünger, Michael and Mutzel, Petra ORCID: 0000-0001-7621-971X (2002). Simple and Efficient Bilayer Cross Counting. In: Graph drawing : 10th international symposium, GD 2002, Irvine, CA, USA, August 26 - 28, 2002 ; revised papers, pp. 331-360. Springer.

Preview

PDF zaik2002-433.pdf - Submitted Version Download (221kB) | 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 on two parallel lines and the edges are straight lines. 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(|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. We present the algorithms and the results of computational experiments with these and other algorithms on a large collection of instances.

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Barth, Wilhelm UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED orcid.org/0000-0001-7621-971X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548638
Title of Book:	Graph drawing : 10th international symposium, GD 2002, Irvine, CA, USA, August 26 - 28, 2002 ; revised papers
Series Name:	Lecture notes in computer science
Volume:	2528
Page Range:	pp. 331-360
Date:	2002
Publisher:	Springer
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/54863