Given a "good" graph (i.e., one for which all intersecting graph edges intersect in a single point and arise from
four distinct graph vertices), the crossing number
is the minimum possible number of crossings with which the graph
can be drawn, including using curved (non-rectilinear) edges. Several notational
conventions exist in the literature, with some of the more common being (e.g., Pan and Richter 2007; Clancy *et al. *2019),
,
(e.g., Pach and Tóth 2005), and .

A graph with crossing number 0 is known as a planar graph. There appears to be no term in standard use for a graph with graph crossing number 1. In particular, the terms "almost planar" and "1-planar" are used in the literature for other concepts. Therefore, in this work, the term singlecross graph will be used for a graph with crossing number 1. A graph with crossing number 2 is known as a doublecross graph. These terms are summarized in the table below.

crossing number | term |

0 | planar graph |

1 | singlecross graph |

2 | doublecross graph |

Garey and Johnson (1983ab) showed that determining the crossing number is an NP-complete problem. Buchheim *et al. *(2008) used integer linear programming to formulate
the first exact algorithm to find provably optimal crossing numbers. Chimani *et
al. *subsequently gave an integer linear programming formulation that can be practically
efficient up to crossing number 37 which attempts to find a crossing number deterministically
via branch-and-cut-and-price based on Buchheim *et al. *(2008), Chimani *et
al. *, and related work by the authors. The authors provide a web form requesting
application of this algorithm to submitted graphs (Chimani and Wiedera). In contrast,
Haythorpe and colleagues implemented a fast heuristic known as QuickCross which is
designed to find optimal or near-optimal embeddings of graphs, as discussed by Clancy
*et al. *(2018), and available for download.

While the graph crossing number allows graph embeddings with arbitrarily-shaped edges (e.g,. curves), the rectilinear crossing number is the minimal possible number of crossings in a straight line embedding of a graph. When the (non-rectilinear) graph crossing number satisfies , (Bienstock and Dean 1993). While Bienstock and Dean don't actually prove the case , they state it can be established analogously to . The result cannot be extended to , since there exist graphs with but for any .

Ajtai *et al. *(1982) showed that there is an absolute constant such that

for every graph with vertex count and edge count . Ajtai *et al. *(1982) established that the inequality
holds for ,
and subsequently improved to 1/64 (cf. Clancy *et al. *2019).

Guy's conjecture posits a closed form for the crossing number of the complete graph and Zarankiewicz's conjecture proposes one for the complete bipartite graph . A conjectured closed form for the crossing number of the torus grid graph has also been proposed.