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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Граф пересечений прямоугольников с интервальной размерностью два

В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 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] описали алгоритмы для нахождения представлений произвольных графов в виде графа пересечений гиперпрямоугольников с размерностью, которая находится в пределах логарифмического множителя наибольшей степени графа. Этот результат даёт верхнюю границу интервальной размерности графа.

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

Примечания[править | править код]

  1. ↑ Roberts, 1969.
  2. ↑ Например, см. статьи Чандрана, Фрэнсиса и Сивадасана (Chandran, Francis, Sivadasan (2010)), Чандрана и Сивадасана Chandran, Sivadasan (2007).
  3. ↑ Scheinerman, 1984.
  4. ↑ Thomassen, 1986.
  5. ↑ Bellantoni, Hartman, Przytycka, Whitesides, 1993.
  6. ↑ Чандран, Фрэнсис и Сивадасан (Chandran, Francis, Sivadasan (2010)) заметили, что это следует из факта, что эти графы имеют полиномиальное число максимальных клик. Явное представление в виде пересечения гиперпрямоугольников не требует перечисления всех максимальных клик.
  7. ↑ См., например, статьи Agarwal, van Kreveld, Suri (1998) и Berman, DasGupta, Muthukrishnan, Ramaswami (2001) для аппроксимациям наибольшего независимого множества для графов пересечений прямоугольников, и Chlebík, Chlebíková (2005) для обсуждения сложности аппроксимации этих задач для больших размерностей
  8. ↑ Коззенс (Cozzens (1981)) показал, что вычисление интервальной размерности графа является NP-полной задачей. Яннакакис (Yannakakis (1982)) показал, что даже проверка, не превосходит ли интервальная размерность величины 3, является NP-трудной. Наконец, Краточвил (Kratochvíl (1994)) показал, что распознавание интервальной размерности = 2 является NP-трудной задачей.
  9. ↑ Chandran, Francis, Sivadasan, 2010.
  10. ↑ Adiga, Chitnis, Saurabh, 2010.

Литература[править | править код]

  • Abhijin Adiga, Rajesh Chitnis, Saket Saurabh. Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I. — 2010. — Т. 6506. — С. 366–377. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-17517-6_33. (недоступная ссылка)
  • Pankaj K. Agarwal, Marc van Kreveld, Subhash Suri. Label placement by maximum independent set in rectangles // Computational Geometry Theory and Applications. — 1998. — Т. 11, вып. 3–4. — С. 209–218. — doi:10.1016/S0925-7721(98)00028-5.
  • Stephen J. Bellantoni, Irith Ben-Arroyo Hartman, Teresa Przytycka, Sue Whitesides. Grid intersection graphs and boxicity // Discrete Mathematics. — 1993. — Т. 114, вып. 1–3. — С. 41–49. — doi:10.1016/0012-365X(93)90354-V.
  • Piotr Berman, B. DasGupta, S. Muthukrishnan, S. Ramaswami. Efficient approximation algorithms for tiling and packing problems with rectangles // J. Algorithms. — 2001. — Т. 41, вып. 2. — С. 443–47. — doi:10.1006/jagm.2001.1188.
  • L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan. Geometric representation of graphs in low dimension using axis parallel boxes // Algorithmica. — 2010. — Т. 56, вып. 2. — С. 129–140. — doi:10.1007/s00453-008-9163-5. — arXiv:cs.DM/0605013.
  • L. Sunil Chandran, Naveen Sivadasan. Boxicity and treewidth // Journal of Combinatorial Theory. — 2007. — Т. 97, вып. 5. — С. 733–744. — doi:10.1016/j.jctb.2006.12.004. — arXiv:math.CO/0505544.
  • Miroslav Chlebík, Janka Chlebíková. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2005. — С. 267–276.
  • M. B. Cozzens. Higher and Multidimensional Analogues of Interval Graphs. — Rutgers University, 1981. — (Ph.D. thesis).
  • Jan Kratochvíl. A special planar satisfiability problem and a consequence of its NP–completeness // Discrete Applied Mathematics. — 1994. — Т. 52, вып. 3. — С. 233–252. — doi:10.1016/0166-218X(94)90143-0.
  • M. Quest, G. Wegner. Characterization of the graphs with boxicity ≤ 2 // Discrete Mathematics. — 1990. — Т. 81, вып. 2. — С. 187–192. — doi:10.1016/0012-365X(90)90151-7.
  • F. S. Roberts. Recent Progress in Combinatorics / W. T. Tutte. — Academic Press, 1969. — С. 301–310. — ISBN 978-0-12-705150-5.
  • E. R. Scheinerman. Intersection Classes and Multiple Intersection Parameters. — Princeton University, 1984. — (Ph. D thesis).
  • Carsten Thomassen. Interval representations of planar graphs // Journal of Combinatorial Theory, Series B. — 1986. — Т. 40. — С. 9–20. — doi:10.1016/0095-8956(86)90061-4.
  • Mihalis Yannakakis. The complexity of the partial order dimension problem // SIAM Journal on Algebraic and Discrete Methods. — 1982. — Т. 3, вып. 3. — С. 351–358. — doi:10.1137/0603036.
  • Diptendu Bhowmick, L. Sunil Chandran, Abhijin Adiga. Boxicity and Poset Dimension // SIAM Journal on Discrete Mathematics. — 2011. — Т. 25, вып. 4. — С. 1687—1698. — doi:10.1137/100786290.
Источник — https://ru.wikipedia.org/w/index.php?title=Интервальная_размерность_графа&oldid=133779334