Graph Crossing Number

The graph crossing number of a "good" graph (i.e., one for which all intersecting graph edges intersect in a single point and arise from four distinct graph vertices) is the minimum possible number of crossings with which the graph can be drawn, including using curved (non-rectilinear) graph edges. Several notational conventions exist in the literature, with some of the more common being (e.g., Pan and Richter 2007; Clancy et al. 2020), (Pach and Tóth 2000b), (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 graph" and "1-planar graph" 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 programming to formulate the first exact algorithm to find provably optimal crossing numbers. Chimani et al. (2008) subsequently gave an integer programming formulation based on Kuratowski constraints that can be practically efficient for instances with crossing number up to 37. Their implementation computes a crossing number using branch-and-cut-and-price based on Buchheim et al. (2008), Chimani et al. (2008), 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 graph embeddings, as discussed by Clancy et al. (2018).

The rectilinear crossing number instead minimizes over straight line embeddings. A graph for which is called a curvy graph in this work.

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. 2020).

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.