Квадратность

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

В теории графов коробчатость — это инвариант графа , введенный Фредом С. Робертсом в 1969 году.

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

Примеры

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

Робертс (1969) показал, что граф с 2 n вершинами, образованный удалением идеального паросочетания из полного графа с 2 n вершинами, имеет квадратичность ровно n : каждая пара несвязных вершин должна быть представлена ​​прямоугольниками, которые разделены в другом измерении, чем каждый другая пара. Ящиковое представление этого графа с размерностью ровно n можно найти, утолщая каждую из 2 n граней n -мерного гиперкуба в прямоугольник. Благодаря этим результатам этот граф был назван графом Робертса . хотя он более известен как граф коктейльной вечеринки , а также его можно понимать как граф Турана T (2 n , n ).

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

Граф имеет квадратичность не более единицы тогда и только тогда, когда он является интервальным графом ; квадратичность произвольного графа G — это минимальное количество интервальных графов на одном и том же наборе вершин таких, что пересечение множеств ребер интервальных графов равно G . Каждый внешнепланарный граф имеет квадратичность не более двух, и каждый планарный граф имеет квадратичность не более трех.

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

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

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

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

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

Границы

Если граф G имеет m ребер, то: $box(G)=O({\sqrt {m\cdot \log(m)}})$.

Если граф G является k - вырожденным (с $k\geq 2$) и имеет n вершин, то G имеет квадратичность $box(G)\leq (k+2)\lceil 2e\log n\rceil$.

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

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

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

Ссылки

• Адига, Абхиджин; Бхоумик, Диптенду; Чандран, Л. Сунил (2011), «Боксичность и упорядоченное измерение», SIAM Journal on Discrete Mathematics , 25 (4): 1687–1698, arXiv : 1003.2357 , doi : 10.1137/100786290 , S2CID   12656133 .
• Адига, Абхиджин; Чандран, Л. Сунил; Мэтью, Роджерс (2014), «Кубичность, вырождение и число пересечений», Европейский журнал комбинаторики , 35 : 2–12, arXiv : 1105.5225 , doi : 10.1016/j.ejc.2013.06.021 , S2CID   2069078 .
• Адига, Абхиджин; Читнис, Раджеш; Саураб, Сакет (2010), «Параметризованные алгоритмы для квадратичности», Алгоритмы и вычисления: 21-й международный симпозиум, ISAAC 2010, остров Чеджу, Корея, 15–17 декабря 2010 г., Материалы, Часть I (PDF) , Конспекты лекций по информатике , том. 6506, стр. 366–377, doi : 10.1007/978-3-642-17517-6_33 , заархивировано из оригинала (PDF) 30 августа 2017 г. , получено 22 января 2018 г.
• Агарвал, Панкадж К .; ван Кревелд, Марк; Сури, Субхаш (1998), «Размещение меток по максимально независимому множеству в прямоугольниках», Теория вычислительной геометрии и приложения , 11 (3–4): 209–218, doi : 10.1016/S0925-7721(98)00028-5 , hdl : 1874/18908 , S2CID   2381363 .
• Беллантони, Стивен Дж.; Бен-Арройо Хартман, Ирит; Пшитицка, Тереза ​​; Уайтсайдс, Сью (1993), «Графы пересечения сетки и квадратичность», Discrete Mathematics , 114 (1–3): 41–49, doi : 10.1016/0012-365X(93)90354-V .
• Берман, Петр; ДасГупта, Б.; Мутукришнан, С .; Рамасвами, С. (2001), «Эффективные алгоритмы аппроксимации для задач мозаики и упаковки прямоугольников», J. Algorithms , 41 (2): 443–470, doi : 10.1006/jagm.2001.1188 .
• Чандран, Л. Сунил; Фрэнсис, Мэтью С.; Сивадасан, Навин (2010), «Геометрическое представление графиков в низком измерении с использованием прямоугольников, параллельных осям», Algorithmica , 56 (2): 129–140, arXiv : cs.DM/0605013 , doi : 10.1007/s00453-008-9163- 5 , MR   2576537 , S2CID   17838951 .
• Чандран, Л. Сунил; Сивадасан, Навин (2007), «Боксичность и ширина дерева», Журнал комбинаторной теории , серия B , 97 (5): 733–744, arXiv : math.CO/0505544 , doi : 10.1016/j.jctb.2006.12.004 , S2CID   9854207 .
• Хлебик, Мирослав; Хлебикова, Янка (2005), «Трудность аппроксимации задач оптимизации в графах пересечений d -мерных ящиков», Труды шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 267–276 .
• Коззенс, М.Б. (1981), Высшие и многомерные аналоги интервальных графов , доктор философии. диссертация, Университет Рутгерса .
• Эспере, Луи (2016), «Боксичность и топологические инварианты», Европейский журнал комбинаторики , 51 : 495–499, arXiv : 1503.05765 , doi : 10.1016/j.ejc.2015.07.020 , S2CID   5548385 .
• Эспере, Луи; Вихерт, Вейт (2018), «Боксичность, упорядоченная размерность и исключенные миноры» , Electronic Journal of Combinatorics , 25 (4): #P4.51, arXiv : 1804.00850 , doi : 10.37236/7787 , S2CID   119148637 .
• Краточвил, Ян (1994), «Особая плоская проблема выполнимости и следствие ее NP-полноты», Discrete Applied Mathematics , 52 (3): 233–252, doi : 10.1016/0166-218X(94)90143-0 .
• Квест, М.; Вегнер, Г. (1990), «Характеризация графиков с квадратичностью ≤ 2», Discrete Mathematics , 81 (2): 187–192, doi : 10.1016/0012-365X(90)90151-7 .
• Робертс, Ф.С. (1969), «О квадратичности и кубичности графа», в Тутте, В.Т. (редактор), «Последний прогресс в комбинаторике» (PDF) , Academic Press, стр. 301–310, ISBN  978-0-12-705150-5 .
• Шайнерман, Э.Р. (1984), Классы пересечений и множественные параметры пересечений , докторская диссертация, Принстонский университет .
• Томассен, Карстен (1986), «Интервальные представления плоских графов», Журнал комбинаторной теории, серия B , 40 : 9–20, doi : 10.1016/0095-8956(86)90061-4 .
• Яннакакис, Михалис (1982), «Сложность проблемы размерности частичного порядка», SIAM Journal on Algebraic and Discrete Methods , 3 (3): 351–358, doi : 10.1137/0603036 .