# How to Prove NP-Completeness of Minimum Crossing Problem?

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. (from wikipedia)

I know that the problem of counting the Crossing Number of a graph to be less than or equal to K is proven to be NP-Complete by Garey and Johnson in 1983. I couldn't find the actual proof papers though.

So, what is the proof idea?

One way would be to reduce (in polynomial time) from some known NPC problem but to which one?

• The original paper is here: epubs.siam.org/doi/abs/10.1137/0604033. You can pay a bit if you want to see it. Otherwise, take a look at arxiv.org/pdf/1204.0660.pdf, which gives a hardness of approximation proof, and links to several NP-hardness proofs which are available online for free. Jul 10 '15 at 13:39

Here is a short summary of the original paper. More modern treatments can be found in a paper of Cabello proving a hardness of approximation result. We are concerned with three different problems:

CROSSING NUMBER: Given a graph $G$ and a number $K$, can it be drawn with at most $K$ crossings?

BIPARTITE CROSSING NUMBER: Given a connected bipartite graph $G$ and a number $K$, can it be drawn in the unit square so that vertices of one part are on the top side, vertices of the other part are on the bottom side, all edges are within the square, and there are at most $K$ crossings?

OPTIMAL LINEAR ARRANGEMENT: Given a graph $G$ and a number $K$, can we arrange the vertices of $G$ in a line so that the total length of all edges is at most $K$.

The latter is known to be NP-complete. The reduction is from OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER, and then from BIPARTITE CROSSING NUMBER to CROSSING NUMBER.

There are several variants of the concept of crossing number, and the one meant here can be gleaned from the proof that crossing number is in NP: given a graph $G$ and a number $K$, to show that the crossing number is at most $K$, identify up to $K$ pairs of crossing edges, for each one introduce a new vertex, and add the appropriate edges so that the resulting graph becomes planar; planarity can be tested in polynomial (indeed, linear) time.

OPTIMAL LINEAR ARRANGEMENT to BIPARTITE CROSSING NUMBER: Given an instance $G=(V,E),K$ of OPTIMAL LINEAR ARRANGEMENT, we construct an instance of BIPARTITE CROSSING NUMBER as follows:

• For each $v \in G$, we include two vertices $v_1,v_2$ on opposite bipartitions, and $|E|^2$ copies of the edge $(v_1,v_2)$.
• Fix some ordering of $V$. For each $(x,y) \in E$ such that $x < y$, include the edge $(x_1,y_2)$.
• Set the new $K$ to be $|E|^2(K-|E|) + |E|^2 - 1$.

Given a good arrangement $A$ of the vertices in $V$, the intended drawing of the new graph has both copies of $V$ equally spaced and ordered according to $A$, with edges $(v_1,v_2)$ being vertical (but slightly fanned so that they don't cross each other) and the "real" edges being straight. A "real" edge spanning a stretch of $\ell$ crosses $(\ell-1)|E|^2$ vertical edges, for a total of $(K-|E|)|E|^2$ crossings. There are also at most $\binom{|E|}{2} \leq < |E|^2$ crossings between "real" edges.

Conversely, any drawing of the new graph with fewer than $|E|^4$ crossings must be of the form above (due to the vertical edges), and so we can read off a good arrangement of the original graph.

BIPARTITE CROSSING NUMBER to CROSSING NUMBER: Given an instance $G=(V_1,V_2,E),K$ of BIPARTITE CROSSING NUMBER, we construct an instance of CROSSING NUMBER as follows:

• We take all vertices in $V_1,V_2$ along with two special vertices $o_1,o_2$.
• We include all original edges.
• We connect $o_i$ to each vertex in $V_i$ using $3K+1$ edges (for $i=1,2$).
• We connect $o_1$ and $o_2$ using $3K+1$ edges.
• We use the same $K$.

Given a good drawing of the original graph, we draw the new graph by putting $o_1$ above $V_1$, $o_2$ below $V_2$, the edges from $o_i$ to $V_i$ are (almost) straight, and the edges connecting $o_1$ and $o_2$ go around the entire construction. This adds no new crossings.

In the other direction, we show that every good embedding of the new graph must be of this form, in a step by step fashion, completing the proof. I'm leaving this part to the reader.