Graph Crossing Number

The graph crossing number of a graph is the minimum number of graph crossings over all graph drawings of in the plane, allowing curved graph edges. The minimum can be attained by a good drawing, in which adjacent edges meet only at their common endpoint, independent edges meet at most once and only transversely, and no three edges meet away from vertices (Pan and Richter 2007).

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 2006), and (Schaefer 2026).

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 called a doublecross graph in this work. These terms are summarized in the table below.

Garey and Johnson (1983ab) showed that deciding whether a graph has crossing number at most , with the nonnegative integer part of the input, is an NP-complete problem. Buchheim et al. (2008) used integer programming to formulate a practical 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 drawings, as discussed by Clancy et al. (2019).

The rectilinear crossing number instead minimizes over straight line drawings. 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 simple graph with positive vertex count and edge count . Ajtai et al. (1982) established that the inequality holds for , and the constant was subsequently improved to 1/64 (cf. Clancy et al. 2020).

Harary-Hill 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.

Pan and Richter (2007) found 3080 and 5679 nonisomorphic optimal good drawings of the complete graphs and , respectively. Here, drawings are identified by a homeomorphism of the sphere mapping one to the other and mapping original vertices to original vertices.

Replacing graph crossings by vertices gives a graph planarization.