Одночасне вкладення графів

Одноча́сне вкла́дення графів — це техніка візуалізації двох і більше різних графів на тій самій множині помічених вершин, за якої уникають схрещення ребер у кожному з графів. Схрещення між ребрами різних графів дозволяються, не дозволені тільки схрещення ребер одного графа^[1].

Якщо дозволено ребра малювати як ламані чи криві, будь-який планарний граф можна намалювати без схрещень з вершинами в довільних позиціях на площині. Якщо використати те саме розташування вершин для двох графів, отримаємо одночасне вкладення двох графів. Дослідження з одночасного вкладення концентруються на пошуку вкладення з невеликим числом перегинів (зламів) ребер, або з малим числом схрещень ребер двох графів^[1]. Вивчаються також обмежені моделі одночасного вкладення. В одночасному геометричному вкладенні кожен граф має бути намальований планарно з реберами-відрізками. Щоб гарантувати існування такого вкладення, доводиться обмежуватись підкласами планарних графів. В іншій обмеженій моделі одночасне вкладення з фіксованими ребрами, дозволені криві та вигини, але будь-яке ребро, наявне в обох графах, має бути поджане однією й тією ж кривою в поданнях обох графів. Якщо існує одночасне геометричне вкладення, воно автоматично є одночасним вкладенням із фіксованими ребрами^[1].

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

У задачах одночасного вкладення більше двох графів зазвичай вважається, що всі пари вхідних графів мають одні й самі схрещення. Тобто множини ребер і вершин утворюють соняшник^[en] . Це обмеження відоме як перетин соняшника^[1].

Багато результатів щодо одночасного геометричного вкладення ґрунтуються на ідеї, що декартові координати вершин двох заданих графів можна отримати із властивостей цих двох графів. Один з основних результатів такого типу — факт, що будь-які два шляхи на тій самій множині вершин завжди мають одночасне вкладення. Щоб знайти таке вкладення, можна використати позицію вершини у першому шляху як x-координати, а позицію вершини у другому шляху — як y-координати. У цьому випадку перший шлях буде намальований як x-монотонна ламана, яка автоматично не буде самоперетинатися, а другий шлях буде намальований як y-монотонна ламана^[2].

Подібного роду малювання розміщує вершини на цілочисельній ґратці, розміри якої лінійно залежать від розміру графа. Схоже визначене розташування також працює, якщо обидва графи є гусеницями або обидва є циклами, хоча розміри ґратки будуть більшими, проте залишаються лінійно залежними від розмірів графа. Одночасне вкладення в ґратку, що лінійно залежить від розмірів графа, можливе для будь-якого числа графів, які є зірками. Інші пари графів, що дозволяють одночасне вкладення, але, можливо, що вимагають білших розмірів ґратки, це колесо і цикл, дерево і парування, а також пари графів, у яких найбільший степінь дорівнює двом. Однак існують пари планарного графа і парування або дерева і шляху, для яких одночасного (геометричного) вкладення не існує^[3][4][5].

Перевірка, чи допускають два графи одночасне геометричне вкладення, є NP-складною задачею^[1][6]. Точніше, вона NP-складна в екзистенційній теорії дійсних чисел. З доведень цього результату також випливає, що для деяких пар графів, що мають одночасне геометричне вкладення, найменша ґратка, на якій можна намалювати графи, має розмір, що залежить двічі експоненційно від розмірів графа^[7][8].

Для одночасного вкладення з фіксованими ребрами класифікація різних видів вхідних графів, що завжди мають вкладення або іноді не мають вкладення, залежить не тільки від типів двох графів, що беруть участь, а також від структури їх перетину. Наприклад, коли обидва графи є зовніпланарними і їх перетин є лінійним лісом, завжди можна знайти таке вкладення, яке має не більше одного зламу на ребро з вершинами і точками зламу на ґратці з розміром, що поліноміально залежить від розміру графа. Існують, проте, інші пари зовніпланарних графів зі складнішими перетинами, які не мають такого вкладення. Можна також знайти одночасне вкладення з фіксованими ребрами для будь-якої пари планарного графа та дерева^[9][10][11].

Нерозв'язана проблема математики: Чи можна за поліноміальний час знайти для двох заданих графів одночасне вкладення з фіксованими ребрами? (більше нерозв'язаних проблем математики)

Є відкритою проблема, чи можна перевірити існування одночасного вкладення з фіксованими ребрами за поліноміальний час. Однак для трьох і більше графів задача NP-складна. Одночасне вкладення з фіксованими ребрами можна знайти (якщо таке існує) за поліноміальний час для пари зовнішньопланових графів, а також для пари графів, перетин яких двозв'язний^{[1][12][13][14]}.

Будь-які два планарні графи мають одночасне вкладення. Це можна зробити на ґратці поліноміального розміру, ребра при цьому матимуть не більше двох зламів. Будь-які два підгамільтонові графи мають одночасне вкладення з максимум одним зламом на ребро^[1][15].