Планарный график - Planar graph

Примеры графиков
Планарный	Непланарный
График бабочки	Полный граф K ₅
Полный граф K ₄	График полезности K _3,3

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

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

Плоские графы можно кодировать комбинаторными картами или системами вращения .

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

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

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

Доказательство без слов , что тессеракт графа является неплоским использованием Куратовских или теорем Вагнера и нахождения либо К ₅ (вверху) или К _3,3 (внизу) подграфам

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

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

{\ displaystyle K_ {3,3}}

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

Пример графа без подграфа K ₅ или K _3,3 . Однако он содержит подразделение K _3,3 и, следовательно, не является плоским.

Вместо того, чтобы рассматривать подразделения, теорема Вагнера имеет дело с несовершеннолетними :

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

{\ displaystyle K_ {5}}

{\ displaystyle K_ {3,3}}

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

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

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

Другие критерии планарности

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

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

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

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

Критерий планарности Уитни дает характеристику, основанную на существовании алгебраического двойственного;
Критерий планарности Мак Лейна дает алгебраическую характеристику конечных планарных графов через их пространства циклов ;
Критерий плоскостности Fraysseix-Rosenstiehl дает характеристику , основанную на существовании двудольности из cotree краев в глубину первого дерева поиска. Это центральный элемент алгоритма проверки лево-правой планарности ;
Теорема Шнайдера дает характеристику планарности в терминах размерности частичного порядка ;
Критерий планарности Колина де Вердьера дает характеристику, основанную на максимальной кратности второго собственного значения некоторых операторов Шредингера, определенных графом.
Теорема Ханани – Тутте утверждает, что граф является плоским тогда и только тогда, когда он имеет рисунок, на котором каждая независимая пара ребер пересекает четное число раз; его можно использовать для характеристики плоских графов с помощью системы уравнений по модулю 2.

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

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

{\ displaystyle 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 ≥ 3:

{\ displaystyle e \ leq 3v-6.}

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

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

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

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

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

Пример теоремы об упаковке кругов на K ^-₅ , полный граф с пятью вершинами без одного ребра.

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

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

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

Плотность плоского графа или сети определяется как отношение количества ребер к количеству возможных ребер в сети с узлами, заданными плоским графом , дающим . Совершенно разреженный планарный граф имеет , в качестве альтернативы полностью плотный плоский граф имеет ${\ displaystyle D}$ ${\ displaystyle E}$ ${\ displaystyle N}$ ${\ Displaystyle (Е _ {\ макс} = 3N-6)}$ ${\ displaystyle D = {\ frac {E-N + 1} {2N-5}}}$ ${\ displaystyle D = 0}$ ${\ displaystyle D = 1}$

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

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

Граф Гольднера – Харари максимально плоский. Все его грани ограничены тремя ребрами.

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

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

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

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

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

Внешнепланарные графы - это графы с вложением в плоскость, все вершины которых принадлежат неограниченной грани вложения. Каждый внешнепланарный граф является плоским, но обратное неверно: K ₄ плоский, но не внешнепланарный. Теорема, аналогичная теореме Куратовского, утверждает, что конечный граф внешнепланарен тогда и только тогда, когда он не содержит подразделения K ₄ или K _2,3 . Вышесказанное является прямым следствием того факта, что граф G является внешнепланарным, если граф, образованный из G путем добавления новой вершины с ребрами, соединяющими ее со всеми другими вершинами, является плоским графом.

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

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

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

Другие родственные семьи

Вершина граф представляет собой график , который может быть плоским удалением одной вершины, и к -apex представляет собой граф , который может быть плоским путем удаления в большинстве K вершин.

1-планарный граф представляет собой график , который может быть обращен в плоскости с не более чем одным простым пересечением на край, а к -planar представляет собой граф , который можно сделать с не более чем к простым пересечениям на край.

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

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

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

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

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

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

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

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

Другие факты и определения

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

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

Планарный граф и его двойственный

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

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

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

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

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

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

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

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

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

Коэффициент сетчатости плоского графа нормализует его количество ограниченных граней (то же самое, что и ранг схемы графа по критерию планарности Мак Лейна ) путем деления его на 2 n - 5, максимально возможное количество ограниченных граней в плоском графе. с n вершинами. Таким образом, он колеблется от 0 для деревьев до 1 для максимальных плоских графов.

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

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

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

Примечания

^ Трюдо, Ричард Дж. (1993). Введение в теорию графов (исправленное, расширенное переиздание. Ред.). Нью-Йорк: Dover Pub. п. 64. ISBN 978-0-486-67870-2. Проверено 8 августа 2012 года . Таким образом, планарный граф, нарисованный на плоской поверхности, либо не имеет пересечений ребер, либо может быть перерисован без них.
Перейти ↑ Barthelemy, M. (2017). Морфогенез пространственных сетей . Нью-Йорк: Спрингер. п. 6.
^ Шнайдера, W. (1989), "Planar графики и посетом измерение", заказ , 5 (4): 323-343, DOI : 10.1007 / BF00353652 , MR 1010382 , S2CID 122785359.
^ Бхаскер, Джаярам; Sahni, Sartaj (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 , МР 0742878.
^ Felsner, Стефан (2004), «1,4 внешнепланарных Графы и Выпуклые геометрические графы», геометрические графики и механизмы , Advanced Лекция по математике, Friedr. Vieweg & Sohn, Висбаден, стр. 6–7, DOI : 10.1007 / 978-3-322-80303-0_1 , ISBN 3-528-06972-4, Руководство по ремонту 2061507
^ Sysło, Maciej M .; Проскуровский, Анджей (1983), «О графах Халина», Теория графов: Труды конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Конспект лекций по математике, 1018 , Springer-Verlag, стр. 248–256, DOI : 10.1007 / BFb0071635.
^ Хименес, Омер; Ной, Марк (2009). «Асимптотическая нумерация и предельные законы плоских графов». Журнал Американского математического общества . 22 (2): 309–329. arXiv : math / 0501269 . Bibcode : 2009JAMS ... 22..309G . DOI : 10.1090 / s0894-0347-08-00624-3 . S2CID 3353537 .
^ МакДиармид, Колин; Стегер, Анжелика ; Валлийский, Доминик 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 .; Шеффер, Г. (2006). «Планарные графики через упорядоченные карты и деревья». Графы и комбинаторика . 22 (2): 185–202. CiteSeerX 10.1.1.106.7456 . DOI : 10.1007 / s00373-006-0647-2 . S2CID 22639942 .
^ Дуймович, Вида ; Йорет, Гвенэль; Мичек, Петр; Morin, Pat ; Ueckerdt, Torsten; Вуд, Дэвид Р. (2020), «Планарные графы имеют ограниченный номер очереди», Журнал ACM , 67 (4): 22: 1–22: 38, arXiv : 1904.04791 , doi : 10.1145 / 3385731
^ Бозе, Просенджит; Дуймович, Вида ; Джаварсине, Мехрнош; Морин, Пат (2020), Асимптотически оптимальное ранжирование вершин плоских графов , arXiv : 2007.06455
^ Дембски, Михал; Фельснер, Стефан; Мичек, Петр; Шредер, Феликс (2019), Улучшенные границы для центрированной раскраски , arXiv : 1907.04586
^ Филотти, Джек Н. Майер. Полиномиальный алгоритм определения изоморфизма графов фиксированного рода. Материалы 12-го ежегодного симпозиума ACM по теории вычислений, с.236–243. 1980 г.
^ Buhl, J .; Gautrais, J .; Подошва, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Тераулаз, Г. (2004), «Эффективность и надежность в муравьиных сетях галерей», European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004EPJB ... 42..123B , doi : 10.1140 / epjb / e2004-00364-9 , S2CID 14975826.
^ М. Халльдорссон, С. Китаев и А. Пяткин. Полутранзитивные ориентации и графы, представимые в виде слов, Discr. Прил. Математика. 201 (2016), 164-171.
^ TZQ Chen, С. Китаев, а ВС Словесная представимость подразделов граней графов треугольной сетки, Графов и Комбинаций. 32 (5) (2016), 1749-1761.
^ TZQ Chen, С. Китаев, а ВС Словесная представимость триангуляций цилиндрических графов, покрытых сеткой, Discr. Прил. Математика. 213 (2016), 60-70.

использованная литература

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

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

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

[1] Трюдо, Ричард Дж. (1993). Введение в теорию графов (исправленное, расширенное переиздание. Ред.). Нью-Йорк: Dover Pub. п. 64. ISBN 978-0-486-67870-2. Проверено 8 августа 2012 года . Таким образом, планарный граф, нарисованный на плоской поверхности, либо не имеет пересечений ребер, либо может быть перерисован без них.

[2] Перейти ↑ Barthelemy, M. (2017). Морфогенез пространственных сетей . Нью-Йорк: Спрингер. п. 6.

[3] Шнайдера, W. (1989), "Planar графики и посетом измерение", заказ , 5 (4): 323-343, DOI : 10.1007 / BF00353652 , MR 1010382 , S2CID 122785359.

[4] Бхаскер, Джаярам; Sahni, Sartaj (1988), "Линейный алгоритм , чтобы найти прямоугольную двойной плоскую триангулированную графу", Algorithmica , 3 (1-4): 247-278, DOI : 10.1007 / BF01762117 , S2CID 2709057.

[5] Сеймур, PD; Уивер, RW (1984), "Обобщение хордальных графов", Журнал теории графов , 8 (2): 241-251, DOI : 10.1002 / jgt.3190080206 , МР 0742878.

[6] Felsner, Стефан (2004), «1,4 внешнепланарных Графы и Выпуклые геометрические графы», геометрические графики и механизмы , Advanced Лекция по математике, Friedr. Vieweg & Sohn, Висбаден, стр. 6–7, DOI : 10.1007 / 978-3-322-80303-0_1 , ISBN 3-528-06972-4, Руководство по ремонту 2061507

[7] Sysło, Maciej M .; Проскуровский, Анджей (1983), «О графах Халина», Теория графов: Труды конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Конспект лекций по математике, 1018 , Springer-Verlag, стр. 248–256, DOI : 10.1007 / BFb0071635.

[8] Хименес, Омер; Ной, Марк (2009). «Асимптотическая нумерация и предельные законы плоских графов». Журнал Американского математического общества . 22 (2): 309–329. arXiv : math / 0501269 . Bibcode : 2009JAMS ... 22..309G . DOI : 10.1090 / s0894-0347-08-00624-3 . S2CID 3353537 .

[9] МакДиармид, Колин; Стегер, Анжелика ; Валлийский, Доминик JA (2005). «Случайные плоские графы». Журнал комбинаторной теории, серии B . 93 (2): 187–205. CiteSeerX 10.1.1.572.857 . DOI : 10.1016 / j.jctb.2004.09.007 .

[10] Bonichon, N .; Gavoille, C .; Hanusse, N .; Poulalhon, D .; Шеффер, Г. (2006). «Планарные графики через упорядоченные карты и деревья». Графы и комбинаторика . 22 (2): 185–202. CiteSeerX 10.1.1.106.7456 . DOI : 10.1007 / s00373-006-0647-2 . S2CID 22639942 .

[11] Дуймович, Вида ; Йорет, Гвенэль; Мичек, Петр; Morin, Pat ; Ueckerdt, Torsten; Вуд, Дэвид Р. (2020), «Планарные графы имеют ограниченный номер очереди», Журнал ACM , 67 (4): 22: 1–22: 38, arXiv : 1904.04791 , doi : 10.1145 / 3385731

[12] Бозе, Просенджит; Дуймович, Вида ; Джаварсине, Мехрнош; Морин, Пат (2020), Асимптотически оптимальное ранжирование вершин плоских графов , arXiv : 2007.06455

[13] Дембски, Михал; Фельснер, Стефан; Мичек, Петр; Шредер, Феликс (2019), Улучшенные границы для центрированной раскраски , arXiv : 1907.04586

[14] Филотти, Джек Н. Майер. Полиномиальный алгоритм определения изоморфизма графов фиксированного рода. Материалы 12-го ежегодного симпозиума ACM по теории вычислений, с.236–243. 1980 г.

[15] Buhl, J .; Gautrais, J .; Подошва, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Тераулаз, Г. (2004), «Эффективность и надежность в муравьиных сетях галерей», European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004EPJB ... 42..123B , doi : 10.1140 / epjb / e2004-00364-9 , S2CID 14975826.

[HKP16-16] М. Халльдорссон, С. Китаев и А. Пяткин. Полутранзитивные ориентации и графы, представимые в виде слов, Discr. Прил. Математика. 201 (2016), 164-171.

[CKS2016-17] TZQ Chen, С. Китаев, а ВС Словесная представимость подразделов граней графов треугольной сетки, Графов и Комбинаций. 32 (5) (2016), 1749-1761.

[CKS2016-2-18] TZQ Chen, С. Китаев, а ВС Словесная представимость триангуляций цилиндрических графов, покрытых сеткой, Discr. Прил. Математика. 213 (2016), 60-70.

Languages

In other projects