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ρ 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 G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 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.