Crossing Numbers and Crossing Minimization

Definition. The crossing number  cr(G) of a graph G is the minimum number of pairwise edge crossings in a drawing of G in the plane.

Formally, a drawing of a graph G in the plane (more generall, in some surface Sigma) is a mapping of its vertex set V(G) into distinct points of the plane. Edges are mapped into continuous curves between the images of their endvertices and must not contain the image of any non-incident vertex. To resolve ambiguity, we consider drawings of graphs such that no three edges intersect in a common point which is not a vertex. Then a crossing is an intersection point of two edges that is not a vertex.

A drawing with no crossings is a planar embedding.

Long history...

See also the original http://www.planarity.net/, and the much better gPlanarity for Linux.