§ 39. Критерии планарности

Имеется несколько критериев планарности графа. Мы рассмотрим характеризации планарности графов, данные G. С. Понтрягиным, К. Куратовским, К. Вагнером и С. Наклейном. Следует заметить, что практическая про­верка условий, которыми ниже характеризуются планарные графы, не всегда является простой. Однако разработаны эффективные алгоритмы, позволяющие для любого заданного графа или найти его плоскую укладку, или установить, что граф непланарен. Один из таких алгорит­мов приведен в § 41.

Для того чтобы сформулировать широко известный критерий Понтрягина — Куратовского, введем понятие гомеоморфизма графов. Нам понадобится операция под­разбиения ребра е = аb графа. Она состоит в следующем:

из графа удаляется ребро е и добавляются два новых ребра е₁ = аv, e₂ = vb, где v — новая вершина.

Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ре­бер.

На рис. 39.1 изображены гомеоморфные графы.

Если граф планарный, то очевидно, что любой граф, гомеоморфный ему, также является планарным.

Исторически первым критерием планарности графов является следующий критерий, доказанный Л. С. Понтрягиным (1927 г.) и К. Куратовским (1930 г.) независимо друг от друга.

Теорема Понтрягина — Куратовского.

Граф планарен тогда и только тогда, когда он не содер­жит подграфов, гомеоморфных К₅ или К_3,3.

Тем самым можно утверждать, что многие графы непланарны и независимо от того, как они изображены на плоскости, некоторые их ребра обязательно пересекаются.

Необходимость условий теоремы уже доказана, по­скольку доказана непланарность графов К₅ и Кз,з (след­ствия 37.4 и 37.5). Для доказательства достаточности требуются новые понятия и теоремы. Попутно будет до­казано, что всякий планарный граф можно уложить на плоскости так, что каждое его ребро будет отрезком прямой.

Ранее было показано (см. теорему 37.8), что граф планарен тогда и только тогда, когда планарны его двусвязные компоненты. Оказывается, будет достаточно, ес­ли мы, касаясь вопросов, связанных с плоской укладкой 2-связного графа G, рассмотрим лишь 3-связные графы, полученные из G специальным образом.

Пусть x(G) = 2|G.|  4. Из определения двусвязности вытекает существование вершин а, b  VG, таких что граф Н = G — а — b не связен. Рассмотрим следующее преобразование А графа G. Пусть h₁, h₂, ..., H_r — связные компоненты графа Н. Для каждой такой компо­ненты Hi рассмотрим граф Gi, порожденный в G мно­жеством V U Hi , a Ub и дополненный ребром ab, если аb  EG. В результате преобразования А получаем семей­ство графов g₁, g₂, ..., G_r, причем |Gi|  3, х(Gi)  2 (i = l, r) (рис. 39.2).

Теорема 39.1. Пусть х(G) = 2, |G|  4. Граф G планарен тогда и только тогда, когда планарен каждый граф Gi, полученный в результате преобразования А.

Необходимость. Если G — планарный граф, то любой его подграф, в том числе G₀i = G(VGi), плана­рен. Если Gi содержит ребро аb, то Gi = G_0i. В противном

случае по лемме 34.7 в G существуетG₀i-цепь L, соединя­ющая вершины а и b. Подграф Gi₀ U L планарен, но он гомеоморфен графу G_i.

Достаточность. Пусть все графы g₁, G₂, ..., G_r планарны. Пусть Р₁, Р₂ , ..., Р_r— соответствующие им плоские укладки, у которых ребро ab лежит на внешней грани. Будем последовательно объединять графы Р₁, p₂, ..., Рr. Сначала построим такую укладку объедине­ния Р_1,2 графов Р₁ и P₂, в которых имеется общее ребро ab, что граф Р₂ лежит на внешней грани графа Р₁. Затем изобразим P_1,2 так, чтобы ребро ab оказалось на внешней грани, и используя прежний прием, построим объедине­ние P_1,.2,3 графов P_1,2и P_з (рис. 39.3) и т. д., пока не объ­единим все графы p₁, Р₂, ..., Р_г. Полученный в результат - не плоский граф p_{1,2 …….r} может отличаться от исходного графа G только ребром аb.

Следствие 39.2. Всякая плоская триангуляция, имеющая более трех вершин, 3-связна.

Доказательство проведем от противного. Предположим, что G — плоская триангуляция и x(G)=2. Пусть а

и b —- такие вершины, что граф G — а — b не связен. Cовершив преобразование А графа G, получим, согласно Теореме 39.1, планарные графы G₁, G₂, ..., G_r. Пусть p₁, p₂, ..., р_r — соответствующие им плоские укладки, в которых ребро аb лежит на внешней грани. Объединим их последовательно, как это делалось при доказательстве теоремы 39.1. При этом на последнемшаге,объединив

графыPP_1,2 ….,_r-1 и Рr, получаем граф P_1,2,..., r, внешняя грань которого со­держит (поскольку Pi  3) несмежные вершины с  VP_{l, 2.... r}__t и d  VPr, c,d  {a, b} (рис. 39.4), т. е. P_{1,2………r,} а, следовательно, и G не является плоской триангуляци­ей. Вернемся к графу G, для которо­го x(G)= 2, |G|>4. Если среди графов g₁, g₂, ..., Gr полученных помощью преобразования А, есть граф Gi, для которого (Gi)= 2, |Gi|  4,то к нему вновь можно применить преoбразование G и

т. д. до тех пор, пока это преобразование будет возможным. Поэтому справедливо

Утверждение 39.3. Пусть x(G)=2, |G|  4. Тогда в результате многократного применения преобразова ния А к графу G будет получено такое семейство графов G_i G₂, .. …G_R ,что для любого i = 1, R либо Gi=K₃, либо х (G_i)  3.

Поскольку Кз — планарный граф, то из теоремы 39.1 и утверждения 39.3 следует, что вопрос о планарности 2-связных графов свелся к вопросу о планарности 3-связных графов.

Прежде чем формулировать критерий планарности 3-связных графов, докажем лемму.

Лемма39.4.

Пусть x(G)= 2, |G|  4. Пусть, да­лее, g₁, g₂, ..., G_r — графы, полученные в результате пре­- образования А,и Аb — ребро этих графов, не принадлежащее графу G. Тогда для любого i = 1, r существует Сi -цепь графа G, соединяющая вершины а и b.

Поскольку x(G_k)  2 для любого k = 1, r, то по теореме 34.1 ребро аb принадлежит некоторому простому циклу графа G_k. При любом k  i часть этого цикла, не содержащая ребра ab, и служит искомойG_i,-цепью.

Плоский граф назовем выпуклым прямолинейным графом, если границей каждой его грани является выпуклый многоугольник. Напомним, что многоугольник называет­ся выпуклым, если он целиком расположен по одну сто­рону от любой прямой, на которой лежит сторона много­угольника, и никакие две его стороны не лежат на одной прямой.

Теорема 39.5. Если граф 3-связный, то он либо изоморфен выпуклому прямолинейному графу, либо со­держит подграф, гомеоморфный К₅ или К_3,3

Доказательство проведем индукцией по числу n вершин графа. Для n = 4 утверждение теоремы верно, так как граф К₄ изоморфен выпуклому прямолинейному графу (см. рис. 36.1, б), а других 3-связных четырех вершинных графов не существует.

Пусть G — 3-связный граф, |G|=n  5 и для всех графов с меньшим числом вершин теорема верна. Соглас­но следствию 34.9 в графе G есть такое ребро x = uv, что граф G_x, полученный из G в результате стягивания этого ребра, является 3-связным. Пусть G_x содержит под­граф Н, гомеоморфный K₅ (рис. 39.5, а). Покажем, что тогда граф G содержит подграф, гомеоморфный К₅ или Kз,з. Это очевидно в случае, когда Н не содержит верши­ны x₀, полученной в результате стягивания ребра х, или содержит ее в качестве вершины степени 2. Пусть теперь степень каждой из вершин а, b, с, d, х₀ в Н равна четы­рем. Тогда вершина х₀ соединена простыми непересекающимися цепями L₁, L₂, .L₃, L₄ с вершинами а, b, с, d cоответственно. В графе G этим цепям соответствуют пе­ресекающиеся простые цепи L₁, L₂, .L₃, L₄, соединяющие каждую из вершин а, b, с, d с одной из вершин и и v. Если одна из этих вершин, например и, принадлежит трем или четырем цепям, то в G существует подграф, гомеоморфный К₅ (рис. 39.5, б). А если каждая из

вершин u и v принадлежит ровно двум цепям, то в G существует подграф, гомеоморфный Кз,з (рис. 39.5, в, г).

Аналогично можно показать, что если G_x содержит подграф, гомеоморфный Кз.з, то и G содержит подграф, гомеоморфный Кз,з.

Пусть теперь в G_x нет подграфов, гомеоморфных графы К₅ или .Кз.з. По индуктивному предположению существует выпуклый прямолинейный граф G_0х, изоморфный графу G_x. Тогда G_0x—x₀ — 2-связный плоский граф, каждая грань которого, по теореме 37.7, ограничена простым циклом.

Как обычно, через N_G(v) обозначим окружение вершины v в графе G. Пусть С — простой цикл, ограничивающий грань графа G_0х — х₀, которая содержит N_G0x(х₀). Вершины из n_g(v)\u делят цикл С на простые цепи

L₁ =(a₁ ..., a₂), L₂ =(a₂, ..., а₃), ..., L_k = (a_k, ..., a₁ ). (1)

Далее рассмотрим отдельно два случая.

Случай 1. Все вершины из N_G(u)\v принадлежат одной из цепей (1). Тогда, удалив из G_0x все ребра вида (x₀, b), где b  a_i (i = 1, k), получим граф G', изоморф­ный графу G — u. Ребрами графа G' являются отрезки, и все его грани, кроме, возможно, грани, содержащей вершины из N_G(u), будут выпуклыми многоугольниками.

Пусть вершина х₀ принадлежит внутренней грани гра­фа G_0x.

Очевидно, что всякий выпуклый многоугольник обладает следующим свойством: для любой его вершины существует такая ее окрестность, в которой можно пере­мещать эту вершину (при неподвижных остальных), не нарушая выпуклости многоугольника. Поэтому в графе G_0х существует такая окрестность 0(х₀) точки х₀, что при перемещении х₀ в 0(х₀) будет сохраняться выпуклость всех многоугольников, находящихся внутри цикла С.

Будем считать, что вершины из N_G(u)\v находятся па цепи L_k и разбивают ее на части: (а₁, ..., b₁), (b₁, ... ..., b₂), ..., (b_l-i, ..., b_l), (b_l,, ..., a_k). Обозначим через Т точки плоскости, лежащие внутри кривой (цикла) (х₀, b₁, ..., b₂, ..., b_l х₀). Из определения выпуклого многоугольника следует, что, поместив вершину и в лю­бую точку области О (х₀) объединяя с Т и соединив и со всеми вер­шинами из N_G(u) (считая x₀ =v), получим выпуклый прямолинейный граф, изоморфный графу G (рис. 39.6). Подобным образом поступаем и тогда, когда вершина х₀ принадлежит внешней грани графа G_0x. (На рис. 39.7 а, б изображен случай, когда вершина и принадлежит внут­ренней грани графа G', а на рис. 39.7 в, г — внешней.) Случай 2. Не существует цепи (1), содержащей все вершины из множества N_G(u)\v. В этой ситуации

множество всех ребер, инцидентных и и v, нельзя изобра­зить без пересечений. В самом деле, если

М= \ (N_G(u)\v)  (N_G(v)\u)\  3,

т. е. число вершин цикла С, смежных и с u, и с v, не меньше трех, то в G существует подграф, гомеоморфный графу К₅ (рис. 39.8). Если же М  2, то в G есть подграф, гомеоморфный графу Кз,з. На рис.39.9—39.11 изображены случаи, ког­да М = 2, 1, 0 соответственно

Следствие 39.6 (теорема Понтрягина — Куратовского). Граф планарен тогда и

только тогда, когда он не содержит подграфов, гомеоморфных графам К₅ или Кз,з.

Осталось доказать достаточность условий теоремы.

Пусть в графеG нет подграфов, гомеоморфных К₅ или Кз,з- если G — 3-связный граф, то по теореме 39.5 он планарен.

Пусть x (G) =2, |G|  5. Далее доказательство проведём от противного. Предположим, что граф G не планарный. Тогда в результате многократного применения к не ­преобразования А (см. утверждение 39.3) получим семейство графов G₁, G₂,……., G_R, среди которых согласно теореме 39.1 имеется 3-связный граф gне являющийся тарным. В силу теоремы 39.5 в G_t есть подграф К, геоморфный К₅ или Кз,з. Если все ребра графа К  G, то К — подграф графа G, т. е. получено противоречие. Если же некоторое ребро аb  ЕК не входит

G, то по лемме 39.4 существует Gi-цепь графа G, соединяющая вершины а и b. Нетрудно показать, что Gi-цепи, cоответствующие различным таким ребрам, не имеющих вершин, кроме, возможно, концевых. Заменив каждое такое ребро соответствующей Gi-цепью, получим подграф графа G, гомеоморфный графу К. Вновь имеем проворечие.

В качестве иллюстрации рассмотрим граф Петерсена(содержит подграф, гомеоморфный графу Кз,з(рис. 39.12, {a₁,a₂,a₃} и {b₁,b₂,b₃} — доли). Следовательно, этот граф не является планарным.

Следствий 39.7 (К. Вагнер, 1936 г.). Для любого планарного графа существует плоская укладка, в ко­торой все ребра изображены в виде отрезков прямых линий.

Пусть G — связный планарный граф, имеющий не более четырех вершин. На основании следствия 38.2 граф G является остовным подграфом плоской триангурации Т, которая согласно следствию 39.2 есть 3-связный граф. Поэтому в силу теоремы 39.5 существует прямолинейный граф Т₀, изоморфный графу Т. Очевидно, что исходный граф G получается из Т путем удаления ранее избавленных к G ребер.

Помимо критерия Понтрягина — Куратовского есть и другие критерии планарности графа. Приведем некоторые из них без доказательств.

Теорема 39.8 (К. Вагнер, 1937 г.). Граф планарен тогда и только тогда, когда в нем нет подграфов, стяги­ваемых к графам К₅ или Кз,з.

Поскольку граф Петерсена очевидным образом стяги­вается к К₅ (для этого нужно стянуть пять ребер, соеди­няющих вершины внутреннего и внешнего циклов), то непланарность графа Петерсена с помощью критерия Вагнера доказывается совсем просто.

Отметим здесь, что стягивая любое ребро планарного графа, получаем вновь планарный граф.

Очевидно, что все ациклические графы планарны. Поэтому вполне естественна формулировка критерия пла­нарности, исключающая этот тривиальный случай. Та­ким критерием является следующая

Теорема 39.9 (С. Маклейн, 1937 г.). Граф планарен тогда и только тогда, когда в каждом его нетривиаль­ном блоке есть такой базис циклов С₁, С₂, ..., C_k и такой один дополнительный цикл Со, что любое ребро блока принадлежит ровно двум из этих k + 1 циклов.