Токсичность - Boxicity

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

В теория графов, коробочка это инвариант графа, представлен Фред С. Робертс в 1969 г.

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

Примеры

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

Робертс (1969) показал, что график с 2п вершины, образованные удалением идеальное соответствие из полный график на 2п вершины имеют прямоугольность ровно п: каждая пара несвязных вершин должна быть представлена ​​блоками, которые разделены в другом измерении, чем каждая другая пара. Коробочное представление этого графа с размером точно п можно найти, утолщив каждый из 2п грани п-размерный гиперкуб в коробку. Из-за этих результатов этот график был назван Граф Робертса,^[1] хотя он более известен как график коктейльной вечеринки и это также можно понимать как График Турана Т(2п,п).

Отношение к другим классам графов

Граф имеет коробчатость не более единицы тогда и только тогда, когда он интервальный график; коробчатость произвольного графа грамм - минимальное количество интервальных графов на одном и том же множестве вершин, такое что пересечение множеств ребер интервальных графов равно грамм. Каждые внешнепланарный граф имеет размер не более двух,^[2] и каждый планарный граф имеет размер не более трех.^[3]

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

Адига, Боумик и Чандран (2011) доказал, что коробчатость двудольного графа грамм находится в пределах коэффициента 2 от размер заказа высоты-два частично заказанный набор связано с грамм следующим образом: набор минимальных элементов соответствует одному частному набору грамм, множество максимальных элементов соответствует второму частному набору грамм, причем два элемента сравнимы, если соответствующие вершины смежны в грамм. Эквивалентно размер заказа высоты-два частично заказанный набор п находится в 2 раза меньше квадратичного размера график сопоставимости из п (который является двудольным, поскольку п имеет высоту два).

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

Многие задачи с графами могут быть решены или аппроксимированы более эффективно для графов с ограниченной прямоугольностью, чем для других графов; например, проблема максимальной клики может быть решена за полиномиальное время для графов с ограниченной коробчатостью.^[5] Для некоторых других проблем с графами эффективное решение или приближение можно найти, если известно низкоразмерное блочное представление.^[6] Однако найти такое представление может быть сложно: это НП-полный чтобы проверить, не превышает ли квадратность данного графа некоторое заданное значение K, даже для K = 2.^[7]Чандран, Фрэнсис и Сивадасан (2010) описывать алгоритмы поиска представлений произвольных графов в виде графов пересечений ящиков с размерностью, которая находится в пределах логарифмический фактор максимальная степень графа; этот результат дает верхнюю границу коробчатости графа.

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

Границы

Если график грамм график имеет м края, то:${displaystyle box (G) = O ({sqrt {mcdot log (m)}})}$.^[9][10]

Если график грамм является k-выродиться (с участием ${displaystyle kgeq 2}$) и имеет п вершины, то грамм имеет боксерский вид ${displaystyle box (G) leq (k + 2) lceil 2elog nceil}$.^[11]

Если график грамм не имеет полного графика на т вершины как незначительный, тогда ${поле displaystyle (G) = O (t ^ {2} log t)}$^[12] а есть графики без полного графика на т вершины как незначительный, и с коробкой ${displaystyle Omega (т {sqrt {log t}})}$.^[13] В частности, любой граф грамм hax boxicity ${displaystyle box (G) = O (mu (G) ^ {2} log mu (G))}$, куда ${displaystyle mu (G)}$ обозначает Инвариант Колена де Вердьера из грамм.

Связанные инварианты графа

• Кубичность определяется так же, как прямоугольность, но с параллельными осям гиперкубы вместо гипер прямоугольников. Боксичность - это обобщение кубичности.
• Сферичность определяется так же, как коробчатость, но со сферами единичного диаметра.

Примечания

Рекомендации