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

Передумови Бензер описував концепцію, близьку до струнних графів, але для загальніших структур. У цьому контексті він також сформулював спеціальний випадок перетину інтервалів на прямій, що став класичним класом інтервальних графів. Пізніше Сінден висловив ту ж ідею для електричних мереж і друкованих схем. Математичне вивчення струнних графів почалося зі статті Ерліха, і Тарджана і, за сприяння Сіндена і Рональда Грема 1976 року опис струнних графів поставлено як відкриту проблему на 5-му угорському колоквіумі з комбінаторики. Зрештою, було доведено, що розпізнавання струнних графів є NP-повною задачею, звідки випливає, що навряд чи існує простий опис цього класуКратохвіл показав, що розпізнавання струнного графа є NP-складною задачею, але не зміг показати, що її можна розв'язати в класі NP. Після проміжних результатів Шефера та Стефанковича , Паха і Тота , Шефера, Седжвіка і Стефанковича завершено доведення, що задача NP-повна..

Пов'язані класи графів Будь-який планарний граф є струнним Шефер і Стефанкович приписують це спостереження Сіндену . — для будь-якого вкладеного в площину графа можна утворити подання у вигляді струнного графа, намалювавши для кожної вершини криву, яка обходить по колу вершину і середину кожного суміжного ребра, як показано на малюнку. Для будь-якого ребра uv графа, струни для u і v перетинаються двічі поблизу середини ребра uv, і не існує інших перетинів, так що перетини пари струн представляють суміжну пару вершин початкового планарного графа. Як варіант, за теоремою про пакування кіл, будь-який планарний граф можна подати у вигляді набору кіл, будь-які два з яких перетинаються тоді й лише тоді, коли відповідні вершини суміжні. Ці кола (з початковою і кінцевою точкою, вибраними для перетворення кола у відкриту криву) є поданням заданого планарного графа у вигляді струнного графа. Чалопін, Гонсалвіс і Ошан довели, що будь-який планарний граф має подання у вигляді струнного графа, в якому кожна пара струн має максимум один перетин, а не так, як описано вище. Гіпотеза Шейнермана, нині доведена, є навіть строгішим твердженням, що будь-який планарний граф можна подати як граф перетинів відрізків. Якщо всі ребра даного графа G розбиваються, отриманий граф є струнним графом тоді й лише тоді, коли граф G планарний. Зокрема, розбиття повного графа K5, показане на малюнку, струнним графом не є, оскільки K5 не планарний.

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

Доповнення графа будь-якого графа порівнянності також є струнним графом; . Див. також статтю Фокса і Паха ..

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

Будь-який струнний граф з m ребрами можна розбити на дві підмножини, при цьому кожна підмножина становитиме фіксовану частку від розміру всього графа, видаливши O(m3/4log1/2m) ребер. Звідси випливає, що струнні графи без клік, струнні графи, що не містять підграфів Kt,t для жодного сталого t, мають O(n) ребер і мають поліноміальне розширення.

Примітки

Література