Интервальная размерность графа

В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 1969.

Граф пересечений прямоугольников с интервальной размерностью два

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

Примеры

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

Робертс^[1] показал, что граф с 2n вершинами, образованный удалением совершенного паросочетания из полного графа с 2n вершинами, имеет интервальную размерность в точности n — любая пара несоединённых вершин должна быть представлена в виде гиперпрямоугольников, которые должны быть разделены в отличной от другой пары размерности. Представление этого графа в виде гиперпрямоугольников с размерностью в точности n можно найти путём утолщения каждой из 2n граней n-мерного гиперкуба в гиперпрямоугольник. Вследствие этого результата такие графы начали называться графами Робертса^[2], хотя они более известны как графы «вечеринки» и их можно трактовать также как графы Турана T(2n,n).

Связь с другими классами графов

Граф имеет интервальную размерность не больше единицы тогда и только тогда, когда он является интервальным графом. Интервальная размерность произвольного графа G — это минимальное число интервальных графов с тем же множеством вершин (что и у G), таких, что пересечение множеств рёбер интервальных графов даёт G. Любой внешнепланарный граф имеет интервальную размерность, не превосходящую двух^[3], а любой планарный граф имеет интервальную размерность, не превосходящую трёх^[4].

Если двудольный граф имеет интервальную размерность два, его можно представить в виде графа пересечений параллельных осям отрезков на плоскости^[5].

Алгоритмические результаты

Многие задачи на графах могут быть решены или аппроксимированы более эффективно на графах с ограниченной интервальной размерностью. Например, задача о наибольшей клике может быть решена за полиномиальное время для графов с ограниченной интервальной размерностью^[6]. Для некоторых других задач на графах эффективное решение или аппроксимация могут быть найдены, если известно представление в виде пересечения гипермногогранников малой размерности ^[7].

Однако нахождение таких представлений может оказаться трудным делом — проверка, не превосходит ли интервальная размерность заданного графа некоторой наперёд заданной величины K, является NP-полной задачей, даже для K = 2^[8]. Чандран, Фрэнсис и Сивадасан ^[9] описали алгоритмы для нахождения представлений произвольных графов в виде графа пересечений гиперпрямоугольников с размерностью, которая находится в пределах логарифмического множителя наибольшей степени графа. Этот результат даёт верхнюю границу интервальной размерности графа.

Несмотря на трудность для естественных параметров, интервальная размерность графа является фиксированно-параметрически разрешимой задачей^[англ.], если параметризацию проводить по числу вершинного покрытия входного графа^[10].