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

Важливим класом топологічних графів є клас геометричних графів, у яких ребра подано відрізками. (Термін геометричний граф^[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].