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

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

Робертс[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].