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. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.^[1]

The study of crossing numbers originated in Turán's brick factory problem, in which Pál Turán asked for a factory plan that minimized the number of crossings between tracks connecting brick kilns to storage sites. Mathematically, this problem can be formalized as asking for the crossing number of a complete bipartite graph.^[2] The same problem arose independently in sociology at approximately the same time, in connection with the construction of sociograms.^[3] Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous formula for the complete graphs.

The crossing number inequality states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e³/n². It has applications in VLSI design and incidence geometry.

Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, the rectilinear crossing number, requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of n points in general position. The problem of determining this number is closely related to the happy ending problem.^[4]

For the purposes of defining the crossing number, a drawing of an undirected graph is a mapping from the vertices of the graph to disjoint points in the plane, and from the edges of the graph to curves connecting their two endpoints. No vertex should be mapped onto an edge that it is not an endpoint of, and whenever two edges have curves that intersect (other than at a shared endpoint) their intersections should form a finite set of proper crossings, where the two curves are transverse. A crossing is counted separately for each of these crossing points, for each pair of edges that cross. The crossing number of a graph is then the minimum, over all such drawings, of the number of crossings in a drawing.^[5]

Some authors add more constraints to the definition of a drawing, for instance that each pair of edges have at most one intersection point (a shared endpoint or crossing). For the crossing number as defined above, these constraints make no difference, because a crossing-minimal drawing cannot have edges with multiple intersection points. If two edges with a shared endpoint cross, the drawing can be changed locally at the crossing point, leaving the rest of the drawing unchanged, to produce a different drawing with one fewer crossing. And similarly, if two edges cross two or more times, the drawing can be changed locally at two crossing points to make a different drawing with two fewer crossings. However, these constraints are relevant for variant definitions of the crossing number that, for instance, count only the numbers of pairs of edges that cross rather than the number of crossings.^[5]

As of April 2015, crossing numbers are known for very few graph families. In particular, except for a few initial cases, the crossing number of complete graphs, bipartite complete graphs, and products of cycles all remain unknown, although there has been some progress on lower bounds.^[6]

The 2/3-bisection width ${\displaystyle b(G)}$ of a simple graph ${\displaystyle G}$ is the minimum number of edges whose removal results in a partition of the vertex set into two separated sets so that no set has more than ${\displaystyle 2n/3}$vertices. Computing ${\displaystyle b(G)}$ is NP-hard. Leighton proved that ${\displaystyle cr(G)+n=\Omega (b^{2}(G))}$, provided that ${\displaystyle G}$ has bounded vertex degrees.^[18] This fundamental inequality can be used to derive an asymptotic lower bound for ${\displaystyle cr(G)}$, when ${\displaystyle b(G)}$, or an estimate of it is known. In addition, this inequality has algorithmic application. Specifically, Bhat and Leighton used it (for the first time) for deriving an upper bound on the number of edge crossings in a drawing which is obtained by a divide and conquer approximation algorithm for computing ${\displaystyle cr(G)}$.^[19]

In general, determining the crossing number of a graph is hard; Garey and Johnson showed in 1983 that it is an NP-hard problem.^[20] In fact the problem remains NP-hard even when restricted to cubic graphs^[21] and to near-planar graphs (graphs that become planar after removal of a single edge).^[22] A closely related problem, determining the rectilinear crossing number, is complete for the existential theory of the reals.^[23]

On the positive side, there are efficient algorithms for determining whether the crossing number is less than a fixed constant k. In other words, the problem is fixed-parameter tractable.^[24][25] It remains difficult for larger k, such as k = |V|/2. There are also efficient approximation algorithms for approximating ${\displaystyle cr(G)+n}$ on graphs of bounded degree^[26] which use the general and previously developed framework of Bhat and Leighton.^[19] In practice heuristic algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. These algorithms are used in the Rectilinear Crossing Number distributed computing project.^[27]

For an undirected simple graph G with n vertices and e edges such that e > 7n the crossing number is always at least

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

This relation between edges, vertices, and the crossing number was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi,^[28] and by Leighton .^[18] It is known as the crossing number inequality or crossing lemma.

The constant 29 is the best known to date, and is due to Ackerman.^[29] The constant 7 can be lowered to 4, but at the expense of replacing 29 with the worse constant of 64.^[28][18]

The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science.^[18] Later, Székely also realized that this inequality yielded very simple proofs of some important theorems in incidence geometry, such as Beck's theorem and the Szemerédi-Trotter theorem,^[30] and Tamal Dey used it to prove upper bounds on geometric k-sets.^[31]

If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings. The rectilinear crossing number is defined to be the minimum number of crossings of a drawing of this type. It is always at least as large as the crossing number, and is larger for some graphs. It is known that, in general, the rectilinear crossing number can not be bounded by a function of the crossing number.^[32] The rectilinear crossing numbers for K₅ through K₁₂ are 1, 3, 9, 19, 36, 62, 102, 153, (A014540) and values up to K₂₇ are known, with K₂₈ requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.^[27]

A graph has local crossing number k if it can be drawn with at most k crossings per edge, but not fewer. The graphs that can be drawn with at most k crossings per edge are also called k-planar.^[33]

Other variants of the crossing number include the pairwise crossing number (the minimum number of pairs of edges that cross in any drawing) and the odd crossing number (the number of pairs of edges that cross an odd number of times in any drawing). The odd crossing number is at most equal to the pairwise crossing number, which is at most equal to the crossing number. However, by the Hanani–Tutte theorem, whenever one of these numbers is zero, they all are.^[5] Schaefer (2014, 2018) surveys many such variants.^[34][35]

• Planarization, a planar graph formed by replacing each crossing by a new vertex
• Three utilities problem, the puzzle that asks whether K_3,3 can be drawn with 0 crossings