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.

[img]
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:
CreatorsEmailORCIDORCID Put Code
Barth, WilhelmUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Mutzel, PetraUNSPECIFIEDorcid.org/0000-0001-7621-971XUNSPECIFIED
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

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item