графа Хівуда — шість ребер мають поодинокі перетини, а решта 15 ребер не перетинаються.
У топологічній теорії графів 1-планарний граф — граф, який можна намалювати в евклідовій площині так, що кожне ребро матиме не більше одного перетину з єдиним іншим ребром.

Розфарбовування
1-планарні графи першим розглядав Рінгель, який показав, що їх можна розфарбувати, не перевищуючи 7 кольорів. Пізніше точне число кольорів, необхідне для розфарбовування цих графів, (у гіршому випадку) зменшено до 6. 1-планарний повний граф K6 є прикладом того, що 1-планарні графи іноді можуть вимагати для розфарбовування 6 кольорів. Однак доведення достатності 6 кольорів не є простим.
 Для розфарбовування вершин та граней трикутної призми потрібно 6 кольорів
До розгляду 1-планарних графів Рінгель прийшов, намагаючись розв'язати варіант задачі тотального розфарбовування для планарних графів, у якому розфарбовуються вершини та грані планарного графа так, що жодні дві суміжні вершини не мають однакового кольору і будь-які дві суміжні грані теж повинні мати різні кольори, а також повинні відрізнятися кольори вершин та суміжних їм граней. Очевидно, що це можна зробити за допомогою 8 фарб, якщо застосувати теорему про чотири фарби до графа і його двоїстого графа окремо, застосувавши два набори з 4 фарб, що не перетинаються. Однак можна отримати меншу кількість фарб, якщо сформувати допоміжний граф, що має по вершині для кожної вершини і грані початкового планарного графа, і в якому дві вершини допоміжного графа суміжні, якщо вони відповідають суміжним об'єктам заданого планарного графа. Розфарбування вершин допоміжного графа відповідає розфарбуванню початкового планарного графа. Допоміжний граф є 1-планарним, звідки випливає, що задачу Рінгеля про розфарбування вершин і граней можна розв'язати з використанням 6 кольорів. Граф K6 не можна отримати як допоміжний граф у такий спосіб, проте задача розфарбовування вершин і граней іноді вимагає 6 кольорів. Наприклад, якщо розфарбовувати планарний граф трикутної призми, для її 6 вершин + 5 граней знадобиться 6 кольорів.

Щільність ребер
Будь-який 1-планарний граф із n вершинами має не більше 4n − 8 ребер. Строгіше, кожен малюнок 1-планарного графа має не більше n − 2 перетинів. Видалення одного ребра з кожної пари ребер, що перетинаються, залишає планарний граф, який має не більше 3n − 6 ребер, звідки негайно випливає межа числа ребер 4n − 8 початкового 1-планарного графа. Однак, на відміну від планарних графів (для яких усі максимальні планарні графи на заданій множині вершин мають однакову кількість ребер), існують максимальні 1-планарні графи (графи, в які не можна додати ребро зі збереженням 1-планарності), які мають істотно менше від 4n − 8 ребер. Межу 4n − 8 максимального можливого числа ребер в 1-планарному графі можна використати, щоб показати, що повний граф K7 із сімома вершинами не є 1-планарним, оскільки цей граф має 21 ребро, а тоді 4n − 8 = 20 2,2,2,2
Повна класифікація 1-планарних повних графів, повних двочасткових графів та більш загальних повних багаточасткових графів відома. Будь-який повний двочастковий граф вигляду K2,n є 1-планарним, як і будь-який повний тричастковий граф вигляду K1,1,n. Крім цих нескінченних множин, повними багаточастковими 1-планарними графами є K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2 ,2 та його підграфи. Мінімальні повні багаточасткові графи, що не є 1-планарними, — це K3,7, K4,5, K1,3,4, K2,3,3 і K1,1,1,1,3. Наприклад, повний двочастковий граф K3,6 є 1-планарним, оскільки він є підграфом K1,1,1,6, а ось K3,7 не є 1-планарним.

Обчислювальна складність
Перевірка, чи є граф 1-планарним, NP-повна, і задача залишається NP-повною навіть для графів, отриманих із планарних графів додаванням єдиного ребра та для графів обмеженої .

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

На відміну від теореми Фарі для планарних графів, не всі 1-планарні графи можна намалювати 1-планарно з ребрами у вигляді відрізків прямих. Однак перевірити, чи можна намалювати 1-планарний граф із прямими ребрами, можна за поліноміальний час. Крім того, будь-який 3-вершинно-зв'язний 1-планарний граф має 1-планарний малюнок, у якому максимум одне ребро на зовнішній грані має злам. Такий малюнок можна побудувати за лінійний час, виходячи з 1-планарного вкладення графа. 1-планарні графи мають обмежену книжкову товщину, але деякі 1-планарні графи, включно з K2,2,2,2, мають книжкову товщину щонайменше чотири.

1-планарні графи мають обмежену локальну деревну ширину, що означає, що існує (лінійна) функція f така, що 1-планарні графи діаметра d мають деревну ширину, що не перевищує f(d). Таку ж властивість мають загальніші графи, які можна вкласти в поверхню обмеженого роду з обмеженою кількістю перетинів на ребро. Вони також мають сепаратори, невелику кількість вершин, видалення яких розбиває граф на зв'язні компоненти, розмір яких становить сталу дробову частину від усього графа. Спираючись на ці властивості, численні алгоритми для планарних графів, такі як техніка Бренди Бейкер (Brenda Sue Baker — американська математикиня) для побудови апроксимаційних алгоритмів, можна розширити на 1-планарні графи. Наприклад, цей метод приводить до схеми наближення до поліноміального часу для знаходження найбільшої незалежної множини 1-планарного графа.

Узагальнення та пов'язані концепції
Клас графів, аналогічних зовніпланарним графам для 1-планарності, називають зовні 1-планарні графи. Це графи, які можна намалювати на диску з вершинами на межі диска та з ребрами, що мають не більше одного перетину на ребро. Ці графи завжди можна намалювати (у вигляді зовні 1-планарного графа) з прямими ребрами та перетинами під прямими кутами. За допомогою динамічного програмування на SPQR-дереві заданого графа перевірити, чи є граф зовні 1-планарним, можна за лінійний час. Тризв'язні компоненти графа (вузли дерева SPQR) можуть складатися тільки з циклів, бондграфів та повних графів із 4 вершинами, звідки випливає, що зовні 1-планарні графи є планарними та мають деревну ширину максимум 3. На відміну від 1-планарних графів, зовні 1-планарні графи мають характеризацію в термінах мінорів графа — граф є зовні 1-планарним тоді й лише тоді, коли в ньому немає жодного з п'яти заборонених мінорів.

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

1-планарні графи узагальнюються до k-планарних графів, у яких кожне ребро перетинається іншими ребрами не більше k разів. Рінгель визначив локальне число перетинів графа G як найменше невід'ємне k таке, що G має k-планарний малюнок. Оскільки локальне число перетинів дорівнює найбільшому степеню графа перетинів ребер оптимального малюнка, а товщину (найменшу кількість планарних графів, на які можна розкласти ребра) можна розглядати як хроматичне число графа перетинів відповідного малюнка, з теореми Брукса випливає, що товщина не більше ніж на 1 перевищує локальне число перетинів. k-планарні графи з n вершинами мають не більше O(k1/2n) ребер та деревну ширину O((kn)1/2). Неглибокий мінор k-планарного графа з глибиною d сам є (2d + 1)k-планарним, так що неглибокі мінори 1-планарних графів і k-планарних графів є розрідженими графами, в тому сенсі, що 1-планарні і k-планарні графи мають обмежене розширення.

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

Інше пов'язане поняття для непланарних графів — , найменша кількість ребер, які потрібно видалити, щоб зробити граф планарним.

Примітки


Література
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
*  Расширенная версия статьи 17-го ACM Симпозиума по Вычислительной геометрии, 2010.
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
