×

Counting edge crossings in a 2-layered drawing. (English) Zbl 1192.68489

Summary: Given a bipartite graph \(G=(V,W,E)\) with a bipartition \(\{V,W\}\) of a vertex set and an edge set \(E\), a 2-layered drawing of \(G\) in the plane means that the vertices of \(V\) and \(W\) are respectively drawn as distinct points on two parallel lines and the edges as straight line segments. We consider the problem of counting the number of edge crossings. In this paper, we design two algorithms to this problem based on the dynamic programming and divide-and-conquer approaches. These algorithms run in \(O(n_{1}n_{2})\) time and \(O(m)\) space and in O\((\min\{n_{1}n_{2},|E|\log (\min\{|V|,|W|\})\})\) time and \(O(m)\) space, respectively. Our algorithms outperform the previously fastest \(\Theta (|E|\log (\min\{|V|,|W|\}))\) time algorithm for dense graphs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI

References:

[1] Barth, W.; Jünger, M.; Mutzel, P., Simple and efficient bilayer cross counting, (Lecture Notes in Comput. Sci., vol. 2528 (2002), Springer: Springer Berlin), 130-141 · Zbl 1037.68564
[2] Eades, P.; Wormald, N. C., Edge crossing in drawing bipartite graphs, Algorithmica, 11, 379-403 (1994) · Zbl 0804.68107
[3] Jünger, M.; Mutzel, P., 2-layer straight line crossing minimization: performance of exact and heuristic algorithms, J. Graph Algorithms Appl., 1, 1-25 (1997) · Zbl 0906.05068
[4] Sugiyama, K., Graph Drawing and Applications: For Software and Knowledge Engineerings, (Chang, S. K., Series of Software Engineering and Knowledge Engineering, vol. 11 (2002), World Scientific: World Scientific Singapore) · Zbl 1011.68068
[5] Sugiyama, K.; Tagawa, S.; Toda, M., Methods for visual understanding of hierarchical system structures, IEEE Transactions on Systems, Man, and Cybernetics, 11, 109-125 (1981)
[6] Waddle, V.; Malhotra, A., An \(E\) log \(E\) line crossing algorithm for levelled graphs, (Lecture Notes in Comput. Sci., vol. 1731 (1999), Springer: Springer Berlin), 59-70
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.