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

Эта статья о графах, вложенных в плоскость, с пересечениями. Информацию о вложениях графов на другие поверхности см. в топологической теории графов .

Граф с номером нечетного пересечения 13 и номером парного пересечения 15.

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

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

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

Экстремальные задачи

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

Исторически первый пример такой теоремы принадлежит Паулю Эрдешу , который расширил результат Хайнца Хопфа и Эрики Паннвиц . Он доказал, что максимальное количество ребер, которое может иметь геометрический граф с n > 2 вершинами, не содержащий двух непересекающихся ребер (которые не могут даже иметь общую конечную точку), равно n . Джон Конвей предположил, что это утверждение можно обобщить на простые топологические графы. Топологический граф называется «простым», если любая пара его ребер имеет общую точку не более одной, которая является либо конечной точкой, либо общей внутренней точкой, в которой два ребра правильно пересекаются. Гипотезу Конвея о трекле теперь можно переформулировать следующим образом: простой топологический граф с n > 2 вершинами и без двух непересекающихся ребер имеет не более n ребер.

Первая линейная верхняя граница количества ребер такого графа была установлена ​​Ловасом и др. Самая известная верхняя граница, 1,3984 n , была доказана Фулеком и Пачем . Помимо геометрических графов, гипотеза Конвея, как известно, верна для x -монотонных топологических графов. Топологический граф называется x-монотонным, если каждая вертикальная линия пересекает все ребра не более чем в одной точке.

Алон и Эрдеш инициировал исследование обобщения поставленного вопроса на случай, когда запрещенная конфигурация состоит из k непересекающихся ребер ( k > 2). Они доказали, что число ребер геометрического графа из n вершин, не содержащих 3 непересекающихся ребер, равно O ( n ). Оптимальная граница примерно 2,5 н была определена Черным. Для больших значений k первая линейная верхняя граница $O(k^{4}n)$, была основана Пахом и Тёрёксиком. Это было улучшено Тотом до $O(k^{2}n)$. Для количества ребер в простом топологическом графе без k непересекающихся ребер только $O(n\log ^{4k-8}n)$ верхняя граница известна. Это означает, что каждый полный простой топологический граф с n вершинами имеет по крайней мере $c{\frac {\log n}{\log \log n}}$ попарно непересекающиеся ребра, что было улучшено до $cn^{{\frac {1}{2}}-\epsilon }$ Руис-Варгас. Возможно, что эта нижняя оценка может быть дополнительно улучшена до cn , где c > 0 — константа.

Квазиплоские графы

Общая внутренняя точка двух ребер, в которой первое ребро переходит с одной стороны второго ребра на другую, называется пересечением . Два ребра топологического графа пересекаются , если они определяют пересечение. Для любого целого числа k > 1 топологический или геометрический граф называется k-квазиплоским, если он не имеет k попарно пересекающихся ребер. Используя эту терминологию, если топологический граф 2-квазипланарен, то это планарный граф . следует Из формулы многогранника Эйлера , что каждый плоский граф с n > 2 вершинами имеет не более 3 n − 6 ребер. Следовательно, любой 2-квазиплоский граф с n > 2 вершинами имеет не более 3 n − 6 ребер.

Это было предположено Pach et al. что каждый k -квазиплоский топологический граф с n вершинами имеет не более c ( k ) n ребра, где c ( k ) — константа, зависящая только от k . Известно, что эта гипотеза верна для k = 3 и к = 4. Известно также, что это верно для выпуклых геометрических графов (т. е. для геометрических графов вершины которого образуют множество вершин выпуклого n -угольника), и для k -квазиплоских топологических графов, ребра которых нарисованы в виде x -монотонных кривых, каждая из которых пересекает вертикальную линию. Из последнего результата следует, что каждый k -квазиплоский топологический граф с n вершинами, ребра которого изображены в виде x -монотонных кривых, имеет не более c ( k ) n log n ребер для подходящей константы c ( k ). Для геометрических графов это ранее доказал Валтр. Самая известная общая верхняя оценка числа ребер k -квазиплоского топологического графа равна $n\log ^{O(\log k)}n$. Это означает, что каждый полный топологический граф с n вершинами имеет по крайней мере $n^{\frac {1}{O(\log \log n)}}$попарно пересекающихся ребер, которая была улучшена до квазилинейной границы в случае геометрического графа.

Пересечение чисел

Основная статья: Число пересечений (теория графов)

С тех пор, как Пал Туран придумал задачу о кирпичном заводе. во время Второй мировой войны определение или оценка чисел пересечений графов было популярной темой в теории графов и теории алгоритмов. который изобилует известными давними открытыми проблемами, такими как гипотеза Альбертсона , гипотеза Харари-Хилла или все еще нерешенная проблема кирпичного завода Турана . Однако в публикациях по данной теме (явно или неявно) использовалось несколько конкурирующих определений числа пересечений. На это указали Пах и Тот, который ввел следующую терминологию.

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

Число пересечений пар : минимальное количество пересекающихся пар ребер на всех G. рисунках Оно обозначается парой-cr( G ).

Число нечетных пересечений : минимальное количество тех пар ребер, которые пересекаются нечетное количество раз на всех рисунках G . Он обозначается нечетным cr( G ).

Эти параметры не являются несвязанными. имеется нечетный-cr( G ) ≤ пара-cr( G ) ≤ cr( G Для каждого графа G ) . Известно, что cr( G ) ≤ 2(нечетно-cr( G )) ² и $O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))$ и что существует бесконечно много графов, для которых пара-cr( G ) ≠ нечетная-cr( G ). Не известны примеры, для которых номер пересечения и номер парного пересечения не совпадают. Это следует из теоремы Ханани–Тутте что нечетное cr( G ) = 0 влечет cr( G ) = 0. Также известно, что из нечетного cr( G ) = k следует cr(G)=k для k = 1, 2, 3. Еще одним хорошо изученным параметром графика является следующий.

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

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

Вычисление числа пересечений является NP-полным. в общем. Поэтому большая часть исследований сосредоточена на его оценках. Лемма о пересечении — это краеугольный результат, который обеспечивает широко применимые нижние оценки числа пересечений. Для жордановых кривых известно несколько интересных вариантов и обобщений леммы о пересечении. и вырожденное число пересечений , где последний связывает понятие числа пересечений с родом графа .

типа Рамсея для

В традиционной теории графов типичный результат типа Рамсея гласит, что если мы раскрасим ребра достаточно большого полного графа фиксированным числом цветов, то мы обязательно найдем одноцветный подграф определенного типа. Аналогичные вопросы можно поставить и для геометрических (или топологических) графов, за исключением того, что теперь мы ищем монохроматические (одноцветные) подструктуры, удовлетворяющие определенным геометрическим условиям. Один из первых результатов такого рода гласит, что каждый полный геометрический граф, ребра которого раскрашены в два цвета, содержит непересекающееся монохроматическое остовное дерево . Верно также, что каждый такой геометрический граф содержит $\left\lceil {\frac {n+1}{3}}\right\rceil$ непересекающиеся края одного цвета. Существование непересекающегося монохроматического пути размером не менее cn , где c > 0 — константа, является давней открытой проблемой. Известно только, что каждый полный геометрический граф на n вершинах содержит непересекающийся одноцветный путь длины не менее $n^{\frac {2}{3}}$.

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

Если мы рассматриваем топологический граф как топологическую реализацию одномерного симплициального комплекса , естественно задаться вопросом, как вышеупомянутые экстремальные задачи и задачи типа Рамсея обобщаются на топологические реализации d -мерных симплициальных комплексов. Первые результаты в этом направлении имеются, но оно требует дальнейших исследований для выявления ключевых понятий и проблем.

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

Известно, что набор d -мерных симплексов, натянутый на n точек в $\mathbb {R} ^{d}$ без пары пересекающихся симплексов может иметь не более $O(n^{d})$ симплексы, и эта оценка асимптотически точна. Этот результат был обобщен на множества двумерных симплексов в $\mathbb {R} ^{2}$ без трех сильно пересекающихся симплексов. Если мы запретим k сильно пересекающихся симплексов, соответствующая наиболее известная верхняя оценка будет равна $O(n^{d+1-\delta })$, для некоторых $\delta =\delta (k,d)<1$. Этот результат следует из цветной теоремы Тверберга . Это далеко от предполагаемой границы $O(n^{d})$.

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

Два треугольника внутри $\mathbb {R} ^{3}$называются почти непересекающимися , если они не пересекаются или имеют только одну общую вершину. Это старая проблема Гила Калаи и других: решить, можно ли выбрать наибольшее число почти непересекающихся треугольников на некотором множестве вершин из n точек в $\mathbb {R} ^{3}$ является $o(n^{2})$. Известно, что существуют множества из n точек, для которых это число не менее $cn^{\frac {3}{2}}$ для подходящей константы c > 0.