Simple and Efficient Bilayer Cross Counting (Journal Version)

Barth, Wilhelm and Mutzel, Petra and Jünger, Michael (2004) Simple and Efficient Bilayer Cross Counting (Journal Version).
Published in: Journal of Graph Algorithms and Applications Vol. 8 (21). pp. 179-194.

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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (401kB) | Preview
Download: [img] PDF - Preprinted Version
Download (680kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • Additional Information: This is a revised and extended version of report zaik2002-433
    Uncontrolled Keywords: cross counting, graph drawing, layered layout
    Subjects: 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 01 Dec 2003 00:00
    Last Modified: 12 Jan 2012 10:50
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 01 Dec 2003 00:00
    Last Modified: 12 Jan 2012 10:50
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/449