Просмотр кода страницы Минимальное число пересечений рёбер графа

{{не путать|Число пересечений графа|числом пересечений графа|наименьшим числом элементов в представлении графа как графа пересечений}}
{{Seealso|Число пересечений (теория узлов)}}
[[Файл:3-crossing Heawood graph.svg|thumb|Рисунок [[Граф Хивуда|графа Хивуда]] с тремя пересечениями. Это минимальное число пересечений среди всех возможных рисунков этого графа, так что число пересечений графа равно {{math|cr(''G'') {{=}} 3}}.]]
В [[Теория графов|теории графов]] '''число пересечений''' {{math|cr(''G'')}} графа {{mvar|G}} — это наименьшее число пересечений рёбер плоского [[Визуализация графов|рисунка]] графа {{mvar|G}}. Например, граф является [[Планарный граф|планарным]] [[тогда и только тогда]], когда его число пересечений равно нулю.

Математической отправной точкой изучения числа пересечений стала '''[[Проблема Заранкевича|задача Турана о кирпичной фабрике]]''', поставленная [[Туран, Пал|Палом Тураном]], в которой требовалось найти число пересечений [[Полный двудольный граф|полного двудольного графа]] {{mvar|K<sub>m,n</sub>}}{{sfn|Turán|1977|с=7—9}}. Однако та же самая задача поставлена в [[Социология|социологии]] примерно в то же самое время в связи с построением [[Социограмма|социограмм]]{{sfn|Bronfenbrenner|1944|с=283—289}}. Задача продолжает играть большую роль в [[Визуализация графов|визуализации графов]].

Если не указано другое, число пересечений относится к представлениям графов с помощью любых кривых. '''Условие прямолинейных пересечений''' требует, чтобы все рёбра были отрезками прямых, что может изменить ответ. В частности, число прямолинейных пересечений [[Полный граф|полного графа]] равно минимальному числу выпуклых четырёхугольников, определённых множеством {{mvar|n}} точек в общем положении, что тесно связано с [[Задача со счастливым концом|задачей со счастливым концом]]{{sfn|Scheinerman, Wilf|1994|с=939—943}}.

== История ==
Во время [[Вторая мировая война|Второй мировой войны]] [[Венгрия|венгерский]] математик [[Туран, Пал|Пал Туран]] вынужден работать на кирпичной фабрике, толкая тележку, гружёную кирпичами, от обжиговых печей в склады. На фабрике имелись колеи от каждой печи до каждого склада, и тележку труднее толкать в местах пересечения колей, что привело Турана к постановке задачи кирпичной фабрики: каково минимальное число пересечений рисунка [[Полный граф|полного графа]]?{{sfn|Pach, Sharir|2009|с=126—127}}.

Заранкиевич (Zarankiewicz) пытался решить задачу Турана{{sfn|Zarankiewicz|1954|с=137—145}}. Его доказательство содержало ошибку, но он установил правильную верхнюю границу

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

для числа пересечений полного двудольного графа {{mvar|K<sub>m,n</sub>}}. Гипотеза, что это неравенство на самом деле является равенством, известна как гипотеза Заранкиевича. Нижняя граница открыта лишь одиннадцать лет спустя после публикации почти одновременно [[Герхард Рингель|Герхардом Рингелем]] и Полем Кайненом (Paul Chester Kainen){{sfn|Guy|1969|с=63—69}}.
 
Задача определения числа пересечений [[Полный граф|полного графа]] поставлена впервые [[Хилл, Энтони|Энтони Хиллом]] и появилась в печати в 1960{{sfn|Guy|1960|с=68—72}}. Хилл и его соавтор [[Эрнест, Джон|Джон Эрнест]] были двумя [[Конструктивизм (искусство)|художниками-конструктивистами]], очарованными математикой, и они не только сформулировали задачу, но и высказали для таких графов гипотезу о верхней границе числа пересечений, которую [[Гай, Ричард Кеннет|Ричард К. Гай]] опубликовал в 1960 году{{sfn|Guy|1960|с=68—72}}. А именно что эта граница равна

:<math>\textrm{cr}(K_p) \le \tfrac{1}{4} \left\lfloor\tfrac{p}{2}\right\rfloor\left\lfloor\tfrac{p-1}{2}\right\rfloor\left\lfloor\tfrac{p-2}{2}\right\rfloor\left\lfloor\tfrac{p-3}{2}\right\rfloor,</math>

что даёт значения {{math|1, 3, 9, 18, 36, 60, 100, 150}} для {{math|''p'' {{=}} 5, ..., 12}} ({{OEIS|A000241}}). Независимую формулировку гипотезы дал {{не переведено 5|Саати, Томас Л.|Томас Л. Саати||Thomas L. Saaty}} в 1964 году{{sfn|Saaty|1964|с=688—690}}. Саати позднее выяснил, что верхняя граница достигается для {{math|''p'' ≤ 10}}, а Пэн и Рихтер (Pan, Richter) показали, что она достигается и для {{math|p {{=}} 11, 12}}

Если разрешены только прямолинейные дуги, требуется большее число пересечений. Число прямолинейных пересечений для графов {{math|''K''<sub>5</sub>}} — {{math|''K''<sub>12</sub>}} равно {{math|1, 3, 9, 19, 36, 62, 102, 153}} ({{OEIS|A014540}}). Значения для графов вплоть до {{math|''K''<sub>27</sub>}} известны. Для {{math|''K''<sub>28</sub>}} нужно либо 7233, либо 7234 пересечений. Дальнейшие значения собираются в проекте «Число прямолинейных пересечений»{{sfn|Aichholzer}}. Интересно, что неизвестно, являются ли обычное и прямолинейное число пересечений тем же самым для полных двудольных графов. Если гипотеза Заранкиевича верна, то формула для числа пересечений полного графа асимптотически верна{{sfn|Kainen|1968|с=374—377}}, то есть,

:<math> \lim_{p \to \infty} \textrm{cr}(K_p) \tfrac{64}{p^4} = 1. </math>

К апрелю 2015 число пересечений известно для совсем небольшого числа семейств графов. В частности, за исключением нескольких начальных случаев, число пересечений полных графов, полных двудольных графов и произведения циклов остаются неизвестными. Был некоторый успех для нижней границы, согласно сообщению де Клерка, Махарри, Пасечника и Рихтера (de Klerk, Maharry, Pasechnik, Richter){{sfn|Klerk, Maharry, Pasechnik, Richter, Salazar|2006|с=189—202}}. Большой обзор различных вариантов приведен Шафером (Schaefer) {{sfn|Schaefer|2014|с=#DS21}}.

[[Гипотеза Албертсона]], сформулированная Михаэлем Альбертсоном (Michael O. Albertson) в 2007 году, утверждает, что среди всех графов с [[Хроматическое число|хроматическим числом]] {{mvar|n}} полный граф {{mvar|K<sub>n</sub>}} имеет минимальное число пересечений. То есть, если гипотеза Гая — Саати о числе пересечения полного графа верна, любой {{mvar|n}}-хроматический граф имеет число пересечений как минимум равное формуле в гипотезе. Известно, что это выполняется для {{math|''n'' ≤ 16}}{{sfn|Barát, Tóth|2009 }}.

== Сложность ==
В общем случае определение числа пересечений графа является сложной задачей. Гарей и Джонсон (Michael Garey, David S. Johnson) в 1983 году показали, что задача эта является [[NP-полная задача|NP-трудной]]{{sfn|Garey, Johnson|1983|с=312—316}}. Фактически, задача остаётся NP-трудной даже при сужении её на [[Кубический граф|кубические графы]]{{sfn|Hliněný|2006|с=455—471}} и почти планарные графы{{sfn|Cabello, Mohar|2013|с=1803—1829 }} (графы, которые становятся планарными после удаления одного ребра). В частности, определение числа прямолинейных пересечений является {{не переведено 5|Полная сложность|полной||Complete (complexity)}} для [[Экзистенциальная теория вещественных чисел|экзистенциальной теории вещественных чисел]]{{sfn|Schaefer|2010|с=334—344}}.

Однако существуют эффективные алгоритмы определения, что число пересечений не превосходит фиксированной константы {{mvar|k}}. Другими словами, задача является {{не переведено 5| Задача, разрешимая с фиксированным параметром| разрешимой с фиксированным параметром||fixed-parameter tractable}}{{sfn|Grohe|2005|с=285—302}}{{sfn|Kawarabayashi, Reed|2007|с=382—390}}. Она остаётся сложной для больших ''k'', таких как |''V''|/2. Существуют также эффективные [[Аппроксимационный алгоритм|аппроксимационные алгоритмы]] для оценки {{math|cr(''G'')}} на графах с ограниченной степенью{{sfn|Even, Guha, Schieber|2003|с=231—252}}. На практике используются [[Эвристика|эвристистические]] алгоритмы, такие как простой алгоритм, начинающий с графа без рёбер и постепенно добавляющий рёбра так, чтобы получить минимально возможное добавочное число пересечений. Этот алгоритм используется в программе проекта [[Распределённые вычисления|распределённых вычислений]] «Число прямолинейных пересечений»<ref>[http://dist.ist.tugraz.at/cape5/ Rectilinear Crossing Number], Институт Программных технологий Граца, Технологический университет (2009).</ref>.

== Число пересечений кубических графов ==
Наименьшие [[Кубический граф|кубические графы]] с числом пересечений 1—8 известны ({{OEIS|id=A110507}}).

Наименьшие кубические графы с числом пересечений 
:1 — [[полный двудольный граф]] {{math|''K''<sub>3,3</sub>}} с 6 вершинами. 
:2 — [[граф Петерсена]] с 10 вершинами. 
:3 — [[граф Хивуда]] с 14 вершинами. 
:4 — [[граф Мёбиуса — Кантора]] с 16 вершинами. 
:5 — [[граф Паппа]] с 18 вершинами. 
:6 — [[Граф Дезарга]] c 20 вершинами. 
:7 — Нет (22 вершин).<ref>{{MathWorld|urlname=GraphCrossingNumber|title=Graph Crossing Number}}</ref> 
:8 — [[граф Науру]] и [[граф МакГи]] (или (3,7)-[[Клетка (теория графов)|клетка]]) с 24 вершинами.

В 2009 году Икзу (Exoo) предположил, что наименьшим кубическим графом с числом пересечений 11 является [[граф Коксетера]], с числом пересечений 13 — [[граф Татта — Коксетера]], с числом пересечений 170 — [[12-клетка Татта]]{{sfn|Exoo|}}{{sfn|Pegg, Exoo|2009}}.

== Неравенство для числа пересечений ==
Очень полезное ''неравенство для числа пересечений'' обнаружили независимо {{не переведено 5|Аитаи, Миклош|Аитаи||Miklós Ajtai}}, {{не переведено 5|Хватал, Вашек|Хватал||Václav Chvátal}}, Ньюборн (Newborn) и [[Семереди, Эндре|Семереди]]{{sfn|Ajtai, Chvátal, Newborn, Szemerédi|1982|с=9—12}} и Лейтон{{sfn|Leighton| 1983}}:

:Для неориентированных [[Простой граф|простых графов]] {{mvar|G}} с {{mvar|n}} вершинами и {{mvar|e}} рёбрами, таких что {{math|''e'' > 7''n''}} имеем:
::<math>\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.</math>

Константа {{math|29}} является наилучшей известной. Согласно Акерману<ref>{{sfn0|Ackerman|2013}}. Для более ранних результатов с другими константами смотрите Пах и Тоф{{sfn0|Pach, Tóth|1997|с=427—439}}, Пах, Радчик, Тардос и Тоф{{sfn0|Pach, Radoičić, Tardos, Tóth|2006|с= 527—552}}</ref> константу {{math|7}} можно понизить до {{math|4}}, но это будет стоить заменой константы {{math|29}} на {{math|64}}.

Причиной интереса Лейтона к изучению числа пересечений было приложение к разработке [[Интегральная схема|СБИС]] микросхем в теоретической информатике. Позднее Секей{{sfn|Székely|1997|с=353—358}} также понял, что это неравенство даёт очень простые доказательства некоторых важных теорем [[Инцидентность (геометрия)|геометрии инцидентности]], таких как [[Теорема Бека (геометрия)|теорема Бека]] и [[теорема Семереди — Троттера]], а Тамал Дей (Tamal Dey) использовал неравенство для доказательства верхней границы {{не переведено 5|K-множество (геометрия)|геометрических ''k''-множеств||K-set (geometry)}}{{sfn|Dey|1998|с=373—382}}.

Для графов с [[Обхват (теория графов)|обхватом]], большим {{math|2''r''}}, и {{math|''e'' ≥ 4''n''}}, Пах, Спенсер и Тот{{sfn|Pach, Spencer, Tóth|2000|с=623—644}} показали улучшение этого неравенства

:<math>\operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}.</math>

=== Доказательство неравенства для числа пересечений ===
Сначала дадим предварительную оценку: для любого графа {{mvar|G}} с {{mvar|n}} вершинами и {{mvar|e}} рёбрами имеем

: <math>\operatorname{cr}(G) \geq e - 3n.</math>

Для доказательства представим рисунок графа {{mvar|G}} с точно {{math|cr(''G'')}} пересечениями. Каждое такое пересечение можно удалить вместе с удалением ребра из {{mvar|G}}. Таким образом мы можем найти граф по меньшей мере с {{math|''e'' − cr(''G'')}} рёбрами и {{mvar|n}} вершинами с нулевым числом пересечений, а следовательно, это будет [[планарный граф]]. Но из [[Планарный граф|формулы Эйлера]] мы должны иметь {{math|''e'' − cr(''G'') ≤ 3''n''}}, откуда получаем требуемое неравенство. (Фактически, мы имеем {{math|''e'' − cr(''G'') ≤ 3''n'' − 6}} для {{math|''n'' ≥ 3}}).

Для получения неравенства числа пересечений мы применяем [[Вероятностный метод|вероятностную аргументацию]]. Пусть {{math|0 < ''p'' < 1}} — [[Вероятность|вероятностный]] параметр, который будет выбран позже. Построим [[Случайный граф|случайный подграф]] {{mvar|H}} графа {{mvar|G}} путём расположения каждой вершины {{mvar|G}} в {{mvar|H}} независимо с вероятностью {{mvar|p}} и каждое ребро {{mvar|G}} будет находиться в {{mvar|H}} тогда и только тогда, когда обе вершины ребра лежат в {{mvar|H}}. Пусть {{mvar|e<sub>H</sub>, n<sub>H</sub>}} и {{math|cr<sub>''H''</sub>}} обозначают число рёбер, вершин и пересечений графа {{mvar|H}} соответственно. Поскольку {{mvar|H}} является подграфом графа {{mvar|G}}, его диаграмма содержится в диаграмме {{mvar|G}}. По предварительному неравенству числа пересечений имеем

: <math>\operatorname{cr}_H \geq e_H - 3n_H.</math>

Вычисляя [[Математическое ожидание|математические ожидания]], получим

: <math>\mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] - 3 \mathbf{E}[n_H].</math>

Поскольку каждая из {{mvar|n}} вершин в {{mvar|G}} имеет вероятность {{mvar|p}} попасть в {{mvar|H}}, получим {{math|'''E'''[''n<sub>H</sub>''] {{=}} ''pn''}}. Таким же образом, каждое ребро в {{mvar|G}} имеет вероятность {{math|''p''<sup>2</sup>}} остаться в {{mvar|H}}, поскольку оба конца должны находиться в {{mvar|H}}. Таким образом, {{math|'''E'''[''e<sub>H</sub>''] {{=}} ''p''<sup>2</sup>''e''}}. Наконец, каждое пересечение на диаграмме {{mvar|G}} имеет вероятность {{math|''p''<sup>4</sup>}} остаться в {{mvar|H}}, поскольку каждое пересечение вовлекает четыре вершины. Чтобы это понять, представим диаграмму {{mvar|G}} с {{math|cr(''G'')}} пересечениями. Можем предположить, что любые два ребра на этой диаграмме с общей вершиной не пересекаются, в противном случае обмениваем части рёбер до пересечения и число пересечений уменьшается на одно. Таким образом, можно считать, что пересечение вовлекает четыре различные вершины графа {{mvar|G}}. Вследствие этого, {{math|'''E'''[cr<sub>''H''</sub>] {{=}} ''p''<sup>4</sup>cr(''G'')}} и мы получаем

: <math> p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n.</math>

Теперь, если мы положим {{math|''p'' {{=}} 4''n''/''e'' < 1}} (поскольку мы предположили, что {{math|''e'' > 4''n''}}), после некоторых алгебраических выкладок, получим

: <math> \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}.</math>

Небольшое изменение приведённой аргументации позволяет заменить {{math|64}} на {{math|33.75}} для {{math|''e'' > 7.5''n''}}{{sfn|Ackerman|2013}}.

== См. также ==
* [[1-планарный граф]]

== Примечания ==
{{примечания|2}}

== Литература ==
* {{статья
|doi=10.1002/jgt.3190010105 
|автор=P. Turán 
|заглавие=A Note of Welcome 
|издание=J. Graph Theory 
|том=1 
|год=1977 
|ref= Turán
}}
* {{статья
|заглавие=The graphic presentation of sociometric data
|автор=Urie Bronfenbrenner
|издание=Sociometry
|том=7
|выпуск=3
|год=1944
|jstor=2785096
|ref=Bronfenbrenner
}}
* {{статья 
|заглавие=The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability 
|автор=Edward R. Scheinerman, Herbert S. Wilf
|издание=[[American Mathematical Monthly]] 
|том=101 
|выпуск=10 
|год=1994
|doi=10.2307/2975158 
|jstor=2975158 
|ref= Scheinerman, Wilf
}}
* {{книга
|автор = János Pach, Micha Sharir 
|часть = 5.1 Crossings—the Brick Factory Problem
|издательство = [[American Mathematical Society]] 
|серия= Mathematical Surveys and Monographs 
|заглавие= Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures 
|том = 152
|год= 2009
|ref= Pach, Sharir 
}}
* {{статья
|автор=K. Zarankiewicz 
|заглавие=On a Problem of P. Turán Concerning Graphs 
|издание=Fund. Math
|том=41 
|год=1954
|ref= Zarankiewicz
}}
* {{статья 
|заглавие=Decline and fall of Zarankiewicz's Theorem
|автор=R. K. Guy 
|издание=Proof Techniques in Graph Theory 
|ответственный=ed. by F. Harary
|издательство=Academic Press
|год=1969
|ref=Guy
}}
* {{статья
|заглавие=A combinatorial problem
|автор=R. K. Guy |authorlink=Richard K. Guy 
|издание=Nabla (Bulletin of the Malayan Mathematical Society) 
|том=7 
|год=1960 
|ref=Guy
}}
* {{статья
|заглавие=The minimum number of intersections in complete graphs 
|автор=T. L. Saaty
|издание=Proceedings of the National Academy of Sciences of the United States of America
|том=52 
|год=1964
|ref= Saaty
|doi=10.1073/pnas.52.3.688
}}
* {{статья
|заглавие=On a problem of P. Erdos
|автор=P. C. Kainen
|издание=Journal of Combinatorial Theory
|том=5 
|год=1968 
|ref= Kainen
|doi=10.1016/s0021-9800(68)80013-4
}}
* {{статья
 |автор       = E. de Klerk, J. Maharry, D. V. Pasechnik, B. Richter, G. Salazar
 |год           = 2006
 |ссылка     = http://arno.uvt.nl/show.cgi?fid=71701
 |заглавие = Improved bounds for the crossing numbers of ''K<sub>m,n</sub>'' and ''K<sub>n</sub>''
 |издание   = [[SIAM Journal on Discrete Mathematics]]
 |том           = 20
 |выпуск     = 1
 |doi              = 10.1137/S0895480104442741
 |ref              = Klerk, Maharry, Pasechnik, Richter, Salazar
 |archiveurl       = https://web.archive.org/web/20110718170724/http://arno.uvt.nl/show.cgi?fid=71701
 |archivedate      = 2011-07-18
}}
* {{статья
|автор= Marcus Schaefer
|издание= [[The Electronic Journal of Combinatorics]]
|заглавие= The graph crossing number and its variants: a survey
|год = 2014
|ref= Schaefer
}}
* {{статья 
|автор=[[Michael Garey|M. R. Garey]], [[David S. Johnson|D. S. Johnson]] 
|заглавие=Crossing number is NP-complete 
|издание=SIAM J. Alg. Discr. Meth. 
|том=4 
|год=1983 
|mr=0711340 
|doi=10.1137/0604033 
|выпуск=3 
|ref= Garey, Johnson
}}
* {{статья 
|автор=L. A. Székely 
|заглавие=Crossing numbers and hard Erdős problems in discrete geometry 
|издание=Combinatorics, Probability and Computing 
|том=6 
|год=1997 
|mr=1464571 
|doi=10.1017/S0963548397002976 
|выпуск=3 
|ref= Székely
}}
* {{статья
|автор=T. L. Dey
|заглавие= Improved bounds for planar ''k''-sets and related problems 
|издание= [[Discrete and Computational Geometry]] 
|том= 19 
|выпуск= 3 
|год= 1998 
|doi= 10.1007/PL00009354 
|mr= 1608878 
|ref = Dey
}}
* {{статья 
|автор=P. Hliněný 
|заглавие=Crossing number is hard for cubic graphs 
|год=2006 
|издание=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] 
|том=96 
|выпуск=4 
|mr=2232384 
|doi=10.1016/j.jctb.2005.09.009 
|ref= Hliněný
}}
* {{статья 
|автор=Cabello S., Mohar B. 
|заглавие=Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard 
|год=2013 
|издание=SIAM Journal on Computing 
|том=42 
|выпуск=5 
|doi=10.1137/120872310 
|ref= Cabello, Mohar
}}
* {{книга
|автор=Marcus Schaefer
|часть=Complexity of some geometric and topological problems
|ссылка=http://ovid.cs.depaul.edu/documents/convex.pdf
|заглавие=International Symposium on Graph Drawing|Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers
|серия=Lecture Notes in Computer Science
|издательство=Springer-Verlag
|том=5849
|doi=10.1007/978-3-642-11805-0_32 
|год=2010
|ref=Schaefer
|isbn=978-3-642-11804-3
}}
* {{статья 
|автор=M. Grohe
|заглавие=Computing crossing numbers in quadratic time 
|издание=J. Comput. System Sci
|том=68 
|выпуск=2 
|год=2005 
|mr=2059096 
|doi=10.1016/j.jcss.2003.07.008 
|ref= Grohe
}} 
* {{книга 
|автор= Ken-ichi Kawarabayashi, Bruce Reed
|часть=Computing crossing number in linear time 
|заглавие=Proceedings of the 29th Annual ACM Symposium on Theory of Computing 
|год=2007
|doi=10.1145/1250790.1250848 
|ref= Kawarabayashi, Reed
|isbn= 978-1-59593-631-8
}}
* {{статья 
|автор=Guy Even, Sudipto Guha, Baruch Schieber 
|заглавие=Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas 
|издание=[[SIAM Journal on Computing]] 
|том=32 
|год=2003
|doi=10.1137/S0097539700373520 
|выпуск=1 
|ref= Even, Guha, Schieber
}}
* {{статья 
|автор=E. T. Pegg, G. Exoo 
|заглавие=Crossing Number Graphs 
|издание=Mathematica Journal 
|том=11 
|год=2009 
|ref= Pegg, Exoo
}}
* {{книга
|автор=M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi
|часть=Crossing-free subgraphs
|заглавие=Theory and Practice of Combinatorics
|серия=North-Holland Mathematics Studies
|том=60
|год=1982
|mr=0806962 
|ref= Ajtai, Chvátal, Newborn, Szemerédi 
}}
* {{книга 
|автор=T. Leighton 
|заглавие=Complexity Issues in VLSI 
|серия=Foundations of Computing Series 
|издательство=MIT Press 
|место=Cambridge, MA 
|год=1983
|ref= Leighton
}}
* {{статья
| издание = [[Discrete and Computational Geometry]] 
| год=2000 
| том=24 
| выпуск=4 
| заглавие =New bounds on crossing numbers 
| автор=János Pach, Joel Spencer, Géza Tóth 
| ref= Pach, Spencer, Tóth
| doi=10.1007/s004540010011
}}
* {{статья
 |заглавие = On topological graphs with at most four crossings per edge
 |автор       = Eyal Ackerman
 |ссылка     = http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf
 |год           = 2013
 |ref              = Ackerman
 |archiveurl       = https://web.archive.org/web/20140714181310/http://sci.haifa.ac.il/~ackerman/publications/4crossings.pdf
 |archivedate      = 2014-07-14
}}
* {{статья |автор=János Pach, Géza Tóth |doi=10.1007/BF01215922 |выпуск=3 |издание=[[Combinatorica]] |mr=1606052 |заглавие=Graphs drawn with few crossings per edge |том=17 |год=1997 |ref=Pach, Tóth}} 
* {{статья |автор=János Pach, Radoš Radoičić, Gábor Tardos, Géza Tóth |doi=10.1007/s00454-006-1264-9 |выпуск=4 |издание=[[Discrete and Computational Geometry]] |mr=2267545 |заглавие= Improving the crossing lemma by finding more crossings in sparse graphs |том=36 |год=2006 |ref=Pach, Radoičić, Tardos, Tóth}}
* {{статья |ссылка=http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ |заглавие=Rectilinear Crossing Number project |автор=Oswin Aichholzer |ref=Aichholzer |издание= |archiveurl=https://archive.is/20121230191705/http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ |archivedate=2012-12-30 }}
* {{статья |автор=G. Exoo |ссылка=http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/ |заглавие=Rectilinear Drawings of Famous Graphs |ref=Exoo}}
* {{статья |автор=János Barát, Géza Tóth |год=2009 |заглавие=Towards the Albertson Conjecture |eprint=0909.0413 |ref=Barát, Tóth }}

{{rq|checktranslate|style}}

[[Категория:Топологическая теория графов]]
[[Категория:Неравенства]]
[[Категория:Инварианты графов]]