×

zbMATH — the first resource for mathematics

Simple and efficient bilayer cross counting. (English) Zbl 1088.05502
Summary: 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 effecient 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_{\text{small}} |)\) algorithm, where \(V_{\text{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.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Software:
GraphBase
PDF BibTeX XML Cite
Full Text: DOI EuDML EMIS