Graph Crossing Number

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.

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.