Зовніпланарний граф

Зовніпланарні графи мають характеризацію забороненими графами, аналогічну теоремі Понтрягіна — Куратовського і теоремі Вагнера для планарних графів — граф зовніпланарний тоді й лише тоді, коли він не містить підрозбиття повного графу K₄ або повного дводольного графу K_2,3[3]. Альтернативно, граф зовніпланарний тоді й лише тоді, коли він не містить K₄ або K_2,3 як мінор, графу, отриманого видаленням і стягуванням ребер[4].

Граф без трикутників зовніпланарний тоді й лише тоді, коли він не містить підрозділів K_2,3[5].

Граф зовніпланарний тоді й лише тоді, коли його інваріант Колена де Вердьєра не перевищує двох. Графи, що характеризуються подібним чином за значенням інваріанта Колена де Вердьєра (який не перевершує значення 1, 3 або 4) — це лінійні ліси, планарні графи і вклада́нні без зачеплення графи.

Зовніпланарний граф є двозв'язним тоді й лише тоді, коли зовнішня грань утворює простий цикл без повторення вершин. Зовніпланарний граф є гамільтоновим тоді й лише тоді, коли він двозв'язний. У цьому випадку зовнішня грань утворює єдиний гамільтонів цикл[1][5]. Загальніше, розмір найдовшого циклу в зовніпланарному графі дорівнює числу вершин найбільшої двозв'язної компоненти. З цієї причини пошук гамільтонових циклів і найдовших циклів у зовніпланарних графах можна здійснити за лінійний час, на противагу до NP-повноти цих задач для довільних графів.

Будь-який максимальний зовніпланарний граф задовольняє сильнішим умовам, ніж гамільтоновість — він вершинно панциклічний, що означає, що для будь-якої вершини v і будь-якого числа k в інтервалі від трьох до числа вершин графу існує цикл довжини k, що містить v. Цикл такої довжини можна знайти послідовним видаленням трикутників, сполучених з залишком графу єдиним ребром, таких, що вилучена вершина не збігається з v, поки зовнішня грань решти графу не набуде довжини k[6].

Планарний граф є зовніпланарним тоді й лише тоді, коли всі його двозв'язні компоненти зовніпланарні[5].

Всі зовніпланарні графи без петель можна розфарбувати всього трьома кольорами[7]. Цей факт проявляється помітно у спрощеному доведенні теореми про картинну галерею Хватала Фіском[8]. Розмальовку трьома кольорами можна знайти за лінійний час алгоритмом жадібного розмальовування, який видаляє будь-яку вершину зі степенем, що не перевищує двох, і розфарбовує решту графу рекурсивно, а потім повертає кожну з видалених вершин з кольором, відмінним від кольорів двох її сусідів.

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

Зовніпланарні графи мають виродження, яке не перевершує 2 — будь-який підграф зовніпланарного графу містить вершину зі степенем, що не перевершує 2[10].

Зовніпланарні графи мають деревну ширину, що не перевищує 2, звідки випливає, що багато задач оптимізації на графах, які NP-повні для графів загального вигляду, можна розв'язати за поліноміальний час за допомогою динамічного програмування, якщо входом служить зовніпланарний граф. Загальніше, k-зовніпланарний граф має деревну ширину O(k)[11].

Будь-який зовніпланарний граф можна подати у вигляді графу перетинів прямокутників із паралельними осям сторонами, так що зовніпланарні графи мають інтервальну розмірність[12][13] максимум два[14][15].