Given a "good" graph (i.e., one for which all intersectinggraph 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.
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
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).