Зовніпланарний граф
В теорії графів зовніпланарний граф — це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані.
![](../I/Triangulation_3-coloring.svg.png.webp)
![](../I/Finite-3-regular-graph-4-vertices.png.webp)
Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження і деревну ширину не більше 2.
Зовніпланарні графи є підмножиною планарних графів, підграфами паралельно-послідовних графів і колових графів. Максимальний зовніпланарний граф — це граф, до якого можна додати ребро без втрати зовніпланарності. Вони також є хордальними і графами видимості.
Історія
Зовніпланарні графи вперше вивчали і назвали Шартран і Харарі[1], розглядаючи задачу визначення планарності графів, утворених за допомогою досконалих парувань, що зв'язують дві копії базового графу (наприклад, багато з узагальнених графів Петерсена утворено цим способом з двох копій графу-циклу). Вони показали, якщо базовий граф двозв'язний, граф, отриманий з нього описаним способом, планарний тоді й лише тоді, коли базовий граф зовніпланарний і парування утворює діедральні перестановки зовнішнього циклу.
Визначення та опис
Зовніпланарний граф є неорієнтованим графом, який можна намалювати на площині без перетинів таким чином, що всі вершини належатимуть зовнішній необмеженій грані малюнка. Тобто жодна з вершин не оточена повністю ребрами. Альтернативно граф G зовніпланарний, якщо граф, утворений з G додаванням нової вершини, з'єднаної ребрами з усіма іншими вершинами, планарний[2].
Максимальний зовніпланарний граф — це зовніпланарний граф, до якого можна додати будь-яке ребро, не порушивши властивість зовніпланарності. Будь-який максимальний зовніпланарний граф з n вершинами має в рівно 2n − 3 ребер і будь-яка обмежена грань максимального зовніпланарного графу є трикутником.
Заборонені графи
Зовніпланарні графи мають характеризацію забороненими графами, аналогічну теоремі Понтрягіна — Куратовського і теоремі Вагнера для планарних графів — граф зовніпланарний тоді й лише тоді, коли він не містить підрозбиття повного графу K4 або повного дводольного графу K2,3[3]. Альтернативно, граф зовніпланарний тоді й лише тоді, коли він не містить K4 або K2,3 як мінор, графу, отриманого видаленням і стягуванням ребер[4].
Граф без трикутників зовніпланарний тоді й лише тоді, коли він не містить підрозділів K2,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].
Пов'язані родини графів
![](../I/Cactus_graph.svg.png.webp)
Будь-який зовніпланарний граф є планарним. Будь-який зовніпланарний граф є підграфом паралельно-послідовного графу[16]. Однак не всі паралельно-послідовні графи зовніпланарні. Повний дводольний граф K2,3 є планарним і паралельно-послідовним, але не зовніпланарним. З іншого боку, повний граф K4 планарний, але ні паралельно-послідовний, ні зовніпланарний. Будь-який ліс і будь-який кактус зовніпланарні.
Слабко двоїстий планарний граф вкладеного зовніпланарного графу (граф, що має на вершині для кожної обмеженої грані вкладення і по ребру для суміжних обмежених граней) є лісом, а слабко двоїстий планарний граф графу Халіна є зовніпланарним графом. Планарний граф є зовніпланарним тоді й лише тоді, коли його слабко двоїстий граф є лісом, і граф є графом Халіна тоді й лише тоді, коли його слабко двоїстий граф є двозв'язним і зовніпланарним[17].
Існує поняття ступеня зовніпланарності. 1-зовніпланарне вкладення графу — це те ж саме, що зовніпланарне вкладення. Для k > 1 кажуть, що планарне вкладення є k-зовніпланарним, якщо видалення вершини з зовнішньої грані призводить до (k − 1)-зовніпланарного вкладення. Граф є k-зовніпланарним тоді й лише тоді, коли він має k-зовніпланарне вкладення[18][5].
Будь-який максимальний зовніпланарний граф є хордальним графом. Будь-який максимальний зовніпланарний граф є графом видимості простого багатокутника[19]. Максимальні зовніпланарні графи утворюються як графи тріангуляції багатокутників. Вони є також прикладами 2-дерев, паралельно-послідовних графів і хордальних графів.
Будь-який зовніпланарний граф є коловим графом, графом перетинів множини хорд кола[20][21].
Примітки
- Chartrand, Harary, 1967.
- Felsner, 2004.
- Chartrand, Harary, (1967); Sysło, (1979); Brandstädt, Le, Spinrad, (1999), Proposition 7.3.1, p. 117; Felsner, (2004).
- Diestel, 2000.
- Sysło, 1979.
- Li, Corneil, Mendelsohn, 2000, с. Proposition 2.5.
- Proskurowski, Sysło, 1986.
- Fisk, 1978.
- Fiorini, 1975.
- Lick, White, 1970.
- Baker, 1994.
- Визначення інтервальної розмірності графу можна знайти в книзі Робертса. Англійська назва терміна — boxicity.
- Робертс, 1986, с. 129.
- Scheinerman, 1984.
- Brandstädt, Le, Spinrad, 1999, с. 54.
- Brandstädt, Le, Spinrad, 1999, с. 174.
- Sysło, Proskurowski, 1983.
- Kane, Basu, 1976.
- El-Gindy, (1985); Lin, Skiena, (1995); Brandstädt, Le, Spinrad, (1999), Theorem 4.10.3, p. 65.
- Wessel, Pöschel, 1985.
- Unger, 1988.
Література
- Ф.С.Робертс. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. — Москва : «Наука», 1986. — С. 129. — (Теория и методы системного анализа)
- Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs // Journal of the ACM. — 1994. — Т. 41, вип. 1 (3 березня). — С. 153–180. — DOI: ..
- Luis Boza, Eugenio M. Fedriani, Juan Núñez. The problem of outer embeddings in pseudosurfaces // Ars Combinatoria. — 2004. — Т. 71 (3 березня). — С. 79–91..
- Luis Boza, Eugenio M. Fedriani, Juan Núñez. Obstruction sets for outer-bananas-surface graphs // Ars Combinatoria. — 2004. — Т. 73 (3 березня). — С. 65–77..
- Luis Boza, Eugenio M. Fedriani, Juan Núñez. Uncountable graphs with all their vertices in one face // Acta Mathematica Hungarica. — 2006. — Т. 112 (4) (3 березня). — С. 307–313. — DOI: ..
- Luis Boza, Eugenio M. Fedriani, Juan Núñez. Outer-embeddability in certain pseudosurfaces arising from three spheres // Discrete Mathematics. — 2010. — Т. 310 (3 березня). — С. 3359–3367. — DOI: ..
- Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — Society for Industrial and Applied Mathematics, 1999. — (SIAM Monographs on Discrete Mathematics and Applications) — ISBN 0-89871-432-X..
- Gary Chartrand, Frank Harary. Planar permutation graphs // Annales de l'Institut Henri Poincaré B. — 1967. — Т. 3, вип. 4 (3 березня). — С. 433–438..
- Reinhard Diestel. Graph Theory. — Springer-Verlag, 2000. — Т. 173. — С. 107. — (Graduate Texts in Mathematics) — ISBN 0-387-98976-5..
- H. El-Gindy. Hierarchical decomposition of polygons with applications. — McGill University, 1985. — (Ph.D. thesis). Як процитовано у Брандштедта, Лі і Спінрада (Brandstädt, Le та Spinrad, (1999)).
- Stefan Felsner. Geometric graphs and arrangements: some chapters from combinational geometry. — Vieweg+Teubner Verlag, 2004. — С. 6. — ISBN 978-3-528-06972-8..
- Stanley Fiorini. On the chromatic index of outerplanar graphs // Journal of Combinatorial Theory. — 1975. — Т. 18, вип. 1 (3 березня). — С. 35–38. — (Series B). — DOI: ..
- Steve Fisk. A short proof of Chvátal's watchman theorem // Journal of Combinatorial Theory. — 1978. — Т. 24 (3 березня). — С. 374. — (Series B). — DOI: ..
- Herbert J. Fleischner, D. P. Geller, Frank Harary. Outerplanar graphs and weak duals // Journal of the Indian Mathematical Society. — 1974. — Т. 38 (3 березня). — С. 215–219..
- Vinay G. Kane, Sanat K. Basu. On the depth of a planar graph // Discrete Mathematics. — 1976. — Т. 14, вип. 1 (3 березня). — С. 63–67. — DOI: ..
- Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyclicity and NP-completeness in planar graphs // Discrete Applied Mathematics. — 2000. — Т. 98, вип. 3 (3 березня). — С. 219–225. — DOI: ..
- Don R. Lick, Arthur T. White. k-degenerate graphs // Canadian Journal of Mathematics. — 1970. — Т. 22 (3 березня). — С. 1082–1096. — DOI: ..
- Yaw-Ling Lin, Steven S. Skiena. Complexity aspects of visibility graphs // International Journal of Computational Geometry and Applications. — 1995. — Т. 5, вип. 3 (3 березня). — С. 289–312. — DOI: ..
- Andrzej Proskurowski, Maciej M. Sysło. Efficient vertex-and edge-coloring of outerplanar graphs // SIAM Journal on Algebraic and Discrete Methods. — 1986. — Т. 7 (3 березня). — С. 131–136. — DOI: ..
- E. R. Scheinerman. Intersection Classes and Multiple Intersection Parameters of a Graph. — Princeton University, 1984. — (Ph.D. thesis). As cited by Brandstädt, Le та Spinrad, (1999).
- Maciej M. Sysło. Characterizations of outerplanar graphs // Discrete Mathematics. — 1979. — Т. 26, вип. 1 (3 березня). — С. 47–53. — DOI: ..
- Maciej M. Sysło, Andrzej Proskurowski. Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 248–256. — (Lecture Notes in Mathematics) — DOI:.
- Walter Unger. Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88). — Springer-Verlag, 1988. — Т. 294. — С. 61–72. — (Lecture Notes in Computer Science) — DOI:.
- W. Wessel, R. Pöschel. Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984 / Horst Sachs. — B.G. Teubner, 1985. — Т. 73. — С. 207–210. — (Teubner-Texte zur Mathematik). Як процитував Унгер (Unger, (1988)).
Посилання
- Outerplanar graphs, Information System on Graph Classes and Their Inclusions
- Weisstein, Eric W. Зовніпланарний граф(англ.) на сайті Wolfram MathWorld.