Crossings and Permutations

Biedl, Therese and Brandenburg, Franz J. and Deng, Xiaotie (2006) Crossings and Permutations. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 1-12(Official URL:

Full text not available from this repository.


We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation pi which minimizes the number of crossings. This is known as the Kemeny optimal aggregation problem minimizing the Kendall-tau distance. Recent interest into this problem comes from application to meta-search and spam reduction on the Web. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. Here we introduce the max-version of the crossing minimization problem, PCM_{max}-k, which attempts to minimize the discrimination against any permutation. We show the NP-hardness of the common and the max version for k >= 4 permutations (and k even), and establish a 2-2/k and a 2-approximation, respectively. For two permutations the problem is solved merely by inspecting the drawings, whereas it remains open for three permutations.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_1
Classifications: G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item