crossingnumber

In graph theory, the crossing number of a graph G, denoted cr(G), is the minimum number of pairwise edge crossings in any drawing of G in the plane. A drawing places vertices as distinct points and edges as curves between them, with the only intersections occurring at common endpoints. Typically, drawings are assumed to have no edge passing through a vertex, and no three edges crossing at the same interior point.

The crossing number is a global measure of how nonplanar a graph is. In particular, cr(G) = 0 if and only if G is planar. For many graphs, the exact crossing number is unknown, and determining cr(G) is computationally challenging.

Two classic small graphs illustrate cr-values: cr(K5) = 1 and cr(K3,3) = 1. These two graphs are nonplanar by Kuratowski’s theorem, and their single necessary crossing in every drawing provides a simple benchmark for the concept.

Computationally, the problem of computing cr(G) is NP-hard, and deciding whether cr(G) ≤ k is NP-complete. This places the exact calculation of crossing numbers among difficult combinatorial optimization problems, though practical heuristics and special-case results are available for various graph families.

For complete graphs Kn, the Harary–Hill conjecture gives a widely cited formula for cr(Kn): cr(Kn) = floor(n/2) · floor((n−1)/2) · floor((n−2)/2) · floor((n−3)/2) / 4. The conjecture is known to hold for small n (up to at least n = 12) and is known to be asymptotically cr(Kn) ~ n^4/64. The exact value for general n remains unproven, although asymptotic bounds are established.

Variants of the problem include the rectilinear crossing number, cr*(G), which minimizes crossings in straight-line drawings; in general cr*(G) ≥ cr(G). Applications appear in graph drawing, VLSI design, and network visualization.