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.

REFERENCES

Ajtai, M.; Chvátal, V.; Newborn, M. M.; and Szemeréedi, E. "Crossing-Free Subgraphs." North-Holland Math. Stud. 60(C), 9-12, 1982.

Bienstock, D. and Dean, N. "Bounds for Rectilinear Crossing Numbers." J. Graph Th. 17, 333-348, 1993.

Buchheim, C.; Chimani, M.; Ebner, D.; Gutwenger, C.; Jünger, M.; Klau, G. W.; Mutzel, P.; and Weiskircher, R. "A Branch-And-Cut Approach to the Crossing Number Problem." Discr. Optimiz. 5, 373-388, 2008.

Chimani, M.; Mutzel, P.; and Bomze, I. "A New Approach to Exact Crossing Minimization." http://ls11-www.cs.tu-dortmund.de/people/chimani/files/oocm-preprint.pdf.Chimani, M. and Wiedera, T. "Crossing Number Web Compute." http://crossings.uos.de.Clancy, K.; Haythorpe, M.; and Newcombe, A. "An Effective Crossing Minimisation Heuristic Based on Star Insertion." Submitted to J. Graph Algorithms and Applications. http://arxiv.org/abs/1804.09900.Clancy, K.; Haythorpe, M.; and Newcombe, A. "A Survey of Graphs with Known or Bounded Crossing Numbers." 15 Feb 2019.

https://arxiv.org/abs/1901.05155.Erdős, P. and Guy, R. K. "Crossing Number Problems." Amer. Math. Monthly 80, 52-57, 1973.

Exoo, G. "Rectilinear Drawings of Famous Graphs." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/.Gardner, M. "Crossing Numbers." Ch. 11 in Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, pp. 133-144, 1986.

Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 339, 1983a.

Garey, M. R. and Johnson, D. S. "Crossing Number is NP-Complete." SIAM J. Alg. Discr. Meth. 4, 312-316, 1983b.

Guy, R. K. "Latest Results on Crossing Numbers." In Recent Trends in Graph Theory, Proc. New York City Graph Theory Conference, 1st, 1970 (Ed. New York City Graph Theory Conference Staff). New York: Springer-Verlag, 1971.

Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.

Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.

Haythorpe, M. "QuickCross--Crossing Number Problem." http://www.flinders.edu.au/science_engineering/csem/research/programs/flinders-hamiltonian-cycle-project/quickcross.cfm.Kleitman, D. J. "A Note on the Parity of the Numbers of Crossings of a Graph." J. Combin. Th., Ser. B 21, 88-89, 1976.

Koman, M. "Extremal Crossing Numbers of Complete -Chromatic Graphs." Mat. Časopis Sloven. Akad. Vied. 20, 315-325, 1970.

Moon, J. W. "On the Distribution of Crossings in Random Complete Graphs." SIAM J. 13, 506-510, 1965.

Owens, A. "On the Biplanar Crossing Number." IEEE Trans. Circuit Th. 18, 277-280, 1971.Pach, J. and Tóth, G. "Thirteen Problems on Crossing Numbers." Geocombin. 9, 195-207, 2000.S

chaefer, M. "The Graph Crossing Number and its Variants: A Survey." Elec. J. Combin., DS21, Version 3, Dec. 22, 2017.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 251, 1990.

Sloane, N. J. A. Sequence A014540 in "The On-Line Encyclopedia of Integer Sequences."Thomassen, C. "Embeddings and Minors." In Handbook of Combinatorics, 2 vols. (Ed. R. L. Graham, M. Grötschel, and L. Lovász.) Cambridge, MA: MIT Press, p. 314, 1996.

Tutte, W. T. "Toward a Theory of Crossing Numbers." J. Comb. Th. 8, 45-53, 1970.

Vrt'o, I. "Crossing Numbers of Graphs: A Bibliography." Jan. 15, 2014. 

ftp://ftp.ifi.savba.sk/pub/imrich/crobib.pdf.Wilf, H. "On Crossing Numbers, and Some Unsolved Problems." In Combinatorics, Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference in Honor of Paul Erdős's 80th Birthday Held at Trinity College, Cambridge, March 1993 

(Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997.