Минимальное число пересечений рёбер графа

Не следует путать с числом пересечений графа — наименьшим числом элементов в представлении графа как графа пересечений.

См. также: Число пересечений (теория узлов)

Рисунок графа Хивуда с тремя пересечениями. Это минимальное число пересечений среди всех возможных рисунков этого графа, так что число пересечений графа равно cr(G) = 3.

В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.

Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа K_m,n. Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограмм. Задача продолжает играть большую роль в визуализации графов.

Если не указано другое, число пересечений относится к представлениям графов с помощью любых кривых. Условие прямолинейных пересечений требует, чтобы все рёбра были отрезками прямых, что может изменить ответ. В частности, число прямолинейных пересечений полного графа равно минимальному числу выпуклых четырёхугольников, определённых множеством n точек в общем положении, что тесно связано с задачей со счастливым концом.

История

Во время Второй мировой войны венгерский математик Пал Туран вынужден работать на кирпичной фабрике, толкая тележку, гружёную кирпичами, от обжиговых печей в склады. На фабрике имелись колеи от каждой печи до каждого склада, и тележку труднее толкать в местах пересечения колей, что привело Турана к постановке задачи кирпичной фабрики: каково минимальное число пересечений рисунка полного графа?.

Заранкиевич (Zarankiewicz) пытался решить задачу Турана. Его доказательство содержало ошибку, но он установил правильную верхнюю границу

${\textrm {cr}}(K_{m,n})\leq \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$

для числа пересечений полного двудольного графа K_m,n. Гипотеза, что это неравенство на самом деле является равенством, известна как гипотеза Заранкиевича. Нижняя граница открыта лишь одиннадцать лет спустя после публикации почти одновременно Герхардом Рингелем и Полем Кайненом (Paul Chester Kainen).

Задача определения числа пересечений полного графа поставлена впервые Энтони Хиллом и появилась в печати в 1960. Хилл и его соавтор Джон Эрнест были двумя художниками-конструктивистами, очарованными математикой, и они не только сформулировали задачу, но и высказали для таких графов гипотезу о верхней границе числа пересечений, которую Ричард К. Гай опубликовал в 1960 году. А именно что эта граница равна

${\textrm {cr}}(K_{p})\leq {\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 ,$

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

Если разрешены только прямолинейные дуги, требуется большее число пересечений. Число прямолинейных пересечений для графов K₅ — K₁₂ равно 1, 3, 9, 19, 36, 62, 102, 153 (последовательность A014540 в OEIS). Значения для графов вплоть до K₂₇ известны. Для K₂₈ нужно либо 7233, либо 7234 пересечений. Дальнейшие значения собираются в проекте «Число прямолинейных пересечений». Интересно, что неизвестно, являются ли обычное и прямолинейное число пересечений тем же самым для полных двудольных графов. Если гипотеза Заранкиевича верна, то формула для числа пересечений полного графа асимптотически верна, то есть,

$\lim _{p\to \infty }{\textrm {cr}}(K_{p}){\tfrac {64}{p^{4}}}=1.$

К апрелю 2015 число пересечений известно для совсем небольшого числа семейств графов. В частности, за исключением нескольких начальных случаев, число пересечений полных графов, полных двудольных графов и произведения циклов остаются неизвестными. Был некоторый успех для нижней границы, согласно сообщению де Клерка, Махарри, Пасечника и Рихтера (de Klerk, Maharry, Pasechnik, Richter). Большой обзор различных вариантов приведен Шафером (Schaefer) .

Гипотеза Албертсона, сформулированная Михаэлем Альбертсоном (Michael O. Albertson) в 2007 году, утверждает, что среди всех графов с хроматическим числом n полный граф K_n имеет минимальное число пересечений. То есть, если гипотеза Гая — Саати о числе пересечения полного графа верна, любой n-хроматический граф имеет число пересечений как минимум равное формуле в гипотезе. Известно, что это выполняется для n ≤ 16.

Сложность

В общем случае определение числа пересечений графа является сложной задачей. Гарей и Джонсон (Michael Garey, David S. Johnson) в 1983 году показали, что задача эта является NP-трудной. Фактически, задача остаётся NP-трудной даже при сужении её на кубические графы и почти планарные графы (графы, которые становятся планарными после удаления одного ребра). В частности, определение числа прямолинейных пересечений является полной для экзистенциальной теории вещественных чисел.

Однако существуют эффективные алгоритмы определения, что число пересечений не превосходит фиксированной константы k. Другими словами, задача является разрешимой с фиксированным параметром. Она остаётся сложной для больших k, таких как |V|/2. Существуют также эффективные аппроксимационные алгоритмы для оценки cr(G) на графах с ограниченной степенью. На практике используются эвристистические алгоритмы, такие как простой алгоритм, начинающий с графа без рёбер и постепенно добавляющий рёбра так, чтобы получить минимально возможное добавочное число пересечений. Этот алгоритм используется в программе проекта распределённых вычислений «Число прямолинейных пересечений».

Число пересечений кубических графов

Наименьшие кубические графы с числом пересечений 1—8 известны (последовательность A110507 в OEIS).

Наименьшие кубические графы с числом пересечений:

1 — полный двудольный граф K_3,3 с 6 вершинами.

2 — граф Петерсена с 10 вершинами.

3 — граф Хивуда с 14 вершинами.

4 — граф Мёбиуса — Кантора с 16 вершинами.

5 — граф Паппа с 18 вершинами.

6 — Граф Дезарга c 20 вершинами.

7 — 4 графа с 22 вершинами (CNG 7A, CNG 7B, CNG 7C, CNG 7D).

8 — граф Науру и граф МакГи (или (3,7)-клетка) с 24 вершинами.

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

Неравенство для числа пересечений

Очень полезное неравенство для числа пересечений обнаружили независимо Аитаи, Хватал, Ньюборн (Newborn) и Семереди и Лейтон:

Для неориентированных простых графов G с n вершинами и e рёбрами, таких что e > 7n имеем:

$\operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.$

Константа 29 является наилучшей известной. Согласно Акерману константу 7 можно понизить до 4, но это будет стоить заменой константы 29 на 64.

Причиной интереса Лейтона к изучению числа пересечений было приложение к разработке СБИС микросхем в теоретической информатике. Позднее Секей также понял, что это неравенство даёт очень простые доказательства некоторых важных теорем геометрии инцидентности, таких как теорема Бека и теорема Семереди — Троттера, а Тамал Дей (Tamal Dey) использовал неравенство для доказательства верхней границы геометрических k-множеств.

Для графов с обхватом, большим 2r, и e ≥ 4n, Пах, Спенсер и Тот показали улучшение этого неравенства

$\operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.$

Доказательство неравенства для числа пересечений

Сначала дадим предварительную оценку: для любого графа G с n вершинами и e рёбрами имеем

$\operatorname {cr} (G)\geq e-3n.$

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

Для получения неравенства числа пересечений мы применяем вероятностную аргументацию. Пусть 0 < p < 1 — вероятностный параметр, который будет выбран позже. Построим случайный подграф H графа G путём расположения каждой вершины G в H независимо с вероятностью p и каждое ребро G будет находиться в H тогда и только тогда, когда обе вершины ребра лежат в H. Пусть e_H, n_H и cr_H обозначают число рёбер, вершин и пересечений графа H соответственно. Поскольку H является подграфом графа G, его диаграмма содержится в диаграмме G. По предварительному неравенству числа пересечений имеем

$\operatorname {cr} _{H}\geq e_{H}-3n_{H}.$

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

$\mathbf {E} [\operatorname {cr} _{H}]\geq \mathbf {E} [e_{H}]-3\mathbf {E} [n_{H}].$

Поскольку каждая из n вершин в G имеет вероятность p попасть в H, получим E[n_H] = pn. Таким же образом, каждое ребро в G имеет вероятность p² остаться в H, поскольку оба конца должны находиться в H. Таким образом, E[e_H] = p²e. Наконец, каждое пересечение на диаграмме G имеет вероятность p⁴ остаться в H, поскольку каждое пересечение вовлекает четыре вершины. Чтобы это понять, представим диаграмму G с cr(G) пересечениями. Можем предположить, что любые два ребра на этой диаграмме с общей вершиной не пересекаются, в противном случае обмениваем части рёбер до пересечения и число пересечений уменьшается на одно. Таким образом, можно считать, что пересечение вовлекает четыре различные вершины графа G. Вследствие этого, E[cr_H] = p⁴cr(G) и мы получаем

$p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.$

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

$\operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.$

Небольшое изменение приведённой аргументации позволяет заменить 64 на 33.75 для e > 7.5n.

См. также

• 1-планарный граф

Литература

• P. Turán. A Note of Welcome // J. Graph Theory. — 1977. — Т. 1. — doi:10.1002/jgt.3190010105.
• Urie Bronfenbrenner. The graphic presentation of sociometric data // Sociometry. — 1944. — Т. 7, вып. 3. — .
• Edward R. Scheinerman, Herbert S. Wilf. The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability // American Mathematical Monthly. — 1994. — Т. 101, вып. 10. — doi:10.2307/2975158. — .
• János Pach, Micha Sharir. 5.1 Crossings—the Brick Factory Problem // Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. — American Mathematical Society, 2009. — Т. 152. — (Mathematical Surveys and Monographs).
• K. Zarankiewicz. On a Problem of P. Turán Concerning Graphs // Fund. Math. — 1954. — Т. 41.
• R. K. Guy. Decline and fall of Zarankiewicz's Theorem // Proof Techniques in Graph Theory / ed. by F. Harary. — Academic Press, 1969.
• R. K. Guy. A combinatorial problem // Nabla (Bulletin of the Malayan Mathematical Society). — 1960. — Т. 7.
• T. L. Saaty. The minimum number of intersections in complete graphs // Proceedings of the National Academy of Sciences of the United States of America. — 1964. — Т. 52. — doi:10.1073/pnas.52.3.688.
• P. C. Kainen. On a problem of P. Erdos // Journal of Combinatorial Theory. — 1968. — Т. 5. — doi:10.1016/s0021-9800(68)80013-4.
• E. de Klerk, J. Maharry, D. V. Pasechnik, B. Richter, G. Salazar. Improved bounds for the crossing numbers of K_m,n and K_n // SIAM Journal on Discrete Mathematics. — 2006. — Т. 20, вып. 1. — doi:10.1137/S0895480104442741. Архивировано 18 июля 2011 года.
• Marcus Schaefer. The graph crossing number and its variants: a survey // The Electronic Journal of Combinatorics. — 2014.
• M. R. Garey, D. S. Johnson. Crossing number is NP-complete // SIAM J. Alg. Discr. Meth.. — 1983. — Т. 4, вып. 3. — doi:10.1137/0604033.
• L. A. Székely. Crossing numbers and hard Erdős problems in discrete geometry // Combinatorics, Probability and Computing. — 1997. — Т. 6, вып. 3. — doi:10.1017/S0963548397002976.
• T. L. Dey. Improved bounds for planar k-sets and related problems // Discrete and Computational Geometry. — 1998. — Т. 19, вып. 3. — doi:10.1007/PL00009354.
• P. Hliněný. Crossing number is hard for cubic graphs // Journal of Combinatorial Theory, Series B. — 2006. — Т. 96, вып. 4. — doi:10.1016/j.jctb.2005.09.009.
• Cabello S., Mohar B. Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard // SIAM Journal on Computing. — 2013. — Т. 42, вып. 5. — doi:10.1137/120872310.
• Marcus Schaefer. Complexity of some geometric and topological problems // International Symposium on Graph Drawing. — Springer-Verlag, 2010. — Т. 5849. — (Lecture Notes in Computer Science). — ISBN 978-3-642-11804-3. — doi:10.1007/978-3-642-11805-0_32.
• M. Grohe. Computing crossing numbers in quadratic time // J. Comput. System Sci. — 2005. — Т. 68, вып. 2. — doi:10.1016/j.jcss.2003.07.008.
• Ken-ichi Kawarabayashi, Bruce Reed. Computing crossing number in linear time // Proceedings of the 29th Annual ACM Symposium on Theory of Computing. — 2007. — ISBN 978-1-59593-631-8. — doi:10.1145/1250790.1250848.
• Guy Even, Sudipto Guha, Baruch Schieber. Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas // SIAM Journal on Computing. — 2003. — Т. 32, вып. 1. — doi:10.1137/S0097539700373520.
• E. T. Pegg, G. Exoo. Crossing Number Graphs // Mathematica Journal. — 2009. — Т. 11.
• M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi. Crossing-free subgraphs // Theory and Practice of Combinatorics. — 1982. — Т. 60. — (North-Holland Mathematics Studies).
• T. Leighton. Complexity Issues in VLSI. — Cambridge, MA: MIT Press, 1983. — (Foundations of Computing Series).
• János Pach, Joel Spencer, Géza Tóth. New bounds on crossing numbers // Discrete and Computational Geometry. — 2000. — Т. 24, вып. 4. — doi:10.1007/s004540010011.
• Eyal Ackerman. On topological graphs with at most four crossings per edge. — 2013. Архивировано 14 июля 2014 года.
• János Pach, Géza Tóth. Graphs drawn with few crossings per edge // Combinatorica. — 1997. — Т. 17, вып. 3. — doi:10.1007/BF01215922.
• János Pach, Radoš Radoičić, Gábor Tardos, Géza Tóth. Improving the crossing lemma by finding more crossings in sparse graphs // Discrete and Computational Geometry. — 2006. — Т. 36, вып. 4. — doi:10.1007/s00454-006-1264-9.
• Oswin Aichholzer. Rectilinear Crossing Number project. Архивировано 30 декабря 2012 года.
• G. Exoo. Rectilinear Drawings of Famous Graphs.
• János Barát, Géza Tóth. Towards the Albertson Conjecture. — 2009.