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
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).
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. Monthly80,
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. B21, 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.Schaefer, 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.