查看“︁交叉數”︁的源代码

[[File:3-crossing Heawood graph.svg|thumb|{{link-en|希伍德圖|Heawood graph}}的一個畫法，其有三個交叉。此為所有畫法中，交叉個數的最小可能值，所以該圖的交叉數為 <math>\text{cr}(G)=3</math>。]]

在[[圖論]]，'''交叉數'''<math>\text{cr}(G)</math>是將[[圖 (數學)|圖]]<math>G</math>畫在[[平面 (数学)|平面]]上時，邊的交叉點的最小數目。若<math>\hbox{cr}(G)=0</math>，則<math>G</math>稱為[[平面图 (图论)|平面圖]]。在{{link-en|圖形製圖|graph drawing}}方面<!--參考https://terms.naer.edu.tw/search/?q=graph+drawing 的譯法-->，計算圖的交叉數仍是一個重要問題，因為讀者研究發現，畫圖的交叉越少，越有利於讀者理解。{{r|pcj}}

交叉數的研究始於{{link-en|圖蘭磚廠問題|Turán's brick factory problem}}。[[圖蘭·帕爾]]想求磚廠中，將每個窯爐各與全部貨倉用路軌連接的最優方案，使路軌的交叉儘可能少。按上述定義，即是問[[完全二部圖]]的交叉數。{{r|turan}}同一問題約莫同時在[[社會學]]研究提出，因為事關{{link-en|社會關係圖|sociogram}}的繪製。{{r|bron}} 圖蘭猜想了完全二部圖交叉數的公式，但該公式迄今未獲證，[[完全圖]]的交叉數公式亦然。
 
[[交叉數不等式]]斷言，若邊數<math>e</math>与頂點數<math>n</math>的比值大于某个常数，則交叉數不小于<math>e^3/n^2</math>乘以另一个固定的常数。此結論在[[超大规模集成电路]]設計與[[組合幾何]]方面有應用。

如無特別註明，交叉數允許使用任意曲線來畫邊。另一個相關概念是'''直線交叉數'''，其要求僅使用直線段來畫邊，所以未必等於交叉數。更具體說，[[完全圖]]<math>K_n</math>的直線交叉數就是平面上處於一般位置的<math>n</math>個點所能組成的[[凸多邊形|凸]][[四邊形]]的最少數目，因為每個凸四邊形的兩條對角線產生一個交叉。直線交叉數問題與[[幸福結局問題]]密切相關。{{r|sw}}

給定一個圖，計算其交叉數是一個[[NP難]]問題。{{r|gj}}

==定義==
定義交叉數之前，先定義[[圖 (數學)#有向圖和無向圖|無向圖]]的'''畫法'''。圖的畫法是一個映射，其將圖的頂點映到平面上互異的點，並將每條邊映到一條連接其兩端的曲線段，但頂點不能映到其他邊上（除非該邊以其為頂點），且若兩條邊的曲線段在公共頂點以外相交，則其僅產生有限多個交叉，並於每個交叉處{{link-en|橫截|Transversality (mathematics)}}相交。若一個交叉點有多於兩條邊相交，則每對相交邊計算一次。圖的交叉數是所有畫法當中，交叉的數目的最小值。{{r|which}}

一些作者對於畫法有更多限制，例如要求每對邊的交集至多只有一點（可為公共端點或交叉）。對於上段定義的交叉數，此項限制沒有任何影響，因為交叉最少的畫法當中，兩條邊必定相交至多一次。（若兩條邊有公共端點，而且相交，則可以將首個交點以前的兩段曲線互換，從而減少一個交叉。類似地，若兩條邊有兩個或更多交叉，則可以將相鄰兩個交叉之間的兩段曲線互換，以減少兩個交叉。）然而，若考慮交叉數的變式定義，例如只計算有多少對邊交叉（稱為'''兩兩交叉數'''），而非有多少個交叉，則上述限制確實會影響兩兩交叉數的值。{{r|which}}

==特殊情況==
截止2015年4月，僅得很少幾類圖的交叉數為人所知。即使是[[完全圖]]、[[完全二部圖]]、兩個[[環 (圖論)|環]]的積等結構較簡單的圖，也僅得初始幾個的交叉數是已知的，但交叉數的下界方面，已有一定進展。{{r|kmprs}}

===完全二部圖===
[[File:Zarankiewicz K4 7.svg|thumb|<math>K_{4,7}</math>的一個最優畫法，顯示圖蘭磚廠問題中，若有4個倉（黃點）和7個窯（藍點），則需要18個交叉（紅點）。]]
{{main
|圖蘭磚廠問題
}}
在[[第二次世界大戰]]期間，匈牙利數學家[[圖蘭·帕爾]]被迫在磚廠工作，要將一車車的磚從窯爐推到貨倉。工廠的每個窯爐到每個貨倉之間各有一條路軌，而磚車在路軌交叉處特別難推。於是，圖蘭提出其'''磚廠問題'''：窯爐、貨倉和路軌應如何安排，才能使交叉的數目最少？數學上，窯爐和貨倉可視為[[完全二部圖]]的頂點，而路軌則是二部圖的邊。於是工廠的佈局就是該圖在平面上的一個畫法，換言之問題變成：
完全二部圖的畫法中，交叉的最少數目是多少？{{r|ps}}

{{link-en|卡齊米日·扎蘭凱維奇|Kazimierz Zarankiewicz}}<!--遵循[[卡齊米日·諾瓦克]]的先例和[[WP:外語譯音表/波蘭語]]暫譯-->嘗試解決圖蘭磚廠問題，{{r|z}}但其證明有錯。不過，他成功推導出完全二部圖<math>K_{m,n}</math>交叉數的一個[[上界和下界|上界]]：

:<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>

一個猜想是，上述上界確實是所有完全二部圖的交叉數。{{r|fall}}

===完全圖與圖染色===
[[完全圖]]的交叉數問題最先由{{link-en|安東尼·希爾|Anthony Hill (artist)}}<!--遵循[[泰勒·希爾]]的先例-->提出，並於1960年出版。{{r|nabla}}希爾及其合作者{{link-en|約翰·恩斯特|John Ernest}}皆為對數學甚感興趣的[[构成主义_(艺术)|構成主義]]藝術家。兩位不僅提出了問題，還猜想了該交叉數的公式，公式由{{link-en|理查·蓋|Richard K. Guy}}<!--遵循[[蓋·皮爾斯]]的先例暫譯-->於1960年出版。{{r|nabla}}具體來說，已知<math>K_p</math>總有一種畫法，其交叉的數目為
:<math>\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>
上式在<math>p = 5, 6, \cdots, 12</math>時，取值分別為<math>1, 3, 9, 18, 36, 60, 100, 150</math>，見[[整數數列線上大全]]的{{OEIS link|A000241}}號數列。希爾等人猜想，不存在更好的畫法，即上式給出了完全圖的交叉數<math>\text{cr}(K_p)</math>。{{link-en|湯瑪士·沙提|Thomas L. Saaty}}<!--遵循[[匹茲堡大學]]中的先例-->於1964年獨立地作出了同一個猜想。{{r|pnas}}

對於<math>p \le 10</math>，沙提驗證了上式確實給出交叉的最小可能數目。潘（Shengjun Pan)<!--未能查證其中文姓名-->和布魯斯·里希特（Bruce Richter）<!--未能查證其姓氏讀音應譯為里希特或里克特-->驗證了<math>p = 11, 12</math>的情況。{{r|pr}}

2007年，米高·艾伯森（Michael O. Albertson）提出了{{link-en|艾伯森猜想|Albertson conjecture}}<!--遵循[[艾伯森·范佐·波斯特]]的先例-->，其斷言：在所有[[圖着色問題#圖色數|色數]]為<math>p</math>的圖之中，完全圖<math>K_p</math>的交叉數最小。換言之，若此猜想與上段的猜想均成立，則每個染色數為<math>p</math>的圖，交叉數皆不小於上段的公式。現已證明，艾伯森猜想對於<math>p \le 16</math>成立。{{r|bt}}

===立方圖===
已知交叉數為<math>1</math>至<math>11</math>的最小的[[立方圖]]，其頂點數分別為<math>6, 10, 14, 16, 18, 20, 22, 24, 26, 28, 28</math>{{OEIS|id=A110507}}，如下表所記：

{| class="wikitable"
! 交叉數
! 最小立方圖例子
! 頂點數
|-
! 1
| [[完全二部圖]]<math>K_{3,3}</math> || 6
|-
! 2
| [[佩特森圖]]
| 10
|-
! 3
| {{link-en|希伍德圖|Heawood graph}}<!--得名於[[彭西·希伍德]]-->
| 14
|-
! 4
| {{link-en|莫比烏斯－坎特圖|Möbius-Kantor graph}}<!--遵循[[米奇·坎特]]的先例-->
| 16
|-
! 5
| {{link-en|帕普斯圖|Pappus graph}}<!--得名於[[帕普斯]]-->
| 18
|-
! 6
| {{link-en|笛沙格圖|Desargues graph}}<!--得名於[[吉拉德·笛沙格]]-->
| 20
|-
! 7
| 有4個不同構的例子，但並無熟知命名{{r|mathworld}}
| 22
|-
! 8
| {{link-en|瑙魯圖|Nauru graph}}<!--得名於[[瑙魯國旗]]-->、{{link-en|麥基圖|McGee graph}}<!--遵循[[傑克·麥基]]的先例-->、(3,7)-{{link-en|籠圖|cage graph}}{{r|pe}}
| 24
|-
! 9
| 麥基圖加某一條邊{{r|oeis}}
| 26
|-
! 10
| 麥基圖加某兩條邊{{r|oeis}}
| 28
|-
! 11
| [[考克斯特圖]]<!--得名於[[哈羅德·斯科特·麥克唐納·考克斯特]]-->{{r|hn}}
| 28
|}

2009年，{{link-en|愛德華·柏奇|Ed Pegg}}<!--遵循[[西蒙·柏奇]]的先例-->和Geoffrey Exoo<!--未能查證讀音-->猜想交叉數為13的最小立方圖為{{link-en|塔特－考克斯特圖|Tutte–Coxeter graph}}<!--按英文維基百科[[W. T. Tutte]]標注的讀音依[[WP: 外語譯音表/英語]]暫譯-->，以及交叉數為170的最小立方圖為{{link-en|塔特12-籠|Tutte 12-cage}}。{{r|pe|exoo}}

==複雜度與近似==
一般情況下，很難計算圖的交叉數。{{link-en|米高·加里|Michael Garey}}<!--參考地名[[加里 (加利福尼亞州)]]暫譯-->和{{link-en|大衛·詹森|David S. Johnson}}於1983年證明了計算交叉數是[[NP難]]問題。{{r|gj}}即使僅考慮[[立方圖]]{{r|hlineny}}，或者僅考慮將近平面的特殊情況（即可藉刪走一條邊使之變成平面圖）{{r|cm}}，問題仍然NP難。另一個相關問題是計算僅能使用直線段畫圖時，交叉數目的最小值。該最小值稱為'''直線交叉數'''（rectilinear crossing number）。該問題對於{{link-en|實數的存在理論|existential theory of the reals}}是[[完備 (複雜度)|完全]]的。{{r|ER}}

另一方面，對於固定的常數<math>k</math>，有高效算法判定交叉數是否小於<math>k</math>。換言之，交叉數問題是{{link-en|固定參數可馴順|fixed-parameter tractable}}<!--tractable的譯法參考张鸿林、葛显良《英汉数学词汇》-->的。{{r|grohe|kr}}但若<math>k</math>不是常數，而是與輸入大小有關的函數，例如<math>k=|V|/2</math>，則問題仍然很難。對於度數有界的圖<math>G</math>，有高效的[[近似算法]]能夠近似計算交叉數<math>\text{cr}(G)</math>。{{r|egs}}實務上，常使用[[啟發法|啟發式]]算法，例如從空圖開始，逐條邊加入，使得每次產生的交叉數儘可能小。直線交叉數[[分布式计算]]計劃（Rectilinear Crossing Number project）使用了此類算法。{{r|rcnp}}

==交叉數不等式==
{{Main
|交叉數不等式
}}

若[[无向图|無向]][[图_(数学)#简单图|簡單圖]]<math>G</math>恰有<math>n</math>個頂點和<math>e</math>條邊，且<math>e>7n</math>，則[[交叉數]]<math> \text{cr}(G)</math>滿足[[不等|不等式]] 
::<math>\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.</math>

此種邊數、頂點數與交叉數的關係，最早由{{link-en|奧伊陶伊·米克洛什|Miklós Ajtai}}、{{link-en|瓦茨拉夫·赫瓦塔爾|Václav Chvátal}}、{{link-en|蒙提·紐邦|Monty Newborn}}、[[塞邁雷迪·安德烈]]四人{{r|acns}}和{{link-en|湯姆森·雷頓|F. Thomson Leighton}}{{r|leighton}}分別獨立發現，稱為[[交叉數不等式]]或交叉數引理。不等式的上述版本是為伊爾·艾克曼（Eyal Ackerman）的結果，其中常數<math>29</math>為截至2019年所知最優。{{r|ackerman}}条件中的常數<math>7</math>也可以縮少至更佳的<math>4</math>，但代價是<math>29</math>要換成較差的<math>64</math>。{{r|acns|leighton}}

雷頓之所以研究交叉數，是為了理論計算機科學中，[[超大型積體電路]]設計方面的應用。{{r|leighton}}其後，Székely 發現交叉數不等式用在[[關聯幾何]]方面，能夠簡短證明一些重要定理，例如[[塞邁雷迪－特羅特定理]]和{{link-en|貝克定理|Beck's theorem (geometry)}}。{{r|szekely}}{{link-en|塔馬爾·戴伊|Tamal Dey}}類似地證明了{{link-en|幾何''k''-集|K-set (geometry)}}數的上界。{{r|dey}}

==變式==
若僅允許用直線段畫邊，而非任意曲線，則一些圖需要更多交叉才能畫出。對於此類畫法，交叉數目的最小可能值稱為'''直線交叉數'''。直線交叉數必不小於交叉數，甚至對某些圖而言，直線交叉數嚴格大於交叉數。完全圖<math>K_5</math>至<math>K_{12}</math>的直線交叉數依序為<math>1, 3, 9, 19, 36, 62, 102, 153</math>{{OEIS|A014540}}。已知直至<math>K_{27}</math>的直線交叉數，而<math>K_{28}</math>則可能需要7233或7234個交叉。直線交叉數[[分布式计算]]計劃（Rectilinear Crossing Number project）收集了更多數據。{{r|rcnp}}

若一個圖有畫法使得每條邊至多<math>k</math>個交叉，但<math>k</math>不能更少，則稱<math>k</math>為其'''局部交叉數'''（local crossing number）。若圖有畫法使每條邊至多<math>k</math>個交叉，則稱其為<math>k</math>-'''平面圖'''（<math>k</math>-planar）。{{r|ringel}}

其他變式包括'''兩兩相交數'''（pairwise crossing number，即任何畫法中，有交叉的邊對數目的最小可能值）和'''奇相交數'''（odd crossing number，即任何畫法中，交叉次數恰為奇數的邊對數目的最小可能值）。奇相交數不大於兩兩相交數，兩兩相交數也不大於相交數。然而，{{link-en|哈納尼-塔特定理|Hanani–Tutte theorem}}<!--遵循[[平面圖 (圖論)]]中的先例-->說明，若這三個數中有任何一個為零，則皆為零。{{r|which}} {{harvs|last=Schaefer|year=2014|year2=2018|txt}}綜述了許多變式。{{r|variants|book}}

==參考==
* http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/ {{Wayback|url=http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/ |date=20201121144634 }}
{{Reflist|30em|refs=

<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=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=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=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 | 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=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|access-date=2020-11-04|archive-date=2021-06-26|archive-url=https://web.archive.org/web/20210626212759/http://ovid.cs.depaul.edu/documents/convex.pdf|dead-url=no}}.</ref>

<ref name=exoo>{{cite web |last=Exoo |first=G. |url=http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/ |title=Rectilinear Drawings of Famous Graphs |access-date=2021-06-24 |archive-date=2021-06-24 |archive-url=https://web.archive.org/web/20210624204634/http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/ |dead-url=no }}</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=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=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 }}</ref>

<ref name=hn>{{citation|first1=Michael|last1=Haythorpe|first2=Alex|last2=Newcombe|title=There are no Cubic Graphs on 26 Vertices with Crossing Number 11|year=2018|arxiv=1804.10336}}</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 |access-date=2021-06-23 |archive-date=2021-06-28 |archive-url=https://web.archive.org/web/20210628151447/https://research.tilburguniversity.edu/en/publications/improved-bounds-for-the-crossing-numbers-of-kmn-and-kn |dead-url=no }}</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=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=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>{{cite mathworld|urlname=GraphCrossingNumber|title=Graph Crossing Number}}</ref>

<ref name=oeis>{{SloanesRef |sequencenumber=A110507 |name=Number of nodes in the smallest cubic graph with crossing number n.}}</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
 }}.</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}}</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}}</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}}.</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=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] {{Wayback|url=http://dist.ist.tugraz.at/cape5/ |date=20080625230740 }} 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 = de
 | mr = 0187232
 | pages = 107–117
 | title = Ein Sechsfarbenproblem auf der Kugel
 | volume = 29
 | year = 1965| issue = 1–2 | s2cid = 123286264 }}</ref>

<ref name=sw>{{Cite journal |title=The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability |url=https://archive.org/details/sim_american-mathematical-monthly_1994-12_101_10/page/939 |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 }}</ref>

<ref name=turan>{{cite journal |doi=10.1002/jgt.3190010105 |last=Turán |first=P.|author-link=圖蘭·帕爾|title=A Note of Welcome |url=https://archive.org/details/sim_journal-of-graph-theory_spring-1977_1_1/page/7 |journal=[[Journal of Graph Theory]] |volume=1 |pages=7–9 |year=1977 }}</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
 | url = https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21
 | access-date = 2021-06-25
 | archive-date = 2021-06-29
 | archive-url = https://web.archive.org/web/20210629211416/https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21
 | dead-url = no
 }}</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=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:圖論]]