PROFILPELAJAR.COM

Полный граф K₄ является наименьшим планарным графом, не являющимся внешнепланарным.

Внешнепланарный граф — в теории графов такой граф, который допускает планарную диаграмму, в которой все вершины принадлежат внешней грани.

Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K₄и K_2,3, или их инвариантами Колен де Вердьера. Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырожденность и древесную ширину не больше 2.

Внешнепланарные графы являются подмножеством планарных графов, подграфами параллельно-последовательных графов и круговых графов. Максимальный внешнепланарный граф — это граф, к которому нельзя добавить ребро без потери внешнепланарности. Они также являются хордальными и графами видимости.

История

Внешнепланарные графы впервые изучали и назвали Шартран и Харари^[1] при рассмотрении задачи определения планарности графов, образованных при помощи совершенных паросочетаний, связывающих две копии базового графа (например, многие из обобщённых графов Петерсена образованы этим способом из двух копий графа-цикла). Как они показали, если базовый граф двусвязен, граф, полученный из него описанным способом, планарен тогда и только тогда, когда базовый граф внешнепланарен и паросочетание образует диэдральные перестановки внешнего цикла.

Определение и описание

Внешнепланарный граф является неориентированным графом, который можно нарисовать на плоскости без пересечений таким образом, что все вершины принадлежат внешней неограниченной грани рисунка. То есть никакая из вершин не окружена полностью рёбрами. Альтернативно граф G внешнепланарен, если граф, образованный из G добавлением новой вершины, соединённой рёбрами со всеми остальными вершинами, планарен^[2].

Максимальный внешнепланарный граф — это внешнепланарный граф, к которому нельзя добавить какое-либо ребро, не нарушив свойство внешнепланарности. Любой максимальный внешнепланарный граф с n вершинами имеет в точности 2n − 3 рёбер и любая ограниченная грань максимального внешнепланарного графа является треугольником.

Запрещённые графы

Внешнепланарные графы имеют характеризацию запрещёнными графами, аналогичную теореме Понтрягина — Куратовского и теореме Вагнера для планарных графов — граф внешнепланарен тогда и только тогда, когда он не содержит подразбиения полного графа 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].

Связанные семейства графов

Любой внешнепланарный граф является планарным. Любой внешнепланарный граф является подграфом параллельно-последовательного графа^[16]. Однако не все параллельно-последовательные графы внешнепланарны. Полный двудольный граф K_2,3 является планарным и параллельно-последовательным, но не внешнепланарным. С другой стороны, полный граф K₄ планарен, но ни параллельно-последователен, ни внешнепланарен. Любой лес и любой кактус внешнепланарны^[17].

Cлабо двойственный планарный граф вложенного внешнепланарного графа (граф, имеющий по вершине для каждой ограниченной грани вложения и по ребру для смежных ограниченных граней) является лесом, а слабо двойственный планарный граф графа Халина является внешнепланарным графом. Планарный граф является внешнепланарным тогда и только тогда, когда его слабо двойственный является лесом, и граф является графом Халина тогда и только тогда, когда его слабо двойственный является двусвязным и внешнепланарным^[18].

Существует понятие степени внешнепланарности. 1-внешнепланарное вложение графа — это то же самое, что внешнепланарное вложение. Для k > 1 говорят, что планарное вложение является k-внешнепланарным, если удаление вершины из внешней грани приводит к (k − 1)-внешнепланарному вложению. Граф является k-внешнепланарным тогда и только тогда, когда он имеет k-внешнепланарное вложение^[19]^[5].

Любой максимальный внешнепланарный граф является хордальным графом. Любой максимальный внешнепланарный граф является графом видимости простого многоугольника^[20]. Максимальные внешнепланарные графы образуются как графы триангуляции многоугольников. Они являются также примерами 2-деревьев, параллельно-последовательноых графов и хордальных графов.

Любой внешнепланарный граф является круговым графом, графом пересечений множества хорд окружности^[21]^[22].

Примечания

↑ ¹ ² 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.
↑ Brandstädt, Le, Spinrad, 1999, с. 169.
↑ 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. — С. 153–180. — doi:10.1145/174644.174650..
Luis Boza, Eugenio M. Fedriani, Juan Núñez. The problem of outer embeddings in pseudosurfaces // Ars Combinatoria^[англ.]. — 2004. — Т. 71. — С. 79–91..
Luis Boza, Eugenio M. Fedriani, Juan Núñez. Obstruction sets for outer-bananas-surface graphs // Ars Combinatoria^[англ.]. — 2004. — Т. 73. — С. 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). — С. 307–313. — doi:10.1007/s10474-006-0082-0..
Luis Boza, Eugenio M. Fedriani, Juan Núñez. Outer-embeddability in certain pseudosurfaces arising from three spheres // Discrete Mathematics. — 2010. — Т. 310. — С. 3359–3367. — doi:10.1016/j.disc.2010.07.027..
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. — С. 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. — С. 35–38. — doi:10.1016/0095-8956(75)90060-X..
Steve Fisk. A short proof of Chvátal's watchman theorem // Journal of Combinatorial Theory. — 1978. — Т. 24. — С. 374. — doi:10.1016/0095-8956(78)90059-X..
Herbert J. Fleischner, D. P. Geller, Frank Harary. Outerplanar graphs and weak duals // Journal of the Indian Mathematical Society. — 1974. — Т. 38. — С. 215–219..
Vinay G. Kane, Sanat K. Basu. On the depth of a planar graph // Discrete Mathematics. — 1976. — Т. 14, вып. 1. — С. 63–67. — doi:10.1016/0012-365X(76)90006-6..
Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyclicity and NP-completeness in planar graphs // Discrete Applied Mathematics. — 2000. — Т. 98, вып. 3. — С. 219–225. — doi:10.1016/S0166-218X(99)00163-8..
Don R. Lick, Arthur T. White. k-degenerate graphs // Canadian Journal of Mathematics. — 1970. — Т. 22. — С. 1082–1096. — doi:10.4153/CJM-1970-125-1..
Yaw-Ling Lin, Steven S. Skiena. Complexity aspects of visibility graphs // International Journal of Computational Geometry and Applications. — 1995. — Т. 5, вып. 3. — С. 289–312. — doi:10.1142/S0218195995000179..
Andrzej Proskurowski, Maciej M. Sysło. Efficient vertex-and edge-coloring of outerplanar graphs // SIAM Journal on Algebraic and Discrete Methods. — 1986. — Т. 7. — С. 131–136. — doi:10.1137/0607016..
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. — С. 47–53. — doi:10.1016/0012-365X(79)90060-8..
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:10.1007/BFb0071635..
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:10.1007/BFb0035832..
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)).