NP-completeness of exact crossing number

A series of gradually strengthening results:

In this paper we consider a problem related to questions of optimal circuit layout: Given a graph or network, how can we embed it in a planar surface so as to minimize the number of edge-crossings? We show that this problem is NP-complete, and hence there is not likely to be any efficient way to design an optimal embedding.

Method - reduction from Optimal linear arrangement: An optimal linear arrangement of a finite simple graph G=(V,E) with vertex set V, edge set E, and |V|=N, is a map f from V onto {1,2,…,N} that minimizes ∑_{u,v}E|f(u)−f(v)|.

• Crossing Number is Hard for Cubic Graphs. Petr Hliněný. J. of Combinatorial Theory ser. B 96 (2006), 455-471.

It was proved by [M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 4 (1983) 312-316] that computing the crossing number of a graph is an NP-hard problem. Their reduction, however, used parallel edges and vertices of very high degrees. We prove here that it is NP-hard to determine the crossing number of a simple 3-connected cubic graph. In particular, this implies that the minor-monotone version of the crossing number problem is also NP-hard, which has been open till now.

Again, proved from optimal linear arrangement:

 

• Crossing Number of Graphs with Rotation Systems. Pelsmajer, Schaefer, Štefankovič. Graph Drawing 2007. Preprint 2009.

We show that computing the crossing number and the odd crossing number of a graph with a given rotation system is NP-complete. As a consequence we can show that many of the well-known crossing number notions are NP-complete even if restricted to cubic graphs (with or without rotation system). In particular, we can show that Tutte’s independent odd crossing number is NP-complete, and we obtain a new and simpler proof of Hliněný’s result that computing the crossing number of a cubic graph is NP-complete.

Rotation system = prescribed cyclic permutation of outgoing edges at each vertex.

Again, proved from optimal linear arrangement (now with the use of "heavy" edges):

 

 

More results from [Pelsmajer, Schaefer, Štefankovič]:

Theorem 4.1. Computing the rectilinear crossing number of a cubic graph with or without a given rotation system is NP-hard.

Theorem 4.2. Computing odd or pair crossing number of a cubic, 3-connected graph with or without a given rotation system is NP-complete.

Corollary 4.3. Computing the independent odd crossing number of a graph is NP-complete.

FPT -- tractability of cr(G)<=k for constant k

• Martin Grohe: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2): 285-302 (2004).

Hopcroft and Tarjan [13] showed in 1974 that planarity of graphs can be decided in linear time. It is natural to relax planarity by admitting a small number of edge-crossings in a drawing of the graph. The crossing number of a graph is the minimum number of edge crossings needed in a drawing of the graph into the plane. Not surprisingly, it is NP-complete to decide, given a graph G and a k; whether the crossing number of G is at most k [12]. On the other hand, for every fixed k there is a simple polynomial time algorithm deciding whether a given graph G has crossing number at most k: It guesses lpk pairs of edges that cross1 and tests if the graph obtained from G by adding a new vertex at each of these edge crossings is planar. The running time of this algorithm is n^k: Downey and Fellows [7] raised the question of whether the crossing-number problem is fixed parameter-tractable, that is, whether there is a constant c such that for every fixed k the problem can be solved in time O(n^c): We answer this question positively with c=2: In other words, we show that for every fixed k there is a quadratic time algorithm deciding whether a given graph G has crossing number at most k: Moreover, we show that if this is the case a drawing of G into the plane with at most k crossings can be computed in quadratic time.

• Ken-ichi Kawarabayashi, Bruce A. Reed: Computing crossing number in linear time. STOC 2007: 382-390