View source for Crossing number (graph theory)

You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 3.92.0.0/16 has been blocked by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: {{unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~}}. You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 07:24, 6 August 2027. Your current IP address is 3.92.33.243.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
This IP address range has been globally blocked.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

This block affects editing on all Wikimedia wikis.
The IP address or range 3.92.0.0/16 has been globally blocked by ‪Jon Kolbert‬ for the following reason(s):

Open proxy/Webhost: See the help page if you are affected

This block will expire on 05:35, 21 February 2029. Your current IP address is 3.92.33.243.

Even while globally blocked, you will usually still be able to edit pages on Meta-Wiki.

If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

Other useful links: Global blocks · Help:I have been blocked

You can view and copy the source of this page:

{{short description|Fewest edge crossings in drawing of a graph}}
[[File:3-crossing Heawood graph.svg|thumb|A drawing of the [[Heawood graph]] with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number {{math|cr(''G'') {{=}} 3}}.]]

In [[graph theory]], the '''crossing number''' {{math|cr(''G'')}} of a [[Graph (discrete mathematics)|graph]] {{mvar|G}} is the lowest number of edge crossings of a plane [[graph drawing|drawing]] of the graph {{mvar|G}}. For instance, a graph is [[planar graph|planar]] if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.{{r|pcj}}

The study of crossing numbers originated in [[Turán's brick factory problem]], in which [[Pál Turán]] asked for a factory plan that minimized the number of crossings between tracks connecting brick kilns to storage sites. Mathematically, this problem can be formalized as asking for the crossing number of a [[complete bipartite graph]].{{r|turan}} The same problem arose independently in [[sociology]] at approximately the same time, in connection with the construction of [[sociogram]]s.{{r|bron}} Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous formula for the [[complete graph]]s.

The [[crossing number inequality]] states that, for graphs where the number {{mvar|e}} of [[Edge (graph theory)|edges]] is sufficiently larger than the number {{mvar|n}} of [[Vertex (graph theory)|vertices]], the crossing number is at least [[Proportionality (mathematics)|proportional]] to {{math|''e''{{sup|3}}/''n''{{sup|2}}}}. It has applications in [[VLSI]] design and [[incidence geometry]].

Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, the '''rectilinear crossing number''', requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a [[complete graph]] is essentially the same as the minimum number of [[convex polygon|convex]] [[quadrilaterals]] determined by a set of {{mvar|n}} points in general position. The problem of determining this number is closely related to the [[happy ending problem]].{{r|sw}}

==Definitions==
For the purposes of defining the crossing number, a drawing of an [[undirected graph]] is a mapping from the vertices of the graph to disjoint points in the plane, and from the edges of the graph to curves connecting their two endpoints. No vertex should be mapped onto an edge that it is not an endpoint of, and whenever two edges have curves that intersect (other than at a shared endpoint) their intersections should form a finite set of proper crossings, where the two curves are [[Transversality (mathematics)|transverse]]. A crossing is counted separately for each of these crossing points, for each pair of edges that cross. The crossing number of a graph is then the minimum, over all such drawings, of the number of crossings in a drawing.{{r|which}}

Some authors add more constraints to the definition of a drawing, for instance that each pair of edges have at most one intersection point (a shared endpoint or crossing). For the crossing number as defined above, these constraints make no difference, because a crossing-minimal drawing cannot have edges with multiple intersection points. If two edges with a shared endpoint cross, the drawing can be changed locally at the crossing point, leaving the rest of the drawing unchanged, to produce a different drawing with one fewer crossing. And similarly, if two edges cross two or more times, the drawing can be changed locally at two crossing points to make a different drawing with two fewer crossings. However, these constraints are relevant for variant definitions of the crossing number that, for instance, count only the numbers of pairs of edges that cross rather than the number of crossings.{{r|which}}

==Special cases==
As of April 2015, crossing numbers are known for very few graph families. In particular, except for a few initial cases, the crossing number of complete graphs, bipartite complete graphs, and products of cycles all remain unknown, although there has been some progress on lower bounds.{{r|kmprs}}

===Complete bipartite graphs===
[[File:Zarankiewicz K4 7.svg|thumb|An optimal drawing of {{math|''K''<sub>4,7</sub>}} showing that Turán's brick factory problem with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots)]]
{{main|Turán's brick factory problem}}
During [[World War II]], Hungarian mathematician [[Pál Turán]] was forced to work in a brick factory, pushing wagon loads of bricks from kilns to storage sites. The factory had tracks from each kiln to each storage site, and the wagons were harder to push at the points where tracks crossed each other, from which Turán was led to ask his brick factory problem: how can the kilns, storage sites, and tracks be arranged to minimize the total number of crossings? Mathematically, the kilns and storage sites can be formalized as the vertices of a [[complete bipartite graph]], with the tracks as its edges. A factory layout can be represented as a drawing of this graph, so the problem becomes:
what is the minimum possible number of crossings in a drawing of a [[complete bipartite graph]]?{{r|ps}}

[[Kazimierz Zarankiewicz]] attempted to solve Turán's brick factory problem;{{r|z}} his proof contained an error, but he established a valid [[Upper and lower bounds|upper bound]] of

:<math>\textrm{cr}(K_{m,n}) \le \left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{m}{2}\right\rfloor\left\lfloor\frac{m-1}{2}\right\rfloor</math>

for the crossing number of the complete bipartite graph {{mvar|K<sub>m,n</sub>}}. This bound has been conjectured to be the optimal number of crossings for all complete bipartite graphs.{{r|fall}}

===Complete graphs and graph coloring===
The problem of determining the crossing number of the [[complete graph]] was first posed by [[Anthony Hill (artist)|Anthony Hill]], and appeared in print in 1960.{{r|nabla}} Hill and his collaborator [[John Ernest]] were two [[Constructivism (art)|constructionist artists]] fascinated by mathematics. They not only formulated this problem but also originated a conjectural formula for this crossing number, which [[Richard K. Guy]] published in 1960.{{r|nabla}} Namely, it is known that there always exists a drawing with
:<math>\textrm{cr}(K_p) \le \frac{1}{4} \left\lfloor\frac{p}{2}\right\rfloor\left\lfloor\frac{p-1}{2}\right\rfloor\left\lfloor\frac{p-2}{2}\right\rfloor\left\lfloor\frac{p-3}{2}\right\rfloor</math>
crossings. This formula gives values of {{math|1, 3, 9, 18, 36, 60, 100, 150, 225, 315}} for {{math|''p'' {{=}} 5, ..., 14}}; see sequence {{OEIS link|A000241}} in the [[On-line Encyclopedia of Integer Sequences]].
The conjecture is that there can be no better drawing, so that this formula gives the optimal number of crossings for the complete graphs. An independent formulation of the same conjecture was made by [[Thomas L. Saaty]] in 1964.{{r|pnas}}

Saaty further verified that this formula gives the optimal number of crossings for {{math|''p'' ≤ 10}} and Pan and Richter showed that it also is optimal for {{math|''p'' {{=}} 11, 12}}.{{r|pr}}

The [[Albertson conjecture]], formulated by Michael O. Albertson in 2007, states that, among all graphs with [[chromatic number]] {{mvar|n}}, the complete graph {{mvar|K<sub>n</sub>}} has the minimum number of crossings. That is, if the conjectured formula for the crossing number of the complete graph is correct, then every {{mvar|n}}-chromatic graph has crossing number at least equal to the same formula. The Albertson conjecture is now known to hold for {{math|''n'' ≤ 16}}.{{r|bt}}

===Cubic graphs===
The smallest [[cubic graph]]s with crossing numbers 1–8 and 11 are known {{OEIS|id=A110507}}. The smallest 1-crossing cubic graph is the [[complete bipartite graph]] {{math|''K''<sub>3,3</sub>}}, with 6 vertices. The smallest 2-crossing cubic graph is the [[Petersen graph]], with 10 vertices. The smallest 3-crossing cubic graph is the [[Heawood graph]], with 14 vertices. The smallest 4-crossing cubic graph is the [[Möbius-Kantor graph]], with 16 vertices. The smallest 5-crossing cubic graph is the [[Pappus graph]], with 18 vertices. The smallest 6-crossing cubic graph is the [[Desargues graph]], with 20 vertices. None of the four 7-crossing cubic graphs, with 22 vertices, are well known.{{r|mathworld}} The smallest 8-crossing cubic graphs include the [[Nauru graph]] and the [[McGee graph]] or (3,7)-[[cage graph]], with 24 vertices.{{r|pe}} The smallest 11-crossing cubic graphs include the [[Coxeter graph]] with 28 vertices.{{r|hn}}

In 2009, Pegg and Exoo conjectured that the smallest cubic graph with crossing number 13 is the [[Tutte–Coxeter graph]] and the smallest cubic graph with crossing number 170 is the [[Tutte 12-cage]].{{r|pe|exoo}}

== Connections to the bisection width ==
The 2/3-bisection width <math>b(G)</math> of a simple graph <math>G</math> is the minimum number of edges whose removal results in a partition of the vertex set into two separated sets so that no  set has  more than <math>2n/3</math>vertices. Computing <math>b(G)</math> is NP-hard. [[F. Thomson Leighton|Leighton]] proved that <math> cr(G)+n=\Omega(b^2(G))</math>, provided that <math>G</math> has bounded vertex degrees.{{r|leighton}}  This fundamental inequality can be used to derive an asymptotic lower bound for <math>cr(G)</math>, when <math>b(G)</math>, or an estimate of it is known. In addition, this inequality has algorithmic application. Specifically, Bhat and Leighton used it (for the first time) for deriving an upper bound on the number of edge crossings in a drawing which is obtained by a divide and conquer  approximation algorithm for computing <math>cr(G)</math>.{{r|BL}}  

==Complexity and approximation==
In general, determining the crossing number of a graph is hard; [[Michael Garey|Garey]] and [[David S. Johnson|Johnson]] showed in 1983 that it is an [[NP-hard]] problem.{{r|gj}} In fact the problem remains NP-hard even when restricted to [[cubic graph]]s{{r|hlineny}} and to near-planar graphs (graphs that become planar after removal of a single edge).{{r|cm}} A closely related problem, determining the rectilinear crossing number, is [[Complete (complexity)|complete]] for the [[existential theory of the reals]].{{r|ER}}

On the positive side, there are efficient algorithms for determining whether the crossing number is less than a fixed constant {{mvar|k}}. In other words, the problem is [[fixed-parameter tractable]].{{r|grohe|kr}} It remains difficult for larger {{mvar|k}}, such as {{math|1=''k'' = {{!}}''V''{{!}}/2}}. There are also efficient [[approximation algorithm]]s for approximating <math>cr(G)+n </math> on graphs of bounded degree{{r|egs}} which use the general and previously developed framework of Bhat and Leighton.{{r|BL}} In practice [[heuristic]] algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. These algorithms are used in the Rectilinear Crossing Number [[distributed computing]] project.{{r|rcnp}}

==The crossing number inequality==
{{main|Crossing number inequality}}
For an undirected [[simple graph]] {{mvar|G}} with {{mvar|n}} vertices and {{mvar|e}} edges such that {{math|''e'' > 7''n''}} the crossing number is always at least
::<math>\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.</math>

This relation between edges, vertices, and the crossing number was discovered independently by [[Miklós Ajtai|Ajtai]], [[Václav Chvátal|Chvátal]], Newborn, and [[Endre Szemerédi|Szemerédi]],{{r|acns}} and by Leighton .{{r|leighton}} It is known as the [[crossing number inequality]] or crossing lemma.

The constant {{math|29}} is the best known to date, and is due to Ackerman.{{r|ackerman}} The constant {{math|7}} can be lowered to {{math|4}}, but at the expense of replacing {{math|29}} with the worse constant of {{math|64}}.{{r|acns|leighton}}

The motivation of Leighton in studying crossing numbers was for applications to [[VLSI]] design in theoretical computer science.{{r|leighton}}  Later, Székely also realized that this inequality yielded very simple proofs of some important theorems in [[Incidence (geometry)|incidence geometry]], such as [[Beck's theorem (geometry)|Beck's theorem]] and the [[Szemerédi-Trotter theorem]],{{r|szekely}} and [[Tamal Dey]] used it to prove upper bounds on [[K-set (geometry)|geometric ''k''-sets]].{{r|dey}}

==Variations==
If edges are required to be drawn as straight line segments, rather than arbitrary curves, then some graphs need more crossings. The '''rectilinear crossing number''' is defined to be the minimum number of crossings of a drawing of this type. It is always at least as large as the crossing number, and is larger for some graphs. It is known that, in general, the rectilinear crossing number can not be bounded by a function of the crossing number.<ref>{{Cite journal |last1=Bienstock |first1=Daniel |last2=Dean |first2=Nathaniel |date=July 1993 |title=Bounds for rectilinear crossing numbers |url=https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190170308 |journal=Journal of Graph Theory |language=en |volume=17 |issue=3 |pages=333–348 |doi=10.1002/jgt.3190170308}}</ref> The rectilinear crossing numbers for {{math|''K''<sub>5</sub>}} through {{math|''K''<sub>12</sub>}} are {{math|1, 3, 9, 19, 36, 62, 102, 153}}, ({{OEIS link|A014540}}) and values up to {{math|''K''<sub>27</sub>}} are known, with {{math|''K''<sub>28</sub>}} requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.{{r|rcnp}}

A graph has [[1-planar graph|local crossing number]] {{mvar|k}} if it can be drawn with at most {{mvar|k}} crossings per edge, but not fewer.
The graphs that can be drawn with at most {{mvar|k}} crossings per edge are also called {{mvar|k}}-planar.{{r|ringel}}

Other variants of the crossing number include the '''pairwise crossing number''' (the minimum number of pairs of edges that cross in any drawing) and the '''odd crossing number''' (the number of pairs of edges that cross an odd number of times in any drawing). The odd crossing number is at most equal to the pairwise crossing number, which is at most equal to the crossing number. However, by the [[Hanani–Tutte theorem]], whenever one of these numbers is zero, they all are.{{r|which}} {{harvs|last=Schaefer|year=2014|year2=2018|txt}} surveys many such variants.{{r|variants|book}}

==See also==
*[[Planarization]], a planar graph formed by replacing each crossing by a new vertex
*[[Three utilities problem]], the puzzle that asks whether {{math|''K''<sub>3,3</sub>}} can be drawn with 0 crossings

==References==
{{Reflist|30em|refs=

<ref name=BL>{{Cite journal |last1=Bhatt |first1=Sandeep N. |last2=Leighton |first2=Frank Thomson|date=1984-04-01 |title=A framework for solving VLSI graph layout problems |url=https://dx.doi.org/10.1016/0022-0000%2884%2990071-0 |journal=Journal of Computer and System Sciences |language=en |volume=28 |issue=2 |pages=300–343 |doi=10.1016/0022-0000(84)90071-0 |issn=0022-0000}}</ref> 

<ref name=ackerman>{{cite web|title=On topological graphs with at most four crossings per edge|first=Eyal|last=Ackerman|url=http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf|year=2013|url-status=dead|archive-url=https://web.archive.org/web/20140714181310/http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf|archive-date=2014-07-14}}</ref>

<ref name=acns>{{cite conference|author1=Ajtai, M.|author-link=Miklós Ajtai|author2=Chvátal, V.|author2-link=Václav Chvátal|author3=Newborn, M. |author4=Szemerédi, E. |author4-link=Endre Szemerédi |title=Crossing-free subgraphs|conference=Theory and Practice of Combinatorics|series=North-Holland Mathematics Studies|volume=60|year=1982|pages=9–12|mr=0806962 }}</ref>

<ref name=book>{{cite book|title= Crossing Numbers of Graphs|title-link= Crossing Numbers of Graphs|first=Marcus|last=Schaefer|publisher=CRC Press|year=2018}}</ref>

<ref name=bt>{{cite arXiv |first1=János |last1=Barát |first2=Géza |last2=Tóth |year=2009 |title=Towards the Albertson Conjecture |eprint=0909.0413 |class=math.CO}}</ref>

<ref name=bron>{{cite journal|title=The graphic presentation of sociometric data| first=Urie| last=Bronfenbrenner| author-link=Urie Bronfenbrenner| journal=Sociometry| volume=7|issue=3|year=1944|pages=283–289| doi=10.2307/2785096|jstor=2785096|quote=The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.}}</ref>

<ref name=cm>{{cite journal |author=Cabello S. and [[Bojan Mohar|Mohar B.]] |title=Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard |year=2013 |journal=[[SIAM Journal on Computing]] |volume=42 |issue=5 |pages=1803–1829 |doi=10.1137/120872310 |arxiv=1203.5944 |s2cid=6535755 }}</ref>

<ref name=dey>{{cite journal | author = Dey, T. K. | author-link = Tamal Dey | title = Improved bounds for planar ''k''-sets and related problems | journal = [[Discrete and Computational Geometry]] | volume = 19 | issue = 3 | year = 1998 | pages = 373–382 | doi = 10.1007/PL00009354 | mr = 1608878 | doi-access = free }}</ref>

<ref name=egs>{{Cite journal |first1=Guy |last1=Even |first2=Sudipto |last2=Guha |first3 = Baruch | last3 = Schieber |author3-link = Baruch Schieber | title=Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas |journal=[[SIAM Journal on Computing]] |volume=32 |year=2003 |pages=231–252 |doi=10.1137/S0097539700373520 |issue=1 }}</ref>

<ref name=exoo>{{cite web |last=Exoo |first=G. |url=http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/ |title=Rectilinear Drawings of Famous Graphs}}</ref>

<ref name=gj>{{cite journal |author1=Garey, M. R. |author-link=Michael Garey |author2=Johnson, D. S. |author2-link=David S. Johnson |title=Crossing number is NP-complete |journal=SIAM Journal on Algebraic and Discrete Methods |volume=4 |pages=312–316 |year=1983 |mr=0711340 |doi=10.1137/0604033 |issue=3 }}</ref>

<ref name=grohe>{{Cite journal |last=Grohe |first=M.|author-link=Martin Grohe |title=Computing crossing numbers in quadratic time |journal=[[Journal of Computer and System Sciences]]|volume=68 |issue=2 |year=2005 |pages=285–302 |mr=2059096 |doi=10.1016/j.jcss.2003.07.008 |arxiv=cs/0009010 }}</ref>

<ref name=nabla>{{Cite journal |title=A combinatorial problem |first1=R. K. |last1=Guy |author-link=Richard K. Guy |journal=Nabla (Bulletin of the Malayan Mathematical Society) |volume=7 |year=1960 |pages=68–72 }}</ref>

<ref name=fall>{{cite book
 | last = Guy | first = Richard K. | author-link = Richard K. Guy
 | contribution = The decline and fall of Zarankiewicz's theorem
 | mr = 0253931
 | pages = 63–69
 | publisher = Academic Press, New York
 | title = Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)
 | year = 1969}}.</ref>

<ref name=hlineny>{{cite journal |author=Hliněný, P. |title=Crossing number is hard for cubic graphs |year=2006 |journal=[[Journal of Combinatorial Theory]]|series=Series B |volume=96 |issue=4 |pages=455–471 |mr=2232384 | doi=10.1016/j.jctb.2005.09.009 |doi-access=free }}</ref>

<ref name=hn>{{cite journal
 | last1 = Clancy | first1 = Kieran
 | last2 = Haythorpe | first2 = Michael
 | last3 = Newcombe | first3 = Alex
 | last4 = Pegg | first4 = Ed Jr. | author4-link = Ed Pegg Jr.
 | arxiv = 1804.10336
 | doi = 10.1007/s00373-020-02204-6
 | issue = 6
 | journal = [[Graphs and Combinatorics]]
 | mr = 4163409
 | pages = 1713–1721
 | title = There are no cubic graphs on 26 vertices with crossing number 10 or 11
 | volume = 36
 | year = 2020| s2cid = 253889498
 }}</ref>

<ref name=kr>{{Cite conference |first1= Ken-ichi |last1=Kawarabayashi | author1-link = Ken-ichi Kawarabayashi |first2=Bruce |last2=Reed | author2-link = Bruce Reed (mathematician) |title=Computing crossing number in linear time |conference=[[Symposium on Theory of Computing|Proceedings of the 29th Annual ACM Symposium on Theory of Computing]] |year=2007 |pages=382–390 |doi=10.1145/1250790.1250848 |isbn= 978-1-59593-631-8}}</ref>

<ref name=kmprs>{{Cite journal |last1=de Klerk |first1=E. |last2=Maharry |first2=J. |last3=Pasechnik |first3=D. V. |last4=Richter |first4=B. |last5=Salazar |first5=G. |year=2006 |url=https://research.tilburguniversity.edu/en/publications/improved-bounds-for-the-crossing-numbers-of-kmn-and-kn |title=Improved bounds for the crossing numbers of ''K<sub>m,n</sub>'' and ''K<sub>n</sub>'' |journal=[[SIAM Journal on Discrete Mathematics]] |volume=20 |issue=1 |pages=189–202 | doi=10.1137/S0895480104442741 |arxiv=math/0404142 |s2cid=1509054 }}</ref>

<ref name=leighton>{{cite book |author=Leighton, T. |author-link=F. Thomson Leighton |title=Complexity Issues in VLSI |series=Foundations of Computing Series |publisher=MIT Press |location=Cambridge, MA |year=1983}}</ref>

<ref name=mathworld>{{MathWorld|urlname=GraphCrossingNumber|title=Graph Crossing Number}}</ref>

<ref name=ps>{{cite book | last1 = Pach | first1 = János | author1-link = János Pach | last2 = Sharir | first2 = Micha | author2-link = Micha Sharir | contribution = 5.1 Crossings—the Brick Factory Problem | pages = 126–127 | publisher = [[American Mathematical Society]] | series = Mathematical Surveys and Monographs | title = Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures | volume = 152| year = 2009}}</ref>

<ref name=which>{{cite conference
 | last1 = Pach | first1 = J. | author1-link = János Pach
 | last2 = Tóth | first2 = G.
 | contribution = Which crossing number is it, anyway?
 | doi = 10.1109/SFCS.1998.743512
 | pages = 617–626
 | title = Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998)
 | year = 1998}}.</ref>

<ref name=pr>{{cite journal
 | last1 = Pan | first1 = Shengjun
 | last2 = Richter | first2 = R. Bruce
 | doi = 10.1002/jgt.20249
 | issue = 2
 | journal = [[Journal of Graph Theory]]
 | mr = 2350621
 | pages = 128–134
 | title = The crossing number of {{math|''K''<sub>11</sub>}} is {{math|100}}
 | volume = 56
 | year = 2007| s2cid = 37155969
 }}.</ref>

<ref name=pe>{{Cite journal |last1=Pegg |first1=E. T. |author1-link=Ed Pegg, Jr.|last2=Exoo |first2=G. |title=Crossing Number Graphs |journal=Mathematica Journal |volume=11 |year=2009 |issue=2 |doi=10.3888/tmj.11.2-2|doi-access=free }}</ref>

<ref name=pcj>{{cite conference
 | last1 = Purchase | first1 = Helen C.
 | last2 = Cohen | first2 = Robert F.
 | last3 = James | first3 = Murray I.
 | editor-last = Brandenburg | editor-first = Franz-Josef
 | contribution = Validating graph drawing aesthetics
 | doi = 10.1007/BFb0021827
 | pages = 435–446
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings
 | volume = 1027
 | year = 1995| doi-access = free
 | isbn = 978-3-540-60723-6
 }}.</ref>

<ref name=rcnp>{{cite web |url=http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ |archive-url=https://archive.today/20121230191705/http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ |url-status=dead |archive-date=2012-12-30 |title=Rectilinear Crossing Number project |author=Oswin Aichholzer }}, and
[http://dist.ist.tugraz.at/cape5/ Rectilinear Crossing Number] on the Institute for Software Technology at Graz, University of Technology (2009).</ref>

<ref name=ringel>{{cite journal
 | last = Ringel | first = Gerhard | author-link = Gerhard Ringel
 | doi = 10.1007/BF02996313
 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
 | language = German
 | mr = 0187232
 | pages = 107–117
 | title = Ein Sechsfarbenproblem auf der Kugel
 | volume = 29
 | year = 1965| issue = 1–2 | s2cid = 123286264 }}</ref>

<ref name=pnas>{{Cite journal |title=The minimum number of intersections in complete graphs |first1=T.L. |last1=Saaty |author-link=Thomas L. Saaty |journal=[[Proceedings of the National Academy of Sciences of the United States of America]]|volume=52 |year=1964 |issue=3 |pages=688–690 |doi=10.1073/pnas.52.3.688|bibcode=1964PNAS...52..688S |pmc=300329 |pmid=16591215|doi-access=free }}</ref>

<ref name=ER>{{Cite conference| first=Marcus| last=Schaefer| title=Complexity of some geometric and topological problems|url=http://ovid.cs.depaul.edu/documents/convex.pdf|conference=[[International Symposium on Graph Drawing|Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers]]|series=Lecture Notes in Computer Science|publisher=Springer-Verlag| volume=5849| pages=334–344| doi=10.1007/978-3-642-11805-0_32 |year=2010|isbn=978-3-642-11804-3|doi-access=free}}.</ref>

<ref name=variants>{{cite journal
 | last1 = Schaefer | first1 = Marcus 
 | journal = [[The Electronic Journal of Combinatorics]]
 | at = DS21
 | title = The graph crossing number and its variants: a survey
 | year = 2014
 | volume = 1000 
 | doi = 10.37236/2713 
 | url = https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21| doi-access = free}}</ref>

<ref name=sw>{{Cite journal |title=The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability |first1=Edward R. |last1=Scheinerman|author1-link=Ed Scheinerman |first2=Herbert S. |last2=Wilf|author2-link=Herbert Wilf |journal=[[American Mathematical Monthly]] |volume=101 |issue=10 |year=1994 |pages=939–943 | doi=10.2307/2975158 |jstor=2975158 }}</ref>

<ref name=szekely>{{cite journal |author=Székely, L. A. |title=Crossing numbers and hard Erdős problems in discrete geometry |journal=[[Combinatorics, Probability and Computing]] |volume=6 |year=1997 |pages=353–358 |mr=1464571 | doi=10.1017/S0963548397002976 |issue=3 |s2cid=36602807 }}</ref>

<ref name=turan>{{cite journal |doi=10.1002/jgt.3190010105 |last=Turán |first=P.|author-link=Pál Turán |title=A Note of Welcome |journal=[[Journal of Graph Theory]] |volume=1 |pages=7–9 |year=1977 }}</ref>

<ref name=z>{{cite journal |last=Zarankiewicz |first=K. |author-link=Kazimierz Zarankiewicz|title=On a Problem of P. Turán Concerning Graphs |journal=[[Fundamenta Mathematicae]] |volume=41 |pages=137–145 |year=1954 |doi=10.4064/fm-41-1-137-145 |doi-access=free }}</ref>

}}

[[Category:Topological graph theory]]
[[Category:Graph invariants]]
[[Category:Graph drawing]]
[[Category:Geometric intersection]]
[[Category:NP-complete problems]]

Pages transcluded onto the current version of this page (help):

Template:Cite arXiv (view source) (template editor protected)
Template:Cite book (view source) (protected)
Template:Cite conference (view source) (protected)
Template:Cite journal (view source) (protected)
Template:Cite web (view source) (protected)
Template:Harvard citations (view source) (semi-protected)
Template:Harvard citations/core (view source) (semi-protected)
Template:Harvs (view source) (semi-protected)
Template:Main (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:Math (view source) (template editor protected)
Template:MathWorld (view source) (template editor protected)
Template:Mvar (view source) (template editor protected)
Template:OEIS (view source) (semi-protected)
Template:OEIS link (edit)
Template:Pagetype (view source) (protected)
Template:R (view source) (template editor protected)
Template:R/ref (view source) (template editor protected)
Template:R/superscript (view source) (template editor protected)
Template:R/where (view source) (template editor protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SDcat (view source) (protected)
Template:SfnRef (view source) (template editor protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Template:Sup (view source) (template editor protected)
Module:Arguments (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:Footnotes (view source) (template editor protected)
Module:Format link (view source) (template editor protected)
Module:GetParameters (view source) (protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Labelled list hatnote (view source) (template editor protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/rfd (view source) (protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:SDcat (view source) (protected)
Module:String (view source) (protected)
Module:String2 (view source) (template editor protected)
Module:Template wrapper (view source) (template editor protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to Crossing number (graph theory).

Retrieved from "https://en.wikipedia.org/wiki/Crossing_number_(graph_theory)"