Інтервальна розмірність графа

У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році.

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

Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини.

Приклади

На рисунку показано граф із шістьма вершинами і подання цього графа у вигляді графа перетинів (звичайних двовимірних) прямокутників. Цей граф можна подати у вигляді графа перетинів прямокутників меншої розмірності (в даному випадку — відрізків), так що інтервальна розмірність графа дорівнює двом.

Робертс показав, що граф з 2n вершинами, утворений видаленням досконалого парування з повного графа з 2n вершинами, має інтервальну розмірність рівно n — будь-яку пару нез'єднаних вершин слід подати у вигляді гіперпрямокутників, які мають бути розділені у відмінному від іншої пари вимірі. Подання цього графа у вигляді гіперпрямокутників з розмірністю рівно n можна знайти потовщенням кожної з 2n граней n-вимірного гіперкуба до гіперпрямокутника. Тому такі графи почали називати графами Робертса, хоча вони відоміші як графи вечірки і їх можна трактувати також як графи Турана T(2n,n).

Зв'язок з іншими класами графів

Граф має інтервальну розмірність не більше одиниці тоді і тільки тоді, коли він є інтервальним графом. Інтервальна розмірність довільного графа G — це найменше число інтервальних графів з тією ж множиною вершин (що і G), таких, що перетин множин ребер інтервальних графів дає G. Інтервальна розмірність будь-якого зовніпланарного графа не перевищує двох, а будь-якого планарного графа — трьох.

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

Алгоритмічні результати

Багато задач на графах можна розв'язати або на графах з обмеженою інтервальною розмірністю. Наприклад, задачу про найбільшу кліку для графів з обмеженою інтервальною розмірністю можна розв'язати за поліноміальний час. Для деяких інших задач на графах ефективний розв'язок або апроксимацію можна знайти, якщо існує подання у вигляді перетину гіпербагатогранників малої розмірності.

Однак знаходження таких подань може виявитися складним — перевірка, чи не перевершує інтервальна розмірність заданого графа деякої наперед заданої величини K, є NP-повною задачею, навіть для K = 2. Чандран, Френсіс і Сівадасан описали алгоритми знаходження подань довільних графів у вигляді графа перетинів гіперпрямокутників з розмірністю в межах логарифмічного множника найбільшого степеня графа. Цей результат дає верхню межу інтервальної розмірності графа.

Попри труднощі для природних параметрів, інтервальна розмірність графа є ^[en], якщо параметризацію проводити за числом вершинного покриття вхідного графа.

Примітки

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.^{[недоступне посилання з червня 2018]}
• Pankaj K. Agarwal, Marc van Kreveld, Subhash Suri. Label placement by maximum independent set in rectangles // . — 1998. — Т. 11, вип. 3–4 (17 червня). — С. 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 // . — 1993. — Т. 114, вип. 1–3 (17 червня). — С. 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 (17 червня). — С. 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 (17 червня). — С. 129–140. — arXiv:cs.DM/0605013. — DOI:10.1007/s00453-008-9163-5.
• L. Sunil Chandran, Naveen Sivadasan. Boxicity and treewidth // . — 2007. — Т. 97, вип. 5 (17 червня). — С. 733–744. — (). — arXiv:math.CO/0505544. — DOI:10.1016/j.jctb.2006.12.004.
• 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 (17 червня). — С. 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 (17 червня). — С. 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. — .
• 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 (17 червня). — С. 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 (17 червня). — С. 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 (17 червня). — С. 1687—1698. — DOI:10.1137/100786290.