Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k  -cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ0.878+0.122ρ approximation algorithm for FLCNP, where ρρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family Gn,1/2Gn,1/2, where each edge of the complete graph KnKn occurs with probability 12. We show that a longstanding conjecture for the crossing number of KnKn implies that with probability at least 1-4e-λ21-4e-λ2, the expected performance bound of the algorithm on a random graph from Gn,1/2Gn,1/2 is 1.366+O(λ/n)1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.