Топологический граф — представление графа на плоскости, в котором вершины графа представлены различными точками, а рёбра кривыми Жордана (связанные куски кривых Жордана), соединяющими соответствующие пары точек. Точки, представляющие вершины графа, и дуги, представляющие рёбра, называются вершинами и рёбрами топологического графа. Обычно предполагается, что любые два ребра топологического графа пересекаются конечное число раз, при этом ни одно ребро не проходит через вершину (кроме случая, когда вершина является конечной точкой ребра) и никакие два ребра не касаются друг друга (без пересечения). Топологический граф называется также «рисунком» графа.

Граф с числом нечётных пересечений 13 и попарным числом пересечений 15[1].

Важным специальным классом топологических графов является класс геометрических графов, в которых рёбра представлены отрезками. (Термин геометрический граф[англ.] используется и в более широком и не вполне чётком смысле.)

Теория топологических графов — это область теории графов, главным образом рассматривающая комбинаторные свойства топологических графов, в частности, вопросы пересечения рёбер. Теория тесно связана с визуализацией графов, более ориентированной на прикладную область, и топологической теорией графов, которая, в частности, специализируется на вложениях графов в поверхности (то есть их отображение без пересечений).

Экстремальные задачи топологических графов

править

Фундаментальной проблемой экстремальной теории графов является следующая: «Каково наибольшее число рёбер может иметь граф с n вершинами, если он не содержит подграфов заданного класса запретных подграфов?». Одним из начальных результатов решения этой проблемы является Теорема Турана, в которой имеется один запрещённый подграф — полный граф с k вершинами (k фиксировано). Аналогичные проблемы стоят для топологических и геометрических графов с другими запрещёнными геометрическими подконфигурациями.

Исторически, первой из теорем, касающихся указанной проблематики, была теорема Пала Эрдёша, который расширил результат Хайнца Хопфа и Эрики Паннвиц[2]. Он доказал, что максимальное число рёбер, которое может иметь геометрический граф с   вершинами, не содержащий двух непересекающихся рёбер (даже не имеющих общие конечные вершины) равно n. Джон Конвей высказал гипотезу, что это утверждение можно обобщить до простых топологических графов. Топологический граф называется «простым», если любая пара его рёбер имеет, по меньшей мере, одну общую точку, которая либо является конечной (вершиной дуги), либо общей внутренней точкой двух пересекающихся дуг. Гипотезу Конвея о треклах можно теперь переформулировать следующим образом: «Простой топологический граф с   вершинами, в котором никакие два ребра не пересекаются, имеет не более n рёбер». Первую верхнюю границу числа рёбер такого графа установили Ловас, Пах и Шегеди[3]. Наименьшую известную верхнюю границу (1,428n) нашли Фулек и Пах[4]. Помимо геометрических графов известно, что гипотеза Конвея о треклах верна для x-монотонных топологических графов[5]. Говорят, что топологический граф x-монотонен, если любая вертикальная прямая пересекает ребро максимум в одной точке.

Алон и Эрдёш[6] инициировали исследования по обобщению поставленных выше вопросов для случаев, когда запрещённая конфигурация состоит из k-непересекающихся рёбер ( ). Они доказали, что число рёбер геометрического графа с n вершинами, не содержащего 3-непересекающихся рёбер, равно O(n). Оптимальная граница около 2,5n была найдена Черни[7]. Для больших значений k первую линейную верхнюю границу   установили Пах и Теречик[8]. Её улучшил Тос до  [9]. О числе рёбер простых топологических графов, не имеющих k-непересекающихся рёбер, известна только верхняя граница  [10]. Из этого следует, что любой полный простой топологический граф с n вершинами имеет, по меньшей мере,   рёбер. Это значение улучшил до   Руиз-Варгас[11].

Квазипланарные графы

править

Общая внутренняя точка двух рёбер, в которой первое ребро проходит с одной стороны второго ребра на его другую сторону, называется пересечением. Два ребра топологического графа пересекают друг друга, если имеют пересечение. Для любого целого   топологический или геометрический граф называется k-квазипланарным, если он не имеет k попарно пересекающихся рёбер. При использовании такой терминологии, если топологический граф 2-квазипланарен, то он является планарным графом. Из формулы Эйлера следует, что любой планарный граф с   вершинами имеет не более   рёбер. Поэтому любой 2-квазипланарный граф с   вершинами имеет не более   рёбер.

Пах, Шарохи и Мари предположили[12], что любой k-квазипланарный топологический граф с n вершинами имеет не более   рёбер, где c(k) является константой, зависящей только от k. Известно, что эта гипотеза верна для  [13][14] и  [15]. Известно также, что она верна для выпуклых геометрических графов (то есть геометрических графов, вершины которых образуют выпуклый n-угольник) [16], а также для k-квазипланарных топологических графов, рёбра которых представлены как x-монотонные кривые, пересекающие вертикальную прямую[17][18]. Из последнего результата следует, что любой k-квазипланарный топологический граф с n вершинами, рёбра которого рисуются как x-монотонные кривые, имеет не более   рёбер при соответствующей константе c(k). Для геометрических графов это утверждение доказал ранее Вальтр[19]. Наименьшая известная общая верхняя граница числа рёбер k-квазипланарного топологического графа равна  [20]. Предварительная версия этого результата была опубликована в статье Якоба Фокса и Яноша Паха[21].

Числа пересечений

править

С тех пор, как Пал Туран сформулировал свою задачу о кирпичном заводе [22] во время второй мировой войны, определение или оценка числа пересечений графов была популярной темой в теории графов и теории алгоритмов[23]. Однако публикации по проблеме (явно или неявно) использовали некоторые соперничающие определения числа пересечений. На это указали Пах и Тос[9] и предложили следующую терминологию.

Число пересечений (графа G): Минимальное число точек пересечения среди всех рисунков графа G на плоскости (то есть, всех представлений графа в виде топологического графа) со свойством, что никакие три ребра не проходят через одну и ту же точку. Это число обозначается как cr(G).

Число попарных пересечений: Минимальное число пересекающихся пар рёбер среди всех рисунков графа G. Это число обозначается как pair-cr(G).

Число нечётных пересечений: Минимальное число пар рёбер, которые пересекаются нечётное число раз среди всех рисунков графа G. Это число обозначается как odd-cr(G).

Эти параметры не независимы. Имеем   для любого графа G. Известно, что  [24] и  [25], а также, что существует бесконечно много графов, для которых  [1]. Предварительная версия этих результатов была объявлена в статье Пелсмайера, Стефанковича и Шефера[26]. Неизвестно ни одного примера, в котором число пересечений и попарное число пересечений не равны. Из теоремы Ханани - Татта[англ.]*[27][28] следует, что из   вытекает  . Известно также, что из   следует   для  [29].

Другой хорошо изученный параметр графа — число прямолинейных пересечений. Это минимальное число точек пересечений среди всех рисунков графа G на плоскости с рёбрами в виде отрезков (то есть, среди всех представлений в виде геометрического графа) со свойством, что никакие три ребра не проходят через ту же самую точку. Число обозначается как lin-cr(G).

По определению имеем   для любого графа G. Биншток и Дин показали, что имеются графы с числом пересечений 4 и с произвольно большим числом прямолинейных пересечений[30].

Задачи рамсеевского типа для геометрических графов

править

В традиционной теории графов типичные результаты рамсеевского типа утверждают, что при раскрашивании рёбер достаточно большого полного графа фиксированным числом цветов, обязательно будет найден монохроматический подграф определённого типа[31]. Можно поставить подобные вопросы для геометрических (или топологических) графов, за исключением того, что в этом случае отыскиваются монохромные (одного цвета) подструктуры, удовлетворяющие определённым геометрическим условиям[32]. Один из первых результатов такого рода утверждает, что любой полный геометрический граф, рёбра которого раскрашены в два цвета, содержит непересекающееся монохроматическое остовное дерево[33]. Верно также, что любой такой геометрический граф содержит   непересекающихся рёбер одного цвета[33]. Существование непересекающихся монохромных путей размера, по меньшей мере, cn, где   является константой, остаётся давней нерешённой проблемой. Известно лишь, что любой полный геометрический граф с n вершинами содержит непересекающийся монохромный путь длиной, по меньшей мере,  [34].

Топологические гиперграфы

править

При анализе топологического графа, как топологической реализации одномерного симплициального комплекса, возникает вопрос: как описанные выше экстремальные задачи рамсеевского типа обобщить на топологическую реализацию d-мерных симплициальных комплексов. Имеется несколько начальных результатов в этом направлении, но они требуют дальнейших исследований для определения ключевых понятий и проблем[35][36][37].

Говорят, что два не имеющих общих вершин симплекса пересекаются, если их относительные внутренности имеют общую точку. Наборы из   симплексов строго пересекаются, если никакие два из них не имеют общих вершин, но все они имеют общую внутреннюю точку.

Известно, что множество d-мерных симплексов, натянутых на n точек в   без пары пересекающихся симплексов, может иметь не более   симплексов, причём эта граница асимптотически точна[38]. Этот результат был обобщён на множества двумерных симплексов в   без того, чтобы три из них сильно пересекались[39]. Если ввести запрет на k сильно пересекающихся симплексов, то соответствующая хорошо известная верхняя граница равна  [38], для некоторого  . Этот результат следует из теоремы раскраски Тверберга[40]. Полученный результат далёк от предполагаемой в гипотезе границы  [38].

Для любого фиксированного   мы можем выбрать (не более)   d-мерных симплексов, натянутых на множество из n точек в   со свойством, что никакие k из них не имеют общей внутренней точки[38][41]. Эта величина асимптотически точна.

Говорят, что два треугольника в   почти не пересекаются, если они не пересекаются, либо имеют всего одну общую вершину. Есть старая задача Гиля Калая (с соавторами): определить, равно ли   наибольшему числу почти непересекающихся треугольников, которые можно выбрать на некотором наборе вершин из n точек в  . Известно, что существуют множества из n точек, для которых это число не меньше   для соответствующей константы  [42].

Примечания

править
  1. 1 2 Pelsmajer, Schaefer, Štefankovič, 2008, с. 442–454.
  2. Hopf, Pannwitz, 1934, с. 114.
  3. Pach, Lovász, Szegedy, 1997, с. 369—376.
  4. Fulek, Pach, 2011, с. 345–355.
  5. Pach, Sterling, 2011, с. 544–548.
  6. Alon, Erdős, 1989, с. 287–290.
  7. Černý, 2005, с. 679–695.
  8. Pach, Töröcsik, 1994, с. 1–7.
  9. 1 2 Tóth, 2000, с. 126–132.
  10. Tóth, Pach, 2003, с. 133—140.
  11. Ruiz-Vargas, 2015, с. 29–34.
  12. Pach, Shahrokhi, Szegedy, 1996, с. 111–117.
  13. Agarwal, Aronov, Pach и др., 1997, с. 1–9.
  14. Ackerman, Tardos, 2007, с. 563–571.
  15. Ackerman, 2009, с. 365–375.
  16. Capoyleas, Pach, 1992, с. 9–15.
  17. Suk, 2011, с. 266–277.
  18. Fox, Pach, Suk, 2013, с. 550–561.
  19. Valtr, 1997, с. 205–218.
  20. Fox, Pach, 2012, с. 853–866.
  21. Fox, Pach, 2008, с. 346–354.
  22. Turán, 1977, с. 7–9.
  23. Garey, Johnson, 1983, с. 312–316.
  24. Tóth, Pach, 2000, с. 225–246.
  25. Matoušek, 2014, с. 135–139.
  26. Pelsmajer, Štefankovič, Schaefer, 2005, с. 386–396.
  27. Chojnacki, 1934, с. 135—142.
  28. Tutte, 1970, с. 45–53.
  29. Pelsmajer, Schaefer, Štefankovič, 2007, с. 489–500.
  30. Bienstock, Dean, 1993, с. 333–348.
  31. Graham, Rothschild, Spencer, 1990.
  32. Károlyi, 2013.
  33. 1 2 Károlyi, Pach, Tóth, 1997, с. 247–255.
  34. Károlyi, Pach, Tóth, Valtr, 1998, с. 375–388.
  35. Pach, 2004.
  36. Matoušek, Tancer, Wagner, 2009, с. 855–864.
  37. Brass, 2004, с. 25–33.
  38. 1 2 3 4 Dey, Pach, 1998, с. 473–484.
  39. Suk, 2013.
  40. Živaljević, Vrećica, 1992, с. 309–318.
  41. Bárány, Fürédi, 1987, с. 436–445.
  42. Károlyi, Solymosi, 2002, с. 577–583.

Литература

править
  • Heinz Hopf, Erika Pannwitz. Aufgabe nr. 167 // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1934. — Т. 43.
  • János Pach, László Lovász, Mario Szegedy. On Conway's thrackle conjecture // Discrete and Computational Geometry. — Springer, 1997. — Т. 18, вып. 4. — doi:10.1007/PL00009322.
  • Radoslav Fulek, János Pach. A computational approach to Conway's thrackle conjecture // Computational Geometry. — 2011. — Т. 44, вып. 6–7. — doi:10.1007/978-3-642-18469-7_21. — arXiv:1002.3904.
  • János Pach, Ethan Sterling. Conway's conjecture for monotone thrackles // American Mathematical Monthly. — 2011. — Т. 118, вып. 6. — doi:10.4169/amer.math.monthly.118.06.544.
  • Noga Alon, Paul Erdős. Disjoint edges in geometric graphs // Discrete and Computational Geometry. — 1989. — Т. 4. — doi:10.1007/bf02187731.
  • Jakub Černý. Geometric graphs with no three disjoint edges // Discrete and Computational Geometry. — 2005. — Т. 34, вып. 4. — doi:10.1007/s00454-005-1191-1.
  • János Pach, Jenö Töröcsik. Some geometric applications of Dilworth's theorem // Discrete and Computational Geometry. — 1994. — Т. 12. — doi:10.1007/BF02574361.
  • Géza Tóth. Note on geometric graphs // Journal of Combinatorial Theory. — 2000. — Т. 89. — doi:10.1006/jcta.1999.3001.
  • Géza Tóth, János Pach. Disjoint edges in topological graphs // Combinatorial Geometry and Graph Theory: Indonesia-Japan Joint Conference, IJCCGGT 2003, Bandung, Indonesia, September 13-16, 2003, Revised Selected Papers. — Springer-Verlag, 2003. — Т. 3330. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-30540-8_15.
  • Andres J. Ruiz-Vargas. Many disjoint edges in topological graphs // Proceedings of LAGOS'15. — 2015. — Т. 50. — doi:10.1016/j.endm.2015.07.006.
  • János Pach, Farhad Shahrokhi, Mario Szegedy. Applications of the crossing number // Algorithmica. — Springer, 1996. — Т. 16, вып. 1. — doi:10.1007/BF02086610.
  • Pankaj K. Agarwal, Boris Aronov, János Pach, Richard M. Pollack, Micha Sharir. Quasi-planar graphs have a linear number of edges // Combinatorica. — 1997. — Т. 17. — doi:10.1007/bf01196127.
  • Eyal Ackerman, Gábor Tardos. On the maximum number of edges in quasi-planar graphs // Journal of Combinatorial Theory. — 2007. — Т. 114, вып. 3. — doi:10.1016/j.jcta.2006.08.002.
  • Eyal Ackerman. On the maximum number of edges in topological graphs with no four pairwise crossing edges // Discrete and Computational Geometry. — 2009. — Т. 41, вып. 3. — doi:10.1007/s00454-009-9143-9.
  • Vasilis Capoyleas, János Pach. A Turán-type theorem on chords of a convex polygon // Journal of Combinatorial Theory. — 1992. — Т. 56, вып. 1. — doi:10.1016/0095-8956(92)90003-G.
  • Andrew Suk. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers. — Springer-Verlag, 2011. — Т. 7034. — doi:10.1007/978-3-642-25878-7_26. — arXiv:1106.0958.
  • Jacob Fox, János Pach, Andrew Suk. The number of edges in k-quasi-planar graphs // SIAM Journal on Discrete Mathematics. — 2013. — Т. 27, вып. 1. — doi:10.1137/110858586. — arXiv:1112.2361.
  • Pavel Valtr. Graph drawing with no k pairwise crossing edges // Graph Drawing: 5th International Symposium, GD '97 Rome, Italy, September 18–20, 1997, Proceedings. — Springer-Verlag, 1997. — Т. 1353. — (Lecture Notes in Computer Science).
  • Jacob Fox, János Pach. Coloring  -free intersection graphs of geometric objects in the plane // European Journal of Combinatorics. — 2012. — Т. 33, вып. 5. — doi:10.1016/j.ejc.2011.09.021.
  • Jacob Fox, János Pach. Coloring kk-free intersection graphs of geometric objects in the plane // =Proc. of Symposium on Computational Geometry. — College Park MD USA, 2008. — (Annual Symposium on Computational Geometry). — ISBN 978-1-60558-071-5. — doi:10.1145/1377676.1377735.
  • Paul Turán. A note of welcome // Journal of Graph Theory. — 1977. — Т. 1. — doi:10.1002/jgt.3190010105.
  • Garey M. R., Johnson D. S. Crossing number is NP-complete // SIAM Journal on Algebraic and Discrete Methods. — 1983. — Т. 4, вып. 3. — doi:10.1137/0604033.
  • Géza Tóth, János Pach. Which crossing number is it anyway? // Journal of Combinatorial Theory. — 2000. — Т. 80. — doi:10.1006/jctb.2000.1978.
  • Jiří Matoušek. Near-optimal separators in string graphs // Combin. Probab. Comput.. — 2014. — Т. 23. — doi:10.1017/S0963548313000400.
  • Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Odd crossing number and crossing number are not the same // Discrete and Computational Geometry. — 2008. — Т. 39, вып. 1-3. — doi:10.1007/s00454-008-9058-x.
  • Michael J. Pelsmajer, Daniel Štefankovič, Marcus Schaefer. Odd Crossing Number Is Not Crossing Number // Proc. of 13th International Symposium on Graph Drawing. — 2005. — doi:10.1007/11618058_35.
  • Chaim (Haim) Chojnacki (Hanani). Uber wesentlich unplattbar Kurven im dreidimensionale Raume // Fundamenta Mathematicae. — 1934. — Т. 23.
  • William T. Tutte. Toward a theory of crossing numbers // Journal of Combinatorial Theory. — 1970. — Т. 8. — doi:10.1016/s0021-9800(70)80007-2.
  • Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Removing even crossings // Journal of Combinatorial Theory. — 2007. — Т. 97, вып. 4. — doi:10.1016/j.jctb.2006.08.001.
  • Daniel Bienstock, Nathaniel Dean. Bounds for rectilinear crossing numbers // Journal of Graph Theory. — 1993. — Т. 17. — doi:10.1002/jgt.3190170308.
  • Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer. Ramsey Theory. — Wiley, 1990.
  • Gyula Károlyi. Ramsey-type problems for geometric graphs // Thirty essays on geometric graph theory / J. Pach. — Springer, 2013.
  • Gyula J. Károlyi, János Pach, Géza Tóth. Ramsey-type results for geometric graphs, I // Discrete and Computational Geometry. — 1997. — Т. 18, вып. 3. — doi:10.1007/PL00009317.
  • Gyula J. Károlyi, János Pach, Géza Tóth, Pavel Valtr. Ramsey-type results for geometric graphs, II // Discrete and Computational Geometry. — 1998. — Т. 20, вып. 3. — doi:10.1007/PL00009391.
  • János Pach. Geometric graph theory // Handbook of Discrete and Computational Geometry / Jacob E. Goodman, Joseph O'Rourke. — 2nd. — Chapman and Hall/CRC, 2004. — (Discrete Mathematics and Its Applications).
  • Jiří Matoušek, Martin Tancer, Uli Wagner. Hardness of embedding simplicial complexes in   // Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2009.
  • Peter Brass. Turán-type problems for convex geometric hypergraphs // Towards a Theory of Geometric Graphs / János Pach. — American Mathematical Society, 2004. — (Contemporary Mathematics).
  • Tamal Dey, János Pach. Extremal problems for geometric hypergraphs // Discrete and Computational Geometry. — 1998. — Т. 19, вып. 4. — doi:10.1007/PL00009365.
  • Andrew Suk. A note on geometric 3-hypergraphs // Thirty Essays on Geometric Graph Theory / János Pach. — Springer, 2013.
  • Rade T. Živaljević, Siniša T. Vrećica. The colored Tverberg's problem and complexes of injective functions // Journal of Combinatorial Theory. — 1992. — Т. 61. — doi:10.1016/0097-3165(92)90028-S.
  • Imre Bárány, Zoltán Fürédi. Empty simplices in Euclidean-space // Canadian Mathematical Bulletin. — 1987. — Т. 30, вып. 4. — doi:10.4153/cmb-1987-064-1.
  • Gyula Károlyi, József Solymosi. Almost disjoint triangles in 3-space // Discrete and Computational Geometry. — 2002. — Т. 28, вып. 4. — doi:10.1007/s00454-002-2888-z.