Топологічний граф

Граф із числом непарних схрещень 13 і попарним числом схрещень 15^[1].

Топологі́чний граф — подання графа на площині, в якому вершини графа подано різними точками, а ребра — дугами Жордана (пов'язані шматки кривих Жордана), що з'єднують відповідні пари точок. Точки, що представляють вершини графа, і дуги, що представляють ребра, називають вершинами та ребрами топологічного графа. Зазвичай передбачається, що будь-які два ребра топологічного графа схрещуються скінченне число разів, причому жодне ребро не проходить через вершину (крім випадку, коли вершина є скінченною точкою ребра) і жодні два ребра не дотикаються між собою (без схрещень). Топологічний граф називають також малюнком графа.

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

Теорія топологічних графів — це галузь теорії графів, що розглядає переважно комбінаторні властивості топологічних графів, зокрема, питання схрещування ребер. Теорія тісно пов'язана з візуалізацією графів, більш орієнтованою на прикладну галузь, та топологічною теорією графів, яка, зокрема, спеціалізується на вкладеннях графів у поверхні (тобто їх відображення без схрещень).

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

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

Історично, першою з теорем, що стосуються зазначеної проблематики, була теорема Пала Ердеша, який розширив результат Гайнца Гопфа та Еріки Паннвіц^[2]. Він довів, що найбільша кількість ребер, яка може мати геометричний граф з ${\displaystyle n>2}$ вершинами, що не містить двох несхрещених ребер (які навіть не мають спільних кінцевих вершин) дорівнює n. Джон Конвей висловив гіпотезу, що це твердження можна узагальнити до найпростіших топологічних графів. Топологічний граф називають «простим», якщо будь-яка пара його ребер має принаймні одну спільну точку, яка або є кінцевою (вершиною дуги), або спільною внутрішньою точкою двох схрещених дуг. Гіпотезу Конвея про трекли можна тепер переформулювати так: «Простий топологічний граф з ${\displaystyle n>2}$ вершинами, в якому жодні два ребра не схрещуються, має не більше n ребер». Першу верхню межу числа ребер такого графа встановили Ловас, Пах і Шегеді^[3]. Найменшу відому верхню межу (1,428 n) знайшли Фулек і Пах^[4]. Крім геометричних графів відомо, що гіпотеза Конвея про трекли істинна для x-монотонних топологічних графів^[5]. Кажуть, що топологічний граф x-монотонний, якщо будь-яка вертикальна пряма перетинає ребро максимум в одній точці.

Алон і Ердеш^[6] ініціювали дослідження з узагальнення поставлених вище питань для випадків, коли заборонена конфігурація складається з k-несхрещених ребер (${\displaystyle k>2}$). Вони довели, що число ребер геометричного графа з n вершинами, що не містить 3-несхрещених ребер, дорівнює O(n). Оптимальну межу близько 2,5n знайшов Черні^[7]. Для більших значень k першу лінійну верхню межу ${\displaystyle O(k^{4}n)}$ встановили Пах і Теречик^[8]. Її покращив Тос до ${\displaystyle O(k^{2}n)}$^[9]. Про кількість ребер простих топологічних графів, що не мають k-несхрещених ребер, відома тільки верхня межа ${\displaystyle O(n\log ^{4k-8}n)}$^[10]. З цього випливає, що будь-який повний простий топологічний граф з n вершинами має принаймні ${\displaystyle c{\tfrac {\log n}{\log \log n}}}$ ребер. Це значення покращив до ${\displaystyle cn^{{\frac {1}{2}}-\epsilon }}$ Руїз-Варгас^[11].

Квазіпланарні графи

Спільну внутрішню точка двох ребер, у якій перше ребро проходить з одного боку другого ребра на його інший бік, називають перетином. Два ребра топологічного графа перетинаються, якщо мають перетин. Для будь-якого цілого ${\displaystyle k>1}$ топологічний або геометричний граф називають k-квазіпланарним, якщо він не має k попарно перетинних ребер. За використання такої термінології, якщо топологічний граф 2-квазіпланарний, він є планарним графом. Зі формули Ейлера випливає, що будь-який планарний граф із ${\displaystyle n>2}$ вершинами має не більше ${\displaystyle 3n-6}$ ребер. Тому будь-який 2-квазіпланарний граф з ${\displaystyle n>2}$ вершинами має не більше ${\displaystyle 3n-6}$ ребер.

Пах, Шарохі та Марі припустили^[12], що будь-який k -квазіпланарний топологічний граф з n вершинами має не більше ${\displaystyle c(k)n}$ ребер, де ${\displaystyle c(k)}$ — константа, яка залежить тільки від k. Відомо, що ця гіпотеза істинна для ${\displaystyle k=3}$^[13][14] та ${\displaystyle k=4}$^[15]. Відомо також, що вона істинна для опуклих геометричних графів (тобто геометричних графів, вершини яких утворюють опуклий n-кутник)^[16], а також для k-квазіпланарних топологічних графів, ребра яких подано як x-монотонні криві, що перетинають вертикальну пряму^[17][18]. З останнього результату випливає, що будь-який k-квазіпланарний топологічний граф з n вершинами, ребра якого малюються як x-монотонні криві, має не більше ${\displaystyle c(k)n\log n}$ ребер за відповідної константи ${\displaystyle c(k)}$. Для геометричних графів це твердження довів раніше Вальтр^[19]. Найменша відома загальна верхня межа числа ребер k-квазіпланарного топологічного графа дорівнює ${\displaystyle n\log ^{O(\log k)}n}$^[20]. Попередню версію цього результату опубліковано в статті Якоба Фокса та Яноша Паха^[21].

Числа перетинів

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

Число хрещень (графа ${\displaystyle G}$): найменша кількість точок перетину серед усіх малюнків графа ${\displaystyle G}$ на площині (тобто всіх подань графа у вигляді топологічного графа) зі властивістю, що ніякі три ребра не проходять через одну й ту саму точку. Це число позначають як ${\displaystyle cr(G)}$.

Число попарних перетинів: найменша кількість пар ребер, що перетинаються, серед усіх малюнків графа ${\displaystyle G}$. Це число позначають як ${\displaystyle pair{-}cr(G)}$.

Число непарних перетинів: найменша кількість пар ребер, які перетинаються непарне число разів серед усіх малюнків графа ${\displaystyle G}$. Це число позначають як ${\displaystyle odd{-}cr(G)}$.

Ці параметри не є незалежними. Маємо ${\displaystyle \mathrm {odd{-}cr} (G)\leqslant \mathrm {pair{-}cr} (G)\leqslant \mathrm {cr} (G)}$ для будь-якого графа ${\displaystyle G}$. Відомо що ${\displaystyle \mathrm {cr} (G)\leqslant 2(\mathrm {odd{-}cr} (G))^{2}}$^[24] та ${\displaystyle O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))}$^[25], а також, що існує нескінченно багато графів, для яких ${\displaystyle \mathrm {pair{-}cr} (G)\neq \mathrm {odd{-}cr} (G)}$^[1]. Попередн. версі. цих результатів оголошено в статті Пелсмаєра, Стефанковича та Шефера^[26]. Невідомо жодного прикладу, у якому число перетинів не дорівнює попарному числу перетинів. З теореми Ханані — Татта^[en][27][28] випливає, що з ${\displaystyle \mathrm {odd{-}cr} (G)=0}$ витікає ${\displaystyle \mathrm {cr} (G)=0}$. Відомо також, що з ${\displaystyle \mathrm {odd{-}cr} (G)=k}$ випливає ${\displaystyle \mathrm {cr} (G)=k}$ для ${\displaystyle k=1,2,3}$^[29].

Інший добре вивчений параметр графа — число прямолінійних перетинів. Це найменша кількість точок перетинів серед усіх малюнків графа ${\displaystyle G}$ на площині з ребрами у вигляді відрізків (тобто серед усіх подань у вигляді геометричного графа) з властивістю, що ніякі три ребра не проходять через ту саму точку. Число позначають як ${\displaystyle lin{-}cr(G)}$.

За визначенням маємо ${\displaystyle \mathrm {cr} (G)\leqslant \mathrm {lin{-}cr} (G)}$ для будь-якого графа ${\displaystyle G}$. Біншток і Дін показали, що є графи з числом перетинів 4 і довільно великим числом прямолінійних перетинів^[30].

Задчі рамсеївського типу для геометричних графів

У традиційній теорії графів типові результати рамсеївського типу стверджують, що при розфарбовуванні ребер досить великого повного графа фіксованою кількістю кольорів, обов'язково буде знайдено монохроматичний підграф певного типу^[31]. Можна поставити подібні питання для геометричних (або топологічних) графів, за винятком того, що в цьому випадку шукають монохроматичні (одного кольору) підструктури, що задовольняють певним геометричним умовам^[32]. Один із перших результатів такого роду стверджує, що будь-який повний геометричний граф, ребра якого розфарбовані в два кольори, містить монохроматичне кістякове дерево, що не перетинається^[33]. Правильно також, що будь-який такий геометричний граф містить ${\displaystyle \left\lceil {\frac {n+1}{3}}\right\rceil }$ неперетинних ребер одного кольору^[33]. Існування монохроматичних неперетинних шляхів розміру, принаймні, cn, де ${\displaystyle c>0}$ є сталою, залишається давньою невирішеною проблемою. Відомо лише, що будь-який повний геометричний граф з n вершинами містить монохроматичний неперетинний шлях довжиною, принаймні, ${\displaystyle n^{\frac {2}{3}}}$^[34].

Топологічні гіперграфи

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

Кажуть, що два симплекси, які не мають спільних вершин, перетинаються, якщо їхні відносні внутрішності мають спільну точку. Набори з ${\displaystyle k>3}$ симплексів строго перетинаються, якщо жодні з них не мають спільних вершин, але всі вони мають спільну внутрішню точку.

Відомо, що множина d-вимірних симплексів, натягнутих на n точок в ${\displaystyle \mathbb {R} ^{d}}$ без пари симплексів, що перетинаються, може мати не більше ${\displaystyle O(n^{d})}$ симплексів, причому ця межа асимптотично точна^[38]. Цей результат узагальнено на множини двовимірних симплексів ${\displaystyle \mathbb {R} ^{2}}$ без того, щоб три з них сильно перетиналися^[39]. Якщо ввести заборону на k симплексів, що сильно перетинаються, то відповідна добре відома верхня межа дорівнює ${\displaystyle O(n^{d+1-\delta })}$^[38], для деякого ${\displaystyle \delta =\delta (k,d)<1}$. Цей результат випливає з теореми Тверберга^[40]. Отриманий результат далекий від передбачуваної в гіпотезі межі ${\displaystyle O(n^{d})}$^[38].

Для будь-якого фіксованого ${\displaystyle k>1}$ можна вибрати (не більше) ${\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}$ d-вимірних симплексів, натягнутих на множину з n точок в ${\displaystyle \mathbb {R} ^{d}}$ зі властивістю, що жодні k з них не мають спільної внутрішньої точки^[38][41]. Ця величина асимптотично точна.

Кажуть, що два трикутники в ${\displaystyle \mathbb {R} ^{3}}$ майже не перетинаються, якщо вони не перетинаються, або мають лише одну спільну вершину. Є стара задача Гіля Калая (зі співавторами): визначити, чи дорівнює ${\displaystyle o(n^{2})}$ найбільшому числу трикутників, що майже не перетинаються, які можна вибрати на деякому наборі вершин з n точок в ${\displaystyle \mathbb {R} ^{3}}$. Відомо, що існують множини з n точок, для яких це число не менше ${\displaystyle cn^{\frac {2}{3}}}$ для відповідної константи ${\displaystyle c>0}$^[42].

Примітки

1. Pelsmajer, Schaefer, Štefankovič, 2008, с. 442–454.
2. Hopf, Pannwitz, 1934, с. 114.
3. Lovász, Pach, 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. Tóth, 2000, с. 126–132.
10. Pach, Tóth, 2003, с. 133–140.
11. Ruiz-Vargas, 2015, с. 29–34.
12. Pach, Shahrokhi, Mario, 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. Pach, Tóth, 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. 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. 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. — arXiv:1002.3904. — DOI:10.1007/978-3-642-18469-7_21.
• 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. — (Series A). — 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. — (Series A). — 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. — (Series B). — 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. — arXiv:1106.0958. — DOI:10.1007/978-3-642-25878-7_26.
• Jacob Fox, János Pach, Andrew Suk. The number of edges in k-quasi-planar graphs // SIAM Journal on Discrete Mathematics. — 2013. — Т. 27, вип. 1. — arXiv:1112.2361. — DOI:10.1137/110858586.
• 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 ${\displaystyle K_{k}}$-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. — (Series B). — 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. — (Lecture Notes in Computer Science) — 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. — (Series B). — 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 ${\displaystyle \mathbb {R} ^{d}}$ // 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. — (Series A). — 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.