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

В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 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].

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (19 апреля 2016) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (19 апреля 2016) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.