交叉數:修订间差异
第1行: | 第1行: | ||
{{Translating|[[:en:Crossing number (graph theory)]]||tpercent= |
{{Translating|[[:en:Crossing number (graph theory)]]||tpercent=78.2|time=2021-06-26T18:45:25+00:00}} |
||
[[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}}。{{link-en|圖蘭·帕爾|Pál Turán}}想求磚廠中,將每個窯爐各與全部貨倉用路軌連接的最優方案,使路軌的交叉儘可能少。按上述定義,即是問[[完全二部圖]]的交叉數。{{r|turan}}同一問題約莫同時在[[社會學]]研究提出,因為事關{{link-en|社會關係圖|sociogram}}的繪製。{{r|bron}} 圖蘭猜想了完全二部圖交叉數的公式,但該公式迄今未獲證,[[完全圖]]的交叉數公式亦然。 |
|||
以<math>\hbox{cr}(G)</math>表示圖<math>G</math>的交叉數。若<math>\hbox{cr}(G)=0</math>,<math>G</math>稱為[[平面图 (图论)|平面圖]]。 |
|||
[[交叉數不等式]]斷言,若邊數<math>e</math>与頂點數<math>n</math>的比值大于某个常数,則交叉數不小于<math>e^3/n^2</math>乘以另一个固定的常数。此結論在[[超大规模集成电路]]設計與[[組合幾何]]方面有應用。 |
|||
⚫ | |||
如無特別註明,交叉數允許使用任意曲線來畫邊。另一個相關概念是'''直線交叉數''',其要求僅使用直線段來畫邊,所以未必等於交叉數。更具體說,[[完全圖]]<math>K_n</math>的直線交叉數就是平面上處於一般位置的<math>n</math>個點所能組成的[[凸多邊形|凸]][[四邊形]]的最少數目,因為每個凸四邊形的兩條對角線產生一個交叉。直線交叉數問題與[[幸福結局問題]]密切相關。{{r|sw}} |
如無特別註明,交叉數允許使用任意曲線來畫邊。另一個相關概念是'''直線交叉數''',其要求僅使用直線段來畫邊,所以未必等於交叉數。更具體說,[[完全圖]]<math>K_n</math>的直線交叉數就是平面上處於一般位置的<math>n</math>個點所能組成的[[凸多邊形|凸]][[四邊形]]的最少數目,因為每個凸四邊形的兩條對角線產生一個交叉。直線交叉數問題與[[幸福結局問題]]密切相關。{{r|sw}} |
||
⚫ | |||
==定義== |
==定義== |
||
定義交叉數之前,先定義[[圖 (數學)#有向圖和無向圖|無向圖]]的'''畫法'''。圖的畫法是一個映射,其將圖的頂點映到平面上互異的點,並將每條邊映到一條連接其兩端的曲線段,但頂點不能映到其他邊上(除非該邊以其為頂點),且若兩條邊的曲線段在公共頂點以外相交,則其僅產生有限多個交叉,並於每個交叉處{{link-en|橫截|Transversality (mathematics)}}相交。若一個交叉點有多於兩條邊相交,則 |
定義交叉數之前,先定義[[圖 (數學)#有向圖和無向圖|無向圖]]的'''畫法'''。圖的畫法是一個映射,其將圖的頂點映到平面上互異的點,並將每條邊映到一條連接其兩端的曲線段,但頂點不能映到其他邊上(除非該邊以其為頂點),且若兩條邊的曲線段在公共頂點以外相交,則其僅產生有限多個交叉,並於每個交叉處{{link-en|橫截|Transversality (mathematics)}}相交。若一個交叉點有多於兩條邊相交,則每對相交邊計算一次。圖的交叉數是所有畫法當中,交叉的數目的最小值。{{r|which}} |
||
一些作者對於畫法有更多限制,例如要求每對邊的交集至多只有一點(可為公共端點或交叉)。對於上段定義的交叉數,此項限制沒有任何影響,因為交叉最少的畫法當中,兩條邊必定相交至多一次。(若兩條邊有公共端點,而且相交,則可以將首個交點以前的兩段曲線互換,從而減少一個交叉。類似地,若兩條邊有兩個或更多交叉,則可以將相鄰兩個交叉之間的兩段曲線互換,以減少兩個交叉。)然而,若考慮交叉數的變式定義,例如只計算有多少對邊交叉(稱為'''兩兩交叉數'''),而非有多少個交叉,則上述限制確實會影響兩兩交叉數的值。{{r|which}} |
一些作者對於畫法有更多限制,例如要求每對邊的交集至多只有一點(可為公共端點或交叉)。對於上段定義的交叉數,此項限制沒有任何影響,因為交叉最少的畫法當中,兩條邊必定相交至多一次。(若兩條邊有公共端點,而且相交,則可以將首個交點以前的兩段曲線互換,從而減少一個交叉。類似地,若兩條邊有兩個或更多交叉,則可以將相鄰兩個交叉之間的兩段曲線互換,以減少兩個交叉。)然而,若考慮交叉數的變式定義,例如只計算有多少對邊交叉(稱為'''兩兩交叉數'''),而非有多少個交叉,則上述限制確實會影響兩兩交叉數的值。{{r|which}} |
||
第136行: | 第138行: | ||
<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=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=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> |
||
第173行: | 第177行: | ||
<ref name=oeis>{{SloanesRef |sequencenumber=A110507 |name=Number of nodes in the smallest cubic graph with crossing number n.}}</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=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> |
||
第208行: | 第227行: | ||
<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=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=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=variants>{{cite journal |
<ref name=variants>{{cite journal |
2021年6月26日 (六) 18:45的版本
此條目目前正依照en:Crossing number (graph theory)上的内容进行翻译。 (2021年6月26日) |
在圖論,交叉數是將圖畫在平面上時,邊的交叉點的最小數目。若,則稱為平面圖。在圖形製圖方面,計算圖的交叉數仍是一個重要問題,因為讀者研究發現,畫圖的交叉越少,越有利於讀者理解。[1]
交叉數的研究始於圖蘭磚廠問題。圖蘭·帕爾想求磚廠中,將每個窯爐各與全部貨倉用路軌連接的最優方案,使路軌的交叉儘可能少。按上述定義,即是問完全二部圖的交叉數。[2]同一問題約莫同時在社會學研究提出,因為事關社會關係圖的繪製。[3] 圖蘭猜想了完全二部圖交叉數的公式,但該公式迄今未獲證,完全圖的交叉數公式亦然。
交叉數不等式斷言,若邊數与頂點數的比值大于某个常数,則交叉數不小于乘以另一个固定的常数。此結論在超大规模集成电路設計與組合幾何方面有應用。
如無特別註明,交叉數允許使用任意曲線來畫邊。另一個相關概念是直線交叉數,其要求僅使用直線段來畫邊,所以未必等於交叉數。更具體說,完全圖的直線交叉數就是平面上處於一般位置的個點所能組成的凸四邊形的最少數目,因為每個凸四邊形的兩條對角線產生一個交叉。直線交叉數問題與幸福結局問題密切相關。[4]
定義
定義交叉數之前,先定義無向圖的畫法。圖的畫法是一個映射,其將圖的頂點映到平面上互異的點,並將每條邊映到一條連接其兩端的曲線段,但頂點不能映到其他邊上(除非該邊以其為頂點),且若兩條邊的曲線段在公共頂點以外相交,則其僅產生有限多個交叉,並於每個交叉處橫截相交。若一個交叉點有多於兩條邊相交,則每對相交邊計算一次。圖的交叉數是所有畫法當中,交叉的數目的最小值。[6]
一些作者對於畫法有更多限制,例如要求每對邊的交集至多只有一點(可為公共端點或交叉)。對於上段定義的交叉數,此項限制沒有任何影響,因為交叉最少的畫法當中,兩條邊必定相交至多一次。(若兩條邊有公共端點,而且相交,則可以將首個交點以前的兩段曲線互換,從而減少一個交叉。類似地,若兩條邊有兩個或更多交叉,則可以將相鄰兩個交叉之間的兩段曲線互換,以減少兩個交叉。)然而,若考慮交叉數的變式定義,例如只計算有多少對邊交叉(稱為兩兩交叉數),而非有多少個交叉,則上述限制確實會影響兩兩交叉數的值。[6]
特殊情況
截止2015年4月,僅得很少幾類圖的交叉數為人所知。即使是完全圖、完全二部圖、兩個環的積等結構較簡單的圖,也僅得初始幾個的交叉數是已知的,但交叉數的下界方面,已有一定進展。[7]
完全二部圖
在第二次世界大戰期間,匈牙利數學家圖蘭·帕爾被迫在磚廠工作,要將一車車的磚從窯爐推到貨倉。工廠的每個窯爐到每個貨倉之間各有一條路軌,而磚車在路軌交叉處特別難推。於是,圖蘭提出其磚廠問題:窯爐、貨倉和路軌應如何安排,才能使交叉的數目最少?數學上,窯爐和貨倉可視為完全二部圖的頂點,而路軌則是二部圖的邊。於是工廠的佈局就是該圖在平面上的一個畫法,換言之問題變成: 完全二部圖的畫法中,交叉的最少數目是多少?[8]
卡齊米日·扎蘭凱維奇嘗試解決圖蘭磚廠問題,[9]但其證明有錯。不過,他成功推導出完全二部圖交叉數的一個上界:
一個猜想是,上述上界確實是所有完全二部圖的交叉數。[10]
完全圖與圖染色
完全圖的交叉數問題最先由安東尼·希爾提出,並於1960年出版。[11]希爾及其合作者約翰·恩斯特皆為對數學甚感興趣的構成主義藝術家。兩位不僅提出了問題,還猜想了該交叉數的公式,公式由理查·蓋於1960年出版。[11]具體來說,已知總有一種畫法,其交叉的數目為
上式在時,取值分別為,見整數數列線上大全的A000241號數列。希爾等人猜想,不存在更好的畫法,即上式給出了完全圖的交叉數。湯瑪士·沙提於1964年獨立地作出了同一個猜想。[12]
對於,沙提驗證了上式確實給出交叉的最小可能數目。潘(Shengjun Pan)和布魯斯·里希特(Bruce Richter)驗證了的情況。[13]
2007年,米高·艾伯森(Michael O. Albertson)提出了艾伯森猜想,其斷言:在所有色數為的圖之中,完全圖的交叉數最小。換言之,若此猜想與上段的猜想均成立,則每個染色數為的圖,交叉數皆不小於上段的公式。現已證明,艾伯森猜想對於成立。[14]
立方圖
已知交叉數為至的最小的立方圖,其頂點數分別為(OEIS數列A110507),如下表所記:
交叉數 | 最小立方圖例子 | 頂點數 |
---|---|---|
1 | 完全二部圖 | 4 |
2 | 佩特森圖 | 10 |
3 | 希伍德圖 | 14 |
4 | 莫比烏斯-坎特圖 | 16 |
5 | 帕普斯圖 | 18 |
6 | 笛沙格圖 | 20 |
7 | 有4個不同構的例子,但並無熟知命名[15] | 22 |
8 | 瑙魯圖、麥基圖、(3,7)-籠圖[16] | 24 |
9 | 麥基圖加某一條邊[17] | 26 |
10 | 麥基圖加某兩條邊[17] | 28 |
11 | 考克斯特圖[18] | 28 |
2009年,愛德華·柏奇和Geoffrey Exoo猜想交叉數為13的最小立方圖為塔特-考克斯特圖,以及交叉數為170的最小立方圖為塔特12-籠。[16][19]
複雜度與近似
一般情況下,很難計算圖的交叉數。米高·加里和大衛·詹森於1983年證明了計算交叉數是NP難問題。[5]即使僅考慮立方圖[20],或者僅考慮將近平面的特殊情況(即可藉刪走一條邊使之變成平面圖)[21],問題仍然NP難。另一個相關問題是計算僅能使用直線段畫圖時,交叉數目的最小值。該最小值稱為直線交叉數(rectilinear crossing number)。該問題對於實數的存在理論是完全的。[22]
另一方面,對於固定的常數k,有高效算法判定交叉數是否小於k。換言之,交叉數問題是固定參數可馴順的。[23][24]但若k不是常數,而是與輸入大小有關的函數,例如k = |V|/2,則問題仍然很難。對於度數有界的圖G,有高效的近似算法能夠近似計算交叉數cr(G)。[25]實務上,常使用啟發式算法,例如從空圖開始,逐條邊加入,使得每次產生的交叉數儘可能小。直線交叉數分布式计算計劃(Rectilinear Crossing Number project)使用了此類算法。[26]
交叉數不等式
交叉數不等式說明了給定邊數目和頂點數目,的下界。
已知平面圖都符合(歐拉公式)。考慮邊面的對應數目,每條邊剛好屬於某兩個面,而每個面最小有三條邊,因此對於平面圖有。為了消去,代入,得。
再考慮一般圖,如何將它「變成」平面圖。如果我們在每個相交點,都去掉一條邊,則剩下的圖必是平面圖。這個新的平面圖的邊數目為,而頂點數目v不變。因此,對於所有的圖都有
接下來使用機率方法,從G中構作一個新的圖。考慮在G所有頂點中選取某些點作為新圖G'的頂點;若G中的某一條邊的兩個端點都在V(G')內,則E(G')亦有該條邊;因此,G中的一個交點仍然存在在G'中的條件,是該交點涉及的2條邊的4個不同端點都保留在G'中。現在隨機選取G中的pv個頂點(),則 ,代入上面的不等式:
求的下界,希望能使上面的不等式右方儘可能大。
當相當大時,考慮,可以取,整理後得:
變式
若僅允許用直線段畫邊,而非任意曲線,則一些圖需要更多交叉才能畫出。對於此類畫法,交叉數目的最小可能值稱為直線交叉數。直線交叉數必不小於交叉數,甚至對某些圖而言,直線交叉數嚴格大於交叉數。完全圖至的直線交叉數依序為(OEIS數列A014540)。已知直至的直線交叉數,而則可能需要7233或7234個交叉。直線交叉數分布式计算計劃(Rectilinear Crossing Number project)收集了更多數據。[26]
若一個圖有畫法使得每條邊至多個交叉,但不能更少,則稱為其局部交叉數(local crossing number)。若圖有畫法使每條邊至多個交叉,則稱其為-平面圖(-planar)。[27]
其他變式包括兩兩相交數(pairwise crossing number,即任何畫法中,有交叉的邊對數目的最小可能值)和奇相交數(odd crossing number,即任何畫法中,交叉次數恰為奇數的邊對數目的最小可能值)奇相交數不大於兩兩相交數,兩兩相交數也不大於相交數。然而,哈納尼-塔特定理說明,若這三個數中有任何一個為零,則皆為零。[6] Schaefer (2014, 2018)綜述了許多變式。[28][29]
參考
- ^ Purchase, Helen C.; Cohen, Robert F.; James, Murray I. Brandenburg, Franz-Josef , 编. Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, Germany, September 20-22, 1995, Proceedings. Lecture Notes in Computer Science 1027. Springer: 435–446. 1995. doi:10.1007/BFb0021827 .
|contribution=
被忽略 (帮助). - ^ Turán, P. A Note of Welcome. Journal of Graph Theory. 1977, 1: 7–9. doi:10.1002/jgt.3190010105.
- ^ Bronfenbrenner, Urie. The graphic presentation of sociometric data. Sociometry. 1944, 7 (3): 283–289. JSTOR 2785096. doi:10.2307/2785096.
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.
- ^ Scheinerman, Edward R.; Wilf, Herbert S. The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability. American Mathematical Monthly. 1994, 101 (10): 939–943. JSTOR 2975158. doi:10.2307/2975158.
- ^ 5.0 5.1 Garey, M. R.; Johnson, D. S. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods. 1983, 4 (3): 312–316. MR 0711340. doi:10.1137/0604033.
- ^ 6.0 6.1 6.2 Pach, J.; Tóth, G. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998): 617–626. 1998. doi:10.1109/SFCS.1998.743512.
|contribution=
被忽略 (帮助). - ^ de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. Improved bounds for the crossing numbers of Km,n and Kn. SIAM Journal on Discrete Mathematics. 2006, 20 (1): 189–202. S2CID 1509054. arXiv:math/0404142 . doi:10.1137/S0895480104442741.
- ^ Pach, János; Sharir, Micha. 5.1 Crossings—the Brick Factory Problem. Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Mathematical Surveys and Monographs 152. American Mathematical Society. 2009: 126–127.
- ^ Zarankiewicz, K. On a Problem of P. Turán Concerning Graphs. Fundamenta Mathematicae. 1954, 41: 137–145. doi:10.4064/fm-41-1-137-145 .
- ^ Guy, Richard K. The decline and fall of Zarankiewicz's theorem. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). Academic Press, New York. 1969: 63–69. MR 0253931..
- ^ 11.0 11.1 Guy, R. K. A combinatorial problem. Nabla (Bulletin of the Malayan Mathematical Society). 1960, 7: 68–72.
- ^ Saaty, T.L. The minimum number of intersections in complete graphs. Proceedings of the National Academy of Sciences of the United States of America. 1964, 52 (3): 688–690. Bibcode:1964PNAS...52..688S. PMC 300329 . PMID 16591215. doi:10.1073/pnas.52.3.688.
- ^ Pan, Shengjun; Richter, R. Bruce. The crossing number of K11 is 100. Journal of Graph Theory. 2007, 56 (2): 128–134. MR 2350621. doi:10.1002/jgt.20249..
- ^ Barát, János; Tóth, Géza. Towards the Albertson Conjecture. 2009. arXiv:0909.0413 [math.CO].
- ^ 埃里克·韦斯坦因. Graph Crossing Number. MathWorld.
- ^ 16.0 16.1 Pegg, E. T.; Exoo, G. Crossing Number Graphs. Mathematica Journal. 2009, 11 (2). doi:10.3888/tmj.11.2-2.
- ^ 17.0 17.1 Sloane, N.J.A. (编). Sequence A110507 (Number of nodes in the smallest cubic graph with crossing number n.). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- ^ Haythorpe, Michael; Newcombe, Alex, There are no Cubic Graphs on 26 Vertices with Crossing Number 11, 2018, arXiv:1804.10336
- ^ Exoo, G. Rectilinear Drawings of Famous Graphs.
- ^ Hliněný, P. Crossing number is hard for cubic graphs. Journal of Combinatorial Theory. Series B. 2006, 96 (4): 455–471. MR 2232384. doi:10.1016/j.jctb.2005.09.009.
- ^ Cabello S. and Mohar B. Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard. SIAM Journal on Computing. 2013, 42 (5): 1803–1829. S2CID 6535755. arXiv:1203.5944 . doi:10.1137/120872310.
- ^ Schaefer, Marcus. Complexity of some geometric and topological problems (PDF). Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. Lecture Notes in Computer Science 5849. Springer-Verlag: 334–344. 2010. ISBN 978-3-642-11804-3. doi:10.1007/978-3-642-11805-0_32 ..
- ^ Grohe, M. Computing crossing numbers in quadratic time. Journal of Computer and System Sciences. 2005, 68 (2): 285–302. MR 2059096. arXiv:cs/0009010 . doi:10.1016/j.jcss.2003.07.008.
- ^ Kawarabayashi, Ken-ichi; Reed, Bruce. Computing crossing number in linear time. Proceedings of the 29th Annual ACM Symposium on Theory of Computing: 382–390. 2007. ISBN 978-1-59593-631-8. doi:10.1145/1250790.1250848.
- ^ Even, Guy; Guha, Sudipto; Schieber, Baruch. Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas. SIAM Journal on Computing. 2003, 32 (1): 231–252. doi:10.1137/S0097539700373520.
- ^ 26.0 26.1 Oswin Aichholzer. Rectilinear Crossing Number project. (原始内容存档于2012-12-30)., and Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
- ^ Ringel, Gerhard. Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 1965, 29 (1–2): 107–117. MR 0187232. S2CID 123286264. doi:10.1007/BF02996313 (德语).
- ^ Schaefer, Marcus. The graph crossing number and its variants: a survey. The Electronic Journal of Combinatorics. 2014. DS21.
- ^ Schaefer, Marcus. Crossing Numbers of Graphs. CRC Press. 2018.