1-планарный граф

В топологической теории графов 1-планарный граф — граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.

Раскраска

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

Поводом для рассмотрения 1-планарных графов Рингелем была попытка решить вариант задачи тотальной раскраски для планарных графов, в которой раскрашиваются вершины и грани планарного графа таким образом, что никакие две смежные вершины не имеют одинаковый цвет и любые две смежные грани тоже должны быть раскрашены в разные цвета, а также цвета вершин и смежных им граней должны отличаться. Очевидно, что это можно сделать с помощью восьми красок, если применить теорему о четырёх красках для графа и его двойственного графа раздельно, применив два непересекающихся набора четырёх красок. Однако можно получить меньшее количество красок, если сформировать вспомогательный граф, имеющий по вершине для каждой вершины и грани исходного планарного графа, и в котором две вершины вспомогательного графа смежны, если они соответствуют смежным объектам заданного планарного графа. Раскраска вершин вспомогательного графа соответствует раскраске исходного планарного графа. Вспомогательный граф является 1-планарным, откуда следует, что задача Рингеля раскраски вершин и граней может быть решена с использованием шести цветов. Граф K6 не может быть получен как вспомогательный граф таким образом, но, тем не менее, задача раскраски вершин и граней иногда требует шести цветов. Например, если раскрашивать планарный граф треугольной призмы, её 6 вершин + 5 граней требует шести цветов.

Плотность рёбер

Любой 1-планарный граф с n вершинами имеет не более 4n − 8 рёбер. Более строго, каждый рисунок 1-планарного графа имеет не более n − 2 пересечений. Удаление одного ребра из каждой пересекающейся пары рёбер оставляет планарный граф, который имеет не более 3n − 6 рёбер, откуда немедленно следует граница числа рёбер 4n − 8 исходного 1-планарного графа. Однако, в отличие от планарных графов (для которых все максимальные планарные графы на заданном множестве вершин имеют одинаковое число рёбер), существуют максимальные 1-планарные графы (графы, в которые нельзя добавить ребро с сохранением 1-планарности), которые имеют существенно менее 4n − 8 рёбер. Граница 4n − 8 максимального возможного числа рёбер в 1-планарном графе может быть использована, чтобы показать, что полный граф K7 с семью вершинами не является 1-планарным, поскольку этот граф имеет 21 ребро, а тогда 4n − 8 = 20 < 21 .

Говорят, что 1-планарный граф является оптимальным 1-планарным графом, если он имеет в точности 4n − 8 рёбер, максимально возможное число. В 1-планарном вложении оптимального 1-планарного графа непересекающиеся рёбра обязательно образуют разбиение на четырёхугольники (т.е. образуют полиэдральный граф, в котором каждая грань является четырёхугольником). Любое разбиение на четырёхугольники порождает 1-планарный граф путём добавления двух диагоналей в каждую квадратную грань. Отсюда следует, что любой оптимальный 1-планарный граф является эйлеровым (все его вершины имеют чётную степень), что наименьшая степень в таких графах — 6, и что любой оптимальный 1-планарный граф имеет по меньшей мере восемь вершин со степенью в точности шесть. Кроме того, любой оптимальный 1-планарный граф вершинно 4-связен и любое 4-вершинное сечение в таком графе является отсекающим циклом в нижележащем разбиении на четырёхугольники.

Графы, имеющие прямолинейные 1-планарные рисунки (то есть рисунки, в которых каждое ребро представляется прямолинейным отрезком и каждый отрезок пересекается максимум одним другим ребром), имеют слегка более сильную границу 4n − 9 максимального числа рёбер, которая достигается на бесконечном числе графов.

Полные многодольные графы

Полная классификация 1-планарных полных графов, полных двудольных графов и более общих полных многодольных графов известна. Любой полный двудольный граф вида K2,n является 1-планарным, как и любой полный трёхдольный граф вида K1,1,n. Кроме этих бесконечных множеств, полными многодольными 1-планарными графами являются K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2 и их подграфы. Минимальные полные многодольные графы, не являющиеся 1-планарными, — это K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3. Например, полный двудольный граф K3,6 является 1-планарным, поскольку он является подграфом K1,1,1,6, а вот K3,7 не является 1-планарным.

Вычислительная сложность

Проверка, является ли граф 1-планарным, NP-полна, и задача остаётся NP-полной даже для граф, полученных из планарных графов путём добавления единственного ребра и для графов ограниченной ширины.

Задача фиксированно-параметрически разрешима, если параметризовать по цикломатическому числу или по глубине дерева, так что она может быть решена за полиномиальное время, если эти параметры ограничены.

В отличие от теоремы Фари для планарных графов, не все 1-планарные графы могут быть нарисованы 1-планарно с отрезками прямой в качестве рёбер. Однако проверка, можно ли нарисовать 1-планарный граф с прямыми рёбрами, может быть выполнена за полиномиальное время. Кроме того, любой вершинно 3-связный 1-планарный граф имеет 1-планарный рисунок, в котором максимум одно ребро на внешней грани имеет изгиб. Такой рисунок может быть построен за линейное время, исходя из 1-планарного вложения графа. 1-планарные графы имеют ограниченную книжную толщину, но некоторые 1-планарные графы, включая K2,2,2,2, имеют книжную толщину по меньшей мере четыре.

1-планарные графы имеют ограниченную локальную древесную ширину, что означает, что существует (линейная) функция f, такая, что 1-планарные графы диаметра d имеют древесную ширину, не превосходящую f(d). То же свойство имеет место для более общих графов, которые можно вложить в поверхность ограниченного рода с ограниченным числом пересечений на ребро. Они также имеют сепараторы, небольшое множество вершин, удаление которых разбивает граф на связные компоненты, размер которых составляет постоянную дробную часть от всего графа. Опираясь на эти свойства многочисленные алгоритмы для планарных графов, такие как техника Бейкер (Brenda Sue Baker – американская женщина-математик ) для построения аппроксимационных алгоритмов, могут быть расширены для 1-планарных графов. Например, этот метод приводит к приближенной схеме полиномиального времени для нахождения наибольшего независимого множества 1-планарного графа.

Обобщения и связанные концепции

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

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

1-планарные графы обобщаются до k-планарных графов, в которых каждое ребро пересекается другими рёбрами не более k раз. Рингель определил локальное число пересечений графа G как наименьшее неотрицательное k, такое, что G имеет k-планарный рисунок. Поскольку локальное число пересечений равно наибольшей степени графа пересечений рёбер оптимального рисунка, а толщина (минимальное число планарных графов, на которые можно разложить рёбра) может рассматриваться как хроматическое число графа пересечений подходящего рисунка, из теоремы Брукса следует, что толщина не больше чем на единицу превышает локальное число пересечений. k-планарные графы с n вершинами имеют максимум O(k1/2n) рёбер и древесную ширину O((kn)1/2). Неглубокий минор k-планарного графа с глубиной d сам является (2d + 1)k-планарным, так что неглубокие миноры 1-планарных графов и k-планарных графов являются разреженными графами, здесь имеется в виду, что 1-планарные и k-планарные графы имеют ограниченное расшериние.

Для непланарных графов также можно задать параметр число пересечений, минимальное число рёбер, которые пересекаются в любом рисунке графа. Граф с числом пересечений k обязательно k-планарен, но обратное не обязательно верно. Например, Граф Хивуда имеет число пересечений 3, но не обязательно эти пересечения должны быть с одним ребром, он 1-планарен и может быть нарисован с одновременной опримизацией общего числа пересечений и пересечений на одно ребро.

Другое связанное понятие для непланарных графов — перекос, минимальное число рёбер, которые нужно удалить, чтобы сделать граф планарным.