What is "crossing number"

n. (context mathematics English) The minimum, taken over all planar representations of a link or graph, of the number of times it crosses itself.

Crossing number may refer to:

• Crossing number (knot theory) of a knot is the minimal number of crossings in any knot diagram for the knot.
  • The average crossing number is a variant of crossing number obtained from a three-dimensional embedding of a knot by averaging over all two-dimensional projections.
• Crossing number (graph theory) of a graph is the minimal number of edge intersections in any planar representation of the graph.

In graph theory, the crossing number of a graph is the lowest number of edge crossings of a plane drawing of the graph . For instance, a graph is planar if and only if its crossing number is zero.

The mathematical origin of the study of crossing numbers is in Turán's brick factory problem, in which Pál Turán asked to determine the crossing number of the complete bipartite graph , and independently in sociology at approximately the same time, in connection with the construction of sociograms. It continues to be of great importance in graph drawing. As well as complete bipartite graphs, another class of graphs for which a formula for the number of crossings has been conjectured, but not proven, are the complete graphs.

The crossing number inequality states that, for graphs where the number of edges is sufficiently larger than the number of vertices, the crossing number is at least proportional to . 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; 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 points in general position, closely related to the Happy Ending problem.

In the mathematical area of knot theory, the crossing number of a knot is the smallest number of crossings of any diagram of the knot. It is a knot invariant.