×

Crossings and permutations. (English) Zbl 1171.68591

Healy, Patrick (ed.) et al., Graph drawing. 13th international symposium, GD 2005, Limerick, Ireland, September 12–14, 2005. Revised papers. Berlin: Springer (ISBN 3-540-31425-3/pbk). Lecture Notes in Computer Science 3843, 1-12 (2006).
Summary: 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, which attempts to minimize the discrimination against any permutation. We show the NP-hardness of the common and the max version for \(k \geq 4\) permutations (and \(k\) even), and establish a 2-2\(/k\) and a 2-approximation, respectively. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.
For the entire collection see [Zbl 1097.68006].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
05C62 Graph representations (geometric and intersection representations, etc.)
05A05 Permutations, words, matrices
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI