Планарный граф

В теории графов планарный граф — это граф , который может быть вложен в плоскость , т. е. его можно нарисовать на плоскости таким образом, что его ребра пересекаются только в своих конечных точках. Другими словами, его можно нарисовать таким образом, что никакие ребра не пересекаются. ^[1]^[2] Такой рисунок называется планарным графом или планарным вложением графа. Плоский граф можно определить как планарный граф с отображением из каждого узла в точку на плоскости и из каждого ребра в плоскую кривую на этой плоскости, таким образом, что крайние точки каждой кривой являются точками, отображенными из ее конечных узлов, и все кривые не пересекаются, за исключением своих крайних точек.

Каждый график, который можно изобразить на плоскости, можно изобразить и на сфере , и наоборот, с помощью стереографической проекции .

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

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

Планарные графы обобщаются до графов, которые можно нарисовать на поверхности заданного рода . В этой терминологии планарные графы имеют род 0, поскольку плоскость (и сфера) являются поверхностями рода 0. См. « вложение графов » для других связанных тем.

Критерии плоскостности

Теоремы Куратовского и Вагнера

Польский математик Казимеж Куратовский дал характеристику планарных графов в терминах запрещённых графов , теперь известную как теорема Куратовского :

Конечный граф является планарным

тогда

и только тогда, когда он не содержит подграфа

,

являющегося подразделением полного графа

K5

или полного двудольного графа

K3,3

( графа полезности ).

Подразделение графа происходит в результате вставки вершин в ребра (например, изменение ребра • —— • на • — • — • ) ноль или более раз.

Вместо рассмотрения подразделений теорема Вагнера имеет дело с минорами :

Конечный граф является планарным тогда и только тогда, когда

он

не имеет

K5

или

K3,3

в качестве минора .

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

Анимация, показывающая, что граф Петерсена содержит минор, изоморфный графу

K 3,3

, и поэтому является непланарным

Клаус Вагнер задался более общим вопросом: определяется ли любой замкнутый по минорам класс графов конечным набором « запрещенных миноров ». Теперь это теорема Робертсона–Сеймура , доказанная в длинной серии статей. На языке этой теоремы $K 5$ и $K 3,3$ являются запрещенными минорами для класса конечных планарных графов.

Другие критерии

На практике трудно использовать критерий Куратовского, чтобы быстро решить, является ли заданный граф планарным. Однако существуют быстрые алгоритмы для этой задачи: для графа с $n$ вершинами можно за время $O (n)$ (линейное время) определить, может ли граф быть планарным или нет (см. тестирование планарности ).

Для простого связного планарного графа с $v$ вершинами, $e$ ребрами и $f$ гранями выполняются следующие простые условия при $v \geq 3$ :

Теорема 1. $e \leq 3 v - 6$ ;
Теорема 2. Если циклов длины 3 нет, то $e \leq 2 v - 4$ .
Теорема 3. $f \leq 2 v - 4$ .

В этом смысле планарные графы являются разреженными графами , поскольку они имеют только $O (v)$ ребер, асимптотически меньше максимального $O (v 2)$ . Граф $K 3,3$ , например, имеет 6 вершин, 9 ребер и не имеет циклов длины 3. Следовательно, по теореме 2 он не может быть планарным. Эти теоремы предоставляют необходимые условия планарности, которые не являются достаточными условиями, и поэтому могут использоваться только для доказательства того, что граф не является планарным, а не того, что он является планарным. Если обе теоремы 1 и 2 не выполняются, можно использовать другие методы.

Критерий планарности Уитни дает характеристику, основанную на существовании алгебраического дуала;
Критерий планарности Маклейна дает алгебраическую характеристику конечных планарных графов через их пространства циклов ;
Критерий планарности Фрейссейкса –Розенштиля дает характеристику, основанную на существовании двуразделения ребер кодерева дерева поиска в глубину. Он является центральным для алгоритма проверки планарности слева направо ;
Теорема Шнайдера дает характеристику планарности в терминах размерности частичного порядка ;
Критерий планарности Колена де Вердьера дает характеристику, основанную на максимальной кратности второго собственного значения некоторых операторов Шредингера, определяемых графиком.
Теорема Ханани–Тутта утверждает, что граф является планарным тогда и только тогда, когда он имеет рисунок, в котором каждая независимая пара ребер пересекается четное число раз; ее можно использовать для характеристики планарных графов с помощью системы уравнений по модулю 2.

Характеристики

Формула Эйлера

Формула Эйлера гласит, что если конечный, связный , плоский граф изображен на плоскости без пересечений ребер, и $v$ — число вершин, $e$ — число ребер, а $f$ — число граней (областей, ограниченных ребрами, включая внешнюю, бесконечно большую область), то

v-e+f=2.

В качестве иллюстрации, в графе-бабочке, приведенном выше, $v = 5$ , $e = 6$ и $f = 3.$ В общем случае, если свойство выполняется для всех планарных графов с $f$ гранями, любое изменение графа, которое создает дополнительную грань, сохраняя при этом планарность графа, сохранит $v - e + f$ инвариантным. Поскольку свойство выполняется для всех графов с $f = 2$ , по математической индукции оно выполняется для всех случаев. Формулу Эйлера можно также доказать следующим образом: если граф не является деревом , то удалить ребро, которое завершает цикл . Это понижает как $e$ , так и $f$ на единицу, оставляя $v - e + f$ постоянным. Повторяйте, пока оставшийся граф не станет деревом; деревья имеют $v = e + 1$ и $f = 1$ , что дает $v - e + f = 2$ , т. е. характеристика Эйлера равна 2.

В конечном, связном , простом , плоском графе любая грань (за исключением, возможно, внешней) ограничена по крайней мере тремя ребрами, и каждое ребро касается не более двух граней; используя формулу Эйлера, можно показать, что эти графы являются разреженными в том смысле, что если $v \geq 3$ :

e\leq 3v-6.

Формула Эйлера также верна для выпуклых многогранников . Это не совпадение: любой выпуклый многогранник можно превратить в связный, простой, плоский граф, используя диаграмму Шлегеля многогранника, перспективную проекцию многогранника на плоскость с центром перспективы, выбранным вблизи центра одной из граней многогранника. Не каждый плоский граф соответствует выпуклому многограннику таким образом: деревья, например, не соответствуют. Теорема Штейница гласит, что многогранные графы, образованные из выпуклых многогранников, являются в точности конечными 3-связными простыми плоскими графами. В более общем смысле формула Эйлера применима к любому многограннику, грани которого являются простыми многоугольниками , которые образуют поверхность, топологически эквивалентную сфере, независимо от ее выпуклости.

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

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

Монетные графики

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

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

Плотность планарного графа

Коэффициент сетчатости или плотность $D$ планарного графа, или сети, представляет собой отношение числа $f - 1$ ограниченных граней (того же, что и ранг контура графа по критерию планарности Маклейна ) к его максимально возможным значениям $2 v - 5$ для графа с $v$ вершинами:

D={\frac {f-1}{2v-5}}

Плотность подчиняется условию $0 \leq D \leq 1$ , где $D = 0$ для полностью разреженного планарного графа (дерева) и $D = 1$ для полностью плотного (максимального) планарного графа. ^[3]

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

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

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

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

Семейства планарных графов

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

Простой граф называется максимальным планарным, если он планарный, но добавление любого ребра (в заданном наборе вершин) разрушит это свойство. Все грани (включая внешнюю) тогда ограничены тремя ребрами, что объясняет альтернативный термин « плоская триангуляция » . Альтернативные названия «треугольный граф» ^[4] или «триангулированный граф» ^[5] также использовались, но они неоднозначны, поскольку они чаще относятся к линейному графу полного графа и к хордовым графам соответственно. Каждый максимальный планарный граф является по крайней мере 3-связным.

Если максимальный планарный граф имеет $v$ вершин с $v > 2$ , то он имеет ровно $3 v - 6$ ребер и $2 v - 4$ граней.

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

Ущемленные графы — это графы, в которых каждый периферийный цикл является треугольником. В максимальном планарном графе (или, в более общем смысле, полиэдральном графе) периферийные циклы являются гранями, поэтому максимальные планарные графы ущемлены. Ущемленные графы включают также хордовые графы и являются именно теми графами, которые могут быть образованы кликовыми суммами (без удаления ребер) полных графов и максимальных планарных графов. ^[6]

Внешнепланарные графы

Внешнепланарные графы — это графы с вложением в плоскость, таким, что все вершины принадлежат неограниченной грани вложения. Каждый внешнепланарный граф является планарным, но обратное неверно: $K 4$ является планарным, но не внешнепланарным. Теорема, аналогичная теореме Куратовского, утверждает, что конечный граф является внешнепланарным тогда и только тогда, когда он не содержит подразделения $K 4$ или $K 2,3$ . Вышеизложенное является прямым следствием того факта, что граф $G$ является внешнепланарным, если граф, образованный из $G$ путем добавления новой вершины, с ребрами, соединяющими ее со всеми остальными вершинами, является планарным графом. ^[7]

1-внешнепланарное вложение графа совпадает с внешнепланарным вложением. Для $k > 1$ планарное вложение является $k$ -внешнепланарным, если удаление вершин на внешней грани приводит к $(k - 1)$ -внешнепланарному вложению. Граф является $k$ -внешнепланарным, если он имеет $k$ -внешнепланарное вложение.

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

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

Восходящие планарные графы

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

Выпуклые планарные графы

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

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

Представляемые в виде слов планарные графы включают в себя планарные графы без треугольников и, в более общем смысле, планарные графы, раскрашиваемые в 3 цвета, ^[9], а также некоторые подразделения граней графов треугольной сетки, ^[10] и некоторые триангуляции графов цилиндров, покрытых сеткой. ^[11]

Теоремы

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

Асимптотика для числа (помеченных) планарных графов на вершинах равна , где и . ^[12] $n$ $g\cdot n^{-7/2}\cdot \gamma ^{n}\cdot n!$ $\гамма \приблизительно 27,22687$ $g\приблизительно 0,43\times 10^{-5}$

Почти все планарные графы имеют экспоненциальное число автоморфизмов. ^[13]

Число немаркированных (неизоморфных) планарных графов на вершинах находится между и . ^[14] $n$ $27.2^{н}$ $30.06^{н}$

Другие результаты

Теорема о четырех красках утверждает, что каждый планарный граф является четырехцветным ( т.е. четырехдольным).

Теорема Фари утверждает, что каждый простой планарный граф допускает представление в виде планарного прямолинейного графа . Универсальное множество точек — это множество точек, такое что каждый планарный граф с n вершинами имеет такое вложение со всеми вершинами в множестве точек; существуют универсальные множества точек квадратичного размера, образованные взятием прямоугольного подмножества целочисленной решетки . Каждый простой внешнепланарный граф допускает вложение в плоскость, такое что все вершины лежат на фиксированной окружности, а все ребра являются отрезками прямых, которые лежат внутри круга и не пересекаются, поэтому правильные многоугольники с n вершинами универсальны для внешнепланарных графов.

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

Теорема о планарном разделителе утверждает, что любой планарный граф с n вершинами может быть разбит на два подграфа размером не более 2 n /3 путем удаления O( √ n ) вершин. Как следствие, планарные графы также имеют ширину дерева и ширину ветвей O( √ n ).

Теорема о структуре планарного произведения утверждает, что каждый планарный граф является подграфом сильного графового произведения графа древовидной ширины не более 8 и пути. ^[15] Этот результат был использован для того, чтобы показать, что планарные графы имеют ограниченное число очередей , ограниченное неповторяющееся хроматическое число и универсальные графы почти линейного размера. Он также имеет приложения к ранжированию вершин ^[16] и p -центрированной раскраске ^[17] планарных графов.

Для двух планарных графов с v вершинами можно за время O( v ) определить, являются ли они изоморфными или нет (см. также проблему изоморфизма графов ). ^[18]

Любой планарный граф на n узлах имеет не более 8(n-2) максимальных клик, ^[19] что означает, что класс планарных графов является классом с небольшим количеством клик.

Обобщения

Граф вершин — это граф, который можно сделать плоским, удалив одну вершину, а граф вершин k — это граф, который можно сделать плоским, удалив не более k вершин.

1 -Планарный граф — это граф, который можно нарисовать на плоскости с максимум одним простым пересечением на ребро, а k -Планарный граф — это граф, который можно нарисовать с максимум k простыми пересечениями на ребро.

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

Тороидальный граф — это граф, который может быть вложен без пересечений в тор . В более общем смысле, род графа — это минимальный род двумерной поверхности, в которую граф может быть вложен; планарные графы имеют род ноль, а непланарные тороидальные графы имеют род один. Каждый граф может быть вложен без пересечений в некоторую (ориентируемую, связную) замкнутую двумерную поверхность (сферу с ручками), и, таким образом, род графа хорошо определен. Очевидно, что если граф может быть вложен без пересечений в (ориентируемую, связную, замкнутую) поверхность с родом g, он может быть вложен без пересечений во все (ориентируемые, связные, замкнутые) поверхности с большим или равным родом. В теории графов есть также другие концепции, которые называются «X-род» с «X» некоторым квалификатором; в целом они отличаются от вышеопределенной концепции «рода» без какого-либо квалификатора. В частности, неориентируемый род графа (использующий в своем определении неориентируемые поверхности) отличается для общего графа от рода этого графа (использующего в своем определении ориентируемые поверхности).

Любой граф может быть встроен в трехмерное пространство без пересечений. Фактически, любой граф может быть нарисован без пересечений в двухплоскостной конфигурации, где две плоскости размещены друг над другом, а ребра могут «подпрыгивать» и «опускаться» с одной плоскости на другую в любом месте (не только в вершинах графа), так что ребра могут избегать пересечений с другими ребрами. Это можно интерпретировать как то, что можно создать любую электрическую проводниковую сеть с помощью двухсторонней печатной платы , где электрическое соединение между сторонами платы может быть выполнено (как это возможно с типичными реальными печатными платами, с электрическими соединениями на верхней стороне платы, достигнутыми с помощью кусков провода, а на нижней стороне — с помощью дорожек из меди, построенных на самой плате, и электрическим соединением между сторонами платы, достигнутым путем сверления отверстий, пропускания проводов через отверстия и припаивания их к дорожкам); можно также интерпретировать это как то, что для построения любой дорожной сети нужны только мосты или только туннели, а не оба (достаточно двух уровней, три не нужны). Кроме того, в трех измерениях вопрос о рисовании графа без пересечений тривиален. Однако трехмерный аналог планарных графов обеспечивается беззвеньевыми вкладываемыми графами , графами, которые могут быть вложены в трехмерное пространство таким образом, что никакие два цикла не будут топологически связаны друг с другом. По аналогии с характеристиками планарных графов Куратовским и Вагнером как графов, которые не содержат K ₅ или K _3,3 в качестве минора, беззвеньевые вкладываемые графы могут быть охарактеризованы как графы, которые не содержат в качестве минора ни один из семи графов семейства Петерсена . По аналогии с характеристиками внешнепланарных и планарных графов как графов с инвариантом графа Колена де Вердьера не более двух или трех, беззвеньевыми вкладываемыми графами являются графы, которые имеют инвариант Колена де Вердьера не более четырех.

Смотрите также

Комбинаторная карта — комбинаторный объект, который может кодировать плоские графы.
Планаризация , планарный граф, образованный из рисунка с пересечениями путем замены каждой точки пересечения новой вершиной.
Толщина (теория графов) , наименьшее число планарных графов, на которые можно разбить ребра данного графа.
Planarity — компьютерная игра-головоломка, цель которой — встроить планарный граф в плоскость.
Ростки (игра) — игра с карандашом и бумагой, в которой в качестве части игрового процесса строится планарный граф, подчиняющийся определенным ограничениям.
Задача о трех утилитах , популярная головоломка

Примечания

^ Трудо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, дополненное переиздание. ред.). Нью-Йорк: Dover Pub. стр. 64. ISBN 978-0-486-67870-2. Получено 8 августа 2012 г. Таким образом, планарный граф, нарисованный на плоской поверхности, либо не имеет пересечений ребер, либо может быть перерисован без них.
^ Бартелеми, М. (2017). "1.5 Плоские графы". Морфогенез пространственных сетей . Springer. стр. 6. ISBN 978-3-319-20565-6.
^ Buhl, J.; Gautrais, J.; Sole, RV; Kuntz, P.; Valverde, S.; Deneubourg, JL; Theraulaz, G. (2004), «Эффективность и надежность в муравьиных сетях галерей», European Physical Journal B , 42 (1): 123–129, Bibcode : 2004EPJB...42..123B, doi : 10.1140/epjb/e2004-00364-9, S2CID 14975826.
^ Шнайдер, В. (1989), «Планарные графы и размерность частично упорядоченных множеств», Order , 5 (4): 323–343, doi :10.1007/BF00353652, MR 1010382, S2CID 122785359.
^ Бхаскер, Джаярам; Сахни, Сартадж (1988), «Линейный алгоритм для нахождения прямоугольного двойственного графа планарного триангулированного графа», Algorithmica , 3 (1–4): 247–278, doi :10.1007/BF01762117, S2CID 2709057.
^ Сеймур, PD; Уивер, RW (1984), «Обобщение хордовых графов», Журнал теории графов , 8 (2): 241–251, doi :10.1002/jgt.3190080206, MR 0742878.
^ Фельснер, Стефан (2004), "1.4 Внешнепланарные графы и выпуклые геометрические графы", Геометрические графы и их расположения , Продвинутые лекции по математике, Фридр. Вивег и Зон, Висбаден, стр. 6–7, doi :10.1007/978-3-322-80303-0_1, ISBN 3-528-06972-4, МР 2061507
^ Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Теория графов: Труды конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Lecture Notes in Mathematics, т. 1018, Springer-Verlag, стр. 248–256, doi :10.1007/BFb0071635.
^ Халлдорссон, М.; Китаев, С.; Пяткин., А. (2016). «Полутранзитивные ориентации и графы, представимые в словах» (PDF) . Discr. Appl. Math . 201 : 164–171. doi : 10.1016/j.dam.2015.07.033 . S2CID 26796091.
^ Chen, TZQ; Kitaev, S.; Sun, BY (2016). «Представимость словесных подразделений граней графов треугольной сетки». Graphs and Combin . 32 (5): 1749–61. arXiv : 1503.08002 . doi : 10.1007/s00373-016-1693-z. S2CID 43817300.
^ Chen, TZQ; Kitaev, S.; Sun, BY (2016). "Представимость в словах триангуляции графов цилиндров, покрытых сеткой". Discr. Appl. Math . 213 : 60–70. arXiv : 1507.06749 . doi : 10.1016/j.dam.2016.05.025. S2CID 26987743.
^ Хименес, Омер; Ной, Марк (2009). «Асимптотическое перечисление и предельные законы планарных графов». Журнал Американского математического общества . 22 (2): 309–329. arXiv : math/0501269 . Bibcode :2009JAMS...22..309G. doi :10.1090/s0894-0347-08-00624-3. S2CID 3353537.
^ McDiarmid, Colin; Steger, Angelika ; Welsh, Dominic JA (2005). «Случайные планарные графы». Журнал комбинаторной теории, серия B. 93 ( 2): 187–205. CiteSeerX 10.1.1.572.857 . doi :10.1016/j.jctb.2004.09.007.
^ Bonichon, N.; Gavoille, C.; Hanusse, N.; Poulalhon, D.; Schaeffer, G. (2006). «Планарные графы через хорошо упорядоченные карты и деревья». Графы и комбинаторика . 22 (2): 185–202. CiteSeerX 10.1.1.106.7456 . doi :10.1007/s00373-006-0647-2. S2CID 22639942.
^ Дуймович, Вида ; Йорет, Гвенаэль; Мичек, Петр; Морин, Пэт ; Уккердт, Торстен; Вуд, Дэвид Р. (2020), «Планарные графы имеют ограниченное число очередей», Журнал ACM , 67 (4): 22:1–22:38, arXiv : 1904.04791 , doi : 10.1145/3385731
^ Бозе, Просенжит; Дуймович, Вида ; Джаварсинех, Мехрнуш; Морин, Пэт (2020), Асимптотически оптимальное ранжирование вершин планарных графов , arXiv : 2007.06455
^ Дембски, Михал; Фельснер, Стефан; Мичек, Петр; Шредер, Феликс (2021), «Улучшенные границы для центрированных раскрасок», Advances in Combinatorics , arXiv : 1907.04586 , doi : 10.19086/aic.27351, S2CID 195874032
^ Филотти, И.С.; Майер, Джек Н. (1980). «Алгоритм полиномиального времени для определения изоморфизма графов фиксированного рода». Труды 12-го ежегодного симпозиума ACM по теории вычислений (PDF) . стр. 236–243. doi :10.1145/800141.804671. ISBN 978-0-89791-017-0. S2CID 16345164.
^ Вуд, DR (2007). О максимальном количестве клик в графе. Графы и комбинаторика , 23 (3), 337–352. https://doi.org/10.1007/s00373-007-0738-8

Ссылки

Куратовский, Казимеж (1930), «Sur le problème des courbes gauches en topologie» (PDF) , Fundamenta Mathematicae (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283.
Вагнер, К. (1937), «Über eine Eigenschaft der ebenen Komplexe», Mathematische Annalen (на немецком языке), 114 : 570–590, doi : 10.1007/BF01594196, S2CID 123534907.
Бойер, Джон М.; Мирволд, Венди Дж. (2005), «На переднем крае: упрощенная планарность O(n) путем добавления ребер» (PDF) , Журнал алгоритмов графов и их применения , 8 (3): 241–273, doi : 10.7155/jgaa.00091.
Маккей, Брендан ; Бринкманн, Гуннар, Полезный генератор планарных графов.
де Фрейссе, Х.; Оссона де Мендес, П.; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерных наук , 17 (5): 1017–1029, arXiv : math/0610935 , doi : 10.1142/S0129054106004248, S2CID 40107560. Специальный выпуск о рисовании графиков.
Bader, DA ; Sreshta, S. (1 октября 2003 г.). Новый параллельный алгоритм для тестирования планарности (технический отчет). Технический отчет UNM-ECE 03-002. Архивировано из оригинала 2016-03-16.
Фиск, Стив (1978), «Краткое доказательство теоремы Хватала о стороже», Журнал комбинаторной теории, Серия B , 24 (3): 374, doi :10.1016/0095-8956(78)90059-X.

Внешние ссылки

На Викискладе есть медиафайлы по теме Планарные графы .

Исходный код алгоритма Edge Addition Planarity, версия 1.0 — Бесплатный исходный код C для эталонной реализации алгоритма планарности Бойера–Мирвольда, который предоставляет как комбинаторный планарный встраиваемый модуль, так и изолятор подграфа Куратовского. Проект с открытым исходным кодом и бесплатной лицензией предоставляет алгоритмы Edge Addition Planarity, текущую версию.
Публичная реализация библиотеки и редактора графовых алгоритмов — библиотека графовых алгоритмов GPL, включающая тестирование планарности, встраиватель планарности и демонстрацию подграфов Куратовского за линейное время.
Инструменты библиотеки Boost Graph для плоских графов, включая линейное тестирование планарности, встраивание, изоляцию подграфа Куратовского и рисование прямых линий.
3 утилиты Головоломка и планарные графики
Модель планарности NetLogo — версия игры Джона Тантало для NetLogo