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

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

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

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

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

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

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

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

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

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

Общая внутренняя точка двух рёбер, в которой первое ребро проходит с одной стороны второго ребра на его другую сторону, называется пересечением. Два ребра топологического графа пересекают друг друга, если имеют пересечение. Для любого целого [math]\displaystyle{ k \gt 1 }[/math] топологический или геометрический граф называется k-квазипланарным, если он не имеет k попарно пересекающихся рёбер. При использовании такой терминологии, если топологический граф 2-квазипланарен, то он является планарным графом. Из формулы Эйлера следует, что любой планарный граф с [math]\displaystyle{ n \gt 2 }[/math] вершинами имеет не более [math]\displaystyle{ 3n - 6 }[/math] рёбер. Поэтому любой 2-квазипланарный граф с [math]\displaystyle{ n \gt 2 }[/math] вершинами имеет не более [math]\displaystyle{ 3n - 6 }[/math] рёбер.

Пах, Шарохи и Мари предположили, что любой k-квазипланарный топологический граф с n вершинами имеет не более [math]\displaystyle{ c(k)n }[/math] рёбер, где c(k) является константой, зависящей только от k. Известно, что эта гипотеза верна для [math]\displaystyle{ k = 3 }[/math] и [math]\displaystyle{ k = 4 }[/math]. Известно также, что она верна для выпуклых геометрических графов (то есть геометрических графов, вершины которых образуют выпуклый n-угольник) , а также для k-квазипланарных топологических графов, рёбра которых представлены как x-монотонные кривые, пересекающие вертикальную прямую. Из последнего результата следует, что любой k-квазипланарный топологический граф с n вершинами, рёбра которого рисуются как x-монотонные кривые, имеет не более [math]\displaystyle{ c(k)n \log n }[/math] рёбер при соответствующей константе c(k). Для геометрических графов это утверждение доказал ранее Вальтр. Наименьшая известная общая верхняя граница числа рёбер k-квазипланарного топологического графа равна [math]\displaystyle{ n\log^{O(\log k)}n }[/math]. Предварительная версия этого результата была опубликована в статье Якоба Фокса и Яноша Паха.

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

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

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

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

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

Эти параметры не независимы. Имеем [math]\displaystyle{ \mathrm{odd{-}cr}(G) \leqslant \mathrm{pair{-}cr}(G) \leqslant \mathrm{cr}(G) }[/math] для любого графа G. Известно, что [math]\displaystyle{ \mathrm{cr}(G) \leqslant 2(\mathrm{odd{-}cr}(G))^2 }[/math] и [math]\displaystyle{ O(\operatorname{pcr}(G)^{\frac{3}{2}}\log^{2}\operatorname{pcr}(G)) }[/math], а также, что существует бесконечно много графов, для которых [math]\displaystyle{ \mathrm{pair{-}cr}(G) \ne \mathrm{odd{-}cr}(G) }[/math]. Предварительная версия этих результатов была объявлена в статье Пелсмайера, Стефанковича и Шефера. Неизвестно ни одного примера, в котором число пересечений и попарное число пересечений не равны. Из теоремы Ханани - Татта следует, что из [math]\displaystyle{ \mathrm{odd{-}cr}(G) = 0 }[/math] вытекает [math]\displaystyle{ \mathrm{cr}(G) = 0 }[/math]. Известно также, что из [math]\displaystyle{ \mathrm{odd{-}cr}(G) = k }[/math] следует [math]\displaystyle{ \mathrm{cr}(G) = k }[/math] для [math]\displaystyle{ k = 1, 2, 3 }[/math].

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

По определению имеем [math]\displaystyle{ \mathrm{cr}(G) \leqslant \mathrm{lin{-}cr}(G) }[/math] для любого графа G. Биншток и Дин показали, что имеются графы с числом пересечений 4 и с произвольно большим числом прямолинейных пересечений.

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

В традиционной теории графов типичные результаты рамсеевского типа утверждают, что при раскрашивании рёбер достаточно большого полного графа фиксированным числом цветов, обязательно будет найден монохроматический подграф определённого типа. Можно поставить подобные вопросы для геометрических (или топологических) графов, за исключением того, что в этом случае отыскиваются монохромные (одного цвета) подструктуры, удовлетворяющие определённым геометрическим условиям. Один из первых результатов такого рода утверждает, что любой полный геометрический граф, рёбра которого раскрашены в два цвета, содержит непересекающееся монохроматическое остовное дерево. Верно также, что любой такой геометрический граф содержит [math]\displaystyle{ \left\lceil \frac{n+1}{3} \right\rceil }[/math] непересекающихся рёбер одного цвета. Существование непересекающихся монохромных путей размера, по меньшей мере, cn, где [math]\displaystyle{ c \gt 0 }[/math] является константой, остаётся давней нерешённой проблемой. Известно лишь, что любой полный геометрический граф с n вершинами содержит непересекающийся монохромный путь длиной, по меньшей мере, [math]\displaystyle{ n^{\frac 23} }[/math].

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

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

Говорят, что два не имеющих общих вершин симплекса пересекаются, если их относительные внутренности имеют общую точку. Наборы из [math]\displaystyle{ k \gt 3 }[/math] симплексов строго пересекаются, если никакие два из них не имеют общих вершин, но все они имеют общую внутреннюю точку.

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

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

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