Введение

Граф, который может быть встроен в плоскость.

Примеры графов: Планарный Непланарный Граф-бабочка Полный граф K5 Полный граф K4 Утилитарный граф K3,3

В теории графов планарный граф — это граф, который может быть встроен в плоскость, то есть его можно нарисовать на плоскости таким образом, чтобы его рёбра пересекались только в своих конечных точках. Иными словами, его можно нарисовать так, чтобы рёбра не пересекались. Такой рисунок называется планарным графом или планарной встройкой графа. Планарный граф можно определить как планарный граф с отображением из каждой вершины в точку на плоскости и из каждого ребра в планарную кривую на этой плоскости, таким образом, чтобы конечные точки каждой кривой соответствовали точкам, отображённым из её конечных вершин, и все кривые были непересекающимися, за исключением их конечных точек. Любой граф, который можно нарисовать на плоскости, можно также нарисовать на сфере, и наоборот, с помощью стереографической проекции. Планарные графы могут быть закодированы комбинаторными картами или системами поворотов. Класс эквивалентности топологически эквивалентных чертежей на сфере, обычно с дополнительными предположениями, такими как отсутствие мостов, называется планарной картой. Хотя планарный граф имеет внешнюю или неограниченную грань, ни одна из граней планарной карты не имеет особого статуса. Планарные графы обобщаются на графы, которые можно нарисовать на поверхности заданного рода. В этой терминологии планарные графы имеют род 0, поскольку плоскость (и сфера) являются поверхностями рода 0. См. «встраивание графа» для получения информации о других связанных темах.

Средняя степень

Связные планарные графы с более чем одним ребром удовлетворяют неравенству 2e ≥ 3f, поскольку каждая грань имеет не менее трех инциденций ребер, а каждое ребро вносит ровно две инциденции. Из алгебраических преобразований этого неравенства совместно с формулой Эйлера v – e + f = 2 следует, что для конечных планарных графов средняя степень вершины строго меньше 6. Графы с более высокой средней степенью не могут быть планарными.

Графики монет

Мы говорим, что два круга, нарисованные на плоскости, касаются (или осциллируют), когда они пересекаются ровно в одной точке. "Граф монет" – это граф, образованный набором кругов, ни два из которых не имеют пересекающихся внутренних областей, путем создания вершины для каждого круга и ребра для каждой пары касающихся кругов. Теорема о плотной упаковке кругов, впервые доказанная Полом Коэбом в 1936 году, утверждает, что граф является планарным тогда и только тогда, когда он является графом монет. Этот результат предоставляет простое доказательство теоремы Фари, согласно которой любой простой планарный граф можно вложить в плоскость таким образом, чтобы его ребра были отрезками прямых, не пересекающими друг друга. Если поместить каждую вершину графа в центр соответствующего круга в представлении графа монет, то отрезки, соединяющие центры касающихся кругов, не будут пересекать другие ребра.

Двойной график

При заданном вложении G связного (не обязательно простого) графа в плоскость без пересечения ребер, мы строим двойственный граф G* следующим образом: мы выбираем одну вершину в каждой области (грани) G, включая внешнюю область, и для каждого ребра e в G вводим новое ребро в G*, соединяющее две вершины в G*, соответствующие двум областям в G, которые имеют общее ребро e. Кроме того, это ребро проводится так, чтобы оно пересекало e ровно один раз и не пересекало никакие другие ребра G или G*. Тогда G* снова является вложением (не обязательно простого) планарного графа; он имеет столько же ребер, сколько и G, столько же вершин, сколько областей у G, и столько же областей, сколько вершин у G. Термин "двойственный" оправдан тем, что G** = G; здесь равенство означает эквивалентность вложений на сфере. Если G — планарный граф, соответствующий выпуклому многограннику, то G* — планарный граф, соответствующий двойственному многограннику. Двойственные графы полезны, поскольку многие свойства двойственного графа связаны простыми способами со свойствами исходного графа, что позволяет доказывать теоремы о графах, исследуя их двойственные графы. Хотя двойственный граф, построенный для конкретного вложения, уникален с точностью до изоморфизма, графы могут иметь различные (т.е. неизоморфные) двойственные графы, полученные из различных (т.е. негомеоморфных) вложений.

Максимальные плоскостные графики

Простой граф называется максимально планарным, если он планарный, но добавление любого ребра (на заданном множестве вершин) разрушит это свойство. Все грани (включая внешнюю) тогда ограничены тремя ребрами, что объясняет альтернативный термин планарная триангуляция. Альтернативные названия "треугольный граф" или "триангулированный граф" также использовались, но они неоднозначны, поскольку чаще всего относятся к линейному графу полного графа и к хордальным графам соответственно. Каждый максимально планарный граф является как минимум 3-связным. Если максимально планарный граф имеет v вершин при v > 2, то он имеет ровно 3v – 6 ребер и 2v – 4 граней. Аполлоновы сети — это максимально планарные графы, формируемые путем многократного разделения треугольных граней на тройки меньших треугольников. Эквивалентно, они являются планарными 3-деревьями. Странгулированные графы — это графы, в которых каждый периферический цикл является треугольником. В максимально планарном графе (или более общо в полиэдральном графе) периферические циклы являются гранями, поэтому максимально планарные графы являются странгулированными. Странгулированные графы включают также хордальные графы и представляют собой именно те графы, которые могут быть сформированы путем сумм клик (без удаления ребер) полных графов и максимально планарных графов.

Внешнеплановые графики

Внешнепланарные графы – это графы, имеющие вложение в плоскость, такое что все вершины принадлежат неограниченной области этого вложения. Любой внешнепланарный граф является планарным, но обратное неверно: K4 является планарным, но не внешнепланарным. Существует теорема, аналогичная теореме Куратовского, утверждающая, что конечный граф является внешнепланарным тогда и только тогда, когда он не содержит подграф, являющийся делением K4 или K2,3. Указанное утверждение является прямым следствием того факта, что граф G является внешнепланарным, если граф, полученный из G добавлением новой вершины и соединением её рёбрами со всеми остальными вершинами, является планарным графом. 1-внешнепланарное вложение графа эквивалентно внешнепланарному вложению. Для k > 1 планарное вложение называется k-внешнепланарным, если удаление вершин, лежащих на внешней области, приводит к (k – 1)-внешнепланарному вложению. Граф называется k-внешнепланарным, если он имеет k-внешнепланарное вложение.

Графики Халина

Граф Халина — это граф, образованный из ненаправленного плоского дерева (без вершин степени два) путём соединения его листьев в цикл в порядке, заданном плоской структурой дерева. Эквивалентно, это полиэдральный граф, в котором одна грань смежна со всеми остальными. Любой граф Халина планарный. Как и у внешнепланарных графов, у графов Халина низкая ширина дерева, что облегчает решение многих алгоритмических задач по сравнению с произвольными планарными графами.

Графики с плановой линией вверх

Верхний планарный граф — это ориентированный ациклический граф, который можно изобразить на плоскости так, чтобы его рёбра были непересекающимися кривыми, последовательно ориентированными вверх. Не каждый планарный ориентированный ациклический граф является верхним планарным, и проверка, является ли данный граф верхним планарным, является NP-полной задачей.

Выпуклые плоскостные графики

Плоский граф называется выпуклым, если все его грани (включая внешнюю) являются выпуклыми многоугольниками. Не все плоские графы допускают выпуклую вложение (например, полный двудольный граф). Достаточным условием для того, чтобы граф можно было нарисовать выпукло, является то, что он является подграфом 3-связного планарного графа. Теорема Тутте о пружинах даже утверждает, что для простых 3-связных планарных графов положение внутренних вершин можно выбрать как среднее арифметическое координат их соседей.

Плановые графики, представляемые словами

Словопредставимые плоские графы включают в себя плоские графы без треугольников и, в более общем случае, 3-раскрашиваемые плоские графы, а также некоторые разбиения граней треугольных решёточных графов и некоторые триангуляции цилиндровых графов, покрытых решёткой.

Перечисление плоских графиков

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

Обобщения

Апекс-граф — это граф, который можно сделать планарным путём удаления одной вершины, а k-апекс-граф — это граф, который можно сделать планарным путём удаления не более k вершин. 1-планарный граф — это граф, который можно нарисовать на плоскости не более чем с одним простым пересечением на ребро, а k-планарный граф — это граф, который можно нарисовать не более чем с k простыми пересечениями на ребро. Картографический граф — это граф, образованный из множества конечного числа просто связанных внутренних непересекающихся областей на плоскости путём соединения двух областей, когда они имеют хотя бы одну общую граничную точку. Когда в одной точке сходятся не более трёх областей, результат является планарным графом, но когда сходятся четыре или более областей, результат может быть непланарным (например, если представить себе круг, разделённый на сектора, где сектора являются областями, то соответствующий картографический граф является полным графом, поскольку все сектора имеют общую граничную точку — центральную точку). Тороидальный граф — это граф, который можно вложить без пересечений на тор. В более общем смысле, род графа — это минимальный род двумерной поверхности, в которую можно вложить граф; планарные графы имеют род ноль, а непланарные тороидальные графы — род один. Любой граф можно вложить без пересечений в некоторую (ориентируемую, связную) замкнутую двумерную поверхность (сферу с ручками), и таким образом род графа определён однозначно. Очевидно, что если граф можно вложить без пересечений в (ориентируемую, связную, замкнутую) поверхность с родом g, то он может быть вложен без пересечений во все (ориентируемые, связные, замкнутые) поверхности с родом, большим или равным g. В теории графов существуют и другие понятия, называемые «X-род», где «X» — некоторый уточняющий признак; в общем случае они отличаются от вышеопределённого понятия «род» без каких-либо уточнений. В частности, неориентируемый род графа (использующий неориентируемые поверхности в своём определении) отличается для общего графа от рода этого графа (использующего ориентируемые поверхности в своём определении). Любой граф можно вложить в трёхмерное пространство без пересечений. Фактически, любой граф можно нарисовать без пересечений в двух плоскостях, где две плоскости расположены друг над другом, а рёбрам разрешено «переходить» и «спускаться» с одной плоскости на другую в любом месте (не только в вершинах графа), чтобы рёбра могли избегать пересечений с другими рёбрами. Это можно интерпретировать как возможность создания любой сети электрических проводников с двусторонней печатной платой, где электрическое соединение между сторонами платы может быть обеспечено (как это возможно с типичными реальными печатными платами, где электрические соединения на верхней стороне платы достигаются с помощью кусков проводов, а на нижней стороне — дорожками из меди, нанесёнными на саму плату, и электрическое соединение между сторонами платы достигается путём сверления отверстий, пропускания проводов через отверстия и пайки их к дорожкам); также это можно интерпретировать как утверждение, что для построения любой дорожной сети нужны только мосты или только тоннели, а не оба варианта (2 уровней достаточно, 3 не нужны). Кроме того, в трёх измерениях вопрос о рисовании графа без пересечений тривиален. Однако трёхмерным аналогом планарных графов служат графы, допускающие безсвязное вложение, то есть графы, которые можно вложить в трёхмерное пространство таким образом, чтобы никакие два цикла не были топологически связаны друг с другом. По аналогии с характеристикой планарных графов Куратовским и Вагнером как графов, не содержащих K5 или K3,3 в качестве минора, графы, допускающие безсвязное вложение, можно охарактеризовать как графы, не содержащие в качестве минора ни одного из семи графов семейства Петерсена. По аналогии с характеристикой внешнепланарных и планарных графов как графов с инвариантом графа Колина де Вердьера, не превышающим двух или трёх, графы, допускающие безсвязное вложение, — это графы, имеющие инвариант Колина де Вердьера, не превышающий четырёх.