Simple and Efficient Bilayer Cross Counting

Barth, Wilhelm and Jünger, Michael and Mutzel, Petra (2002) Simple and Efficient Bilayer Cross Counting. [Preprint]

WarningThere is a more recent version of this item available.

[img]
Preview
 Postscript - Requires a viewer, such as GSview
317Kb

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:Preprint
Classifications:M Methods > M.500 Layered
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:11
Alternative Locations:http://e-archive.informatik.uni-koeln.de/433/

Available Versions of this Item

Repository Staff Only: item control page

References

Chazelle, B. (1986) Reporting and counting segment intersections. Journal of Computer and System Sciences, 32 156-182.

Chazelle, B. and Edelsbrunner, H. (1992) An optimal algorithm for intersecting line segments in the plane. Journal of the ACM, 39 1-54.

Cormen, T. H. and Leiserson, C. E. and Rivest, R. L. (1990) Introduction to algorithms. MIT Press, Cambridge, MA.

Eades, P. and Wormald, N. (1994) Edge crossings in drawings of bipartite graphs. Algorithmica, 11 379-403.

Gutwenger, C. and Jünger, M. and Klau, G. W. and Leipert, S. and Mutzel, P. (2002). In: S. Diehl (ed.) Graph Drawing Algorithm Engineering with AGD, Sortware Visualization, International Dagstuhl Seminar on Software Visualization 2001, Lecture Notes on Computer Science 2269, Springer, 2002, pp. 307-323, see also: http://www.mpi-sb.mpg.de/AGD/

Jünger, M. and Mutzel, P. (1997) 2-layer straight line crossing minimization: perfomance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications, 1 1-25.

Knuth, D. E. (1993) The Stanford GraphBase: A platform for combinatiorial computing. Addison-Wesley, Reading, Massachusetts.

Lueker, G. S. (1978) A data structure for orthogonal range queries. Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pp. 28-34.

Sander, G. (1995) Graph Layout through the VCG Tool. In: R. Tamassia and I.G. Tollis (eds.) Graph Drawing 1994, Lecture Notes in Computer Science 894, Springer, pp. 194-205, see also: http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html

Sander, G (1996) Visualisierungstechniken für den Compilerbau. Pirrot Verlag & Druck, Saarbrücken.

Sugiyama, K. and Tagawa, S. and Toda, M. (1981) Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11 109-125.

Waddle, V. and Malhotra, A. (1999) An E log E line crossing algorithm for levelled graphs. In: J. Kratochvil (ed.) Graph Drawing 1999, Lecture Notes in Computer Science 1731, Springer, pp. 59-70.