Crossing number (graph theory)

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]