Введение

Построение рисунка плоского графа и визуализация его изображения [1-5] являются важными подзадачами, возникающими при решении многих актуальных прикладных задач. Например, для визуализации различных задач современного производства [6,7], а также при создании систем автоматизации проектирования плоских конструктивов, где под плоским конструктивом будем понимать техническое устройство (конструкцию), в котором непересекающиеся соединения между элементами устройства и сами элементы расположены в параллельных (эквидистантных) плоскостях. Это могут быть печатные платы, интегральные микросхемы, БИС, СБИС и т.д. В работе [8] авторами данной статьи был представлен метод проверки планарности графа с одновременным построением математических структур для описания топологического рисунка графа с целью его визуализации. Метод основывается на построении системы изометрических циклов [9,10], понятии вращения вершин графа [11], а также введении операции определения пересечения рёбер как пересечения их проекций на координатно-базисную систему, в качестве которой выступает опорный цикл DFS-дерева графа [8]. Стоит отметить, что на сегодняшний день существуют эффективные алгоритмы, позволяющие определить, является ли граф планарным, со сложностью характеризующейся линейной зависимостью от количества вершин графа [12]. В отличие от алгоритмов с линейной сложностью, метод, описанный в работе [8], обладает более высокой вычислительной сложностью (O(m²), где m – количество вершин графа). Хотя этот метод позволяет не только определить, является ли граф планарным, но и получить топологический рисунок графа, который может затем использоваться для визуализации графа, высокую вычислительную сложность можно считать его существенным недостатком. В данной работе мы будем рассматривать модифицированный метод определения планарности и построения вращения вершин с вычислительной сложностью соизмеримой с алгоритмом Хопкрофта-Тарьяна [13]. Для этой цели необходимо исключить из расчета самую длительную процедуру сравнения проекций обратных маршрутов на координатно-базисную систему, образованную опорным циклом. Такой способ существует! Он основан на способе переформирования DFS-дерева и обратных путей, а также на рекурсивном способе построения обручей.

1. Действия над суграфами

Напомним основные положения и определения, необходимые для описания наших алгоритмов. Пусть задан произвольный граф G. Последовательно просматривая все вершины графа, удалим петли, «висячие» вершины и кратные ребра (если таковые будут найдены). Затем удалим мосты и точки сочленения, тем самым получив несколько компонент связности, которые можно рассматривать по отдельности. Два ребра, соединённых одной вершиной, имеющей локальную степень равную двум, можно заменить одним ребром. Естественно, что преобразование нужно запомнить для последующего восстановления первоначального вида графа G после проверки.

В дальнейшем будем рассматривать несепарабельные неориентированные графы G = (X, U). С этой целью расширим понятие несепарабельного графа.

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

К таким несепарабельным графам для определения планарности можно применить критерий планарности Маклейна [14] и использовать операцию кольцевого суммирования суграфов в подпространстве циклов.

Пусть G = (X,U) – несеперабельный граф с пронумерованным множеством ребер U = {u₁, u₂,...,u_m} и X = {x_1,x₂,...,x_n} вершин, причём card X = n и card U = m. Обычно граф G представляется матрицей инциденций или матрицей смежностей. Графически граф может быть представлен диаграммой, в которой вершина изображена точкой или кружком, а ребро – отрезком линии, соединяющим вершины [15-17].

 

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

Следует отметить, что существуют структуры, которые являются общими для любого плоского изображения графа. Рассмотрим множество простых циклов являющихся границами граней плоского изображения. В качестве примера рассмотрим граф G, представленный на рис. 1. Запишем множество граничных циклов в виде элементов пространства суграфов:

c₁ = {u₂,u₅,u₁₀};  c₂ = {u₃,u₅,u₁₂};  c₃ = {u₈,u₁₀,u₁₂};  c₄ = {u₈,u₉,u₁₁};

c₅ = {u₆,u₇,u₉};  c₆ = {u₃,u₄,u₁₁}; c₇ = {u₁,u₄,u₇};  c₈ = {u₁,u₂,u₆}.

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

 

Рис. 2. Задание направления обхода рёбер в циклах

 

Если задать направление обхода рёбер в циклах с соблюдением условия планарности Маклейна [14], то можно записать циклы как кортежи вершин (см. рис. 2):

 

c₁ = {u₂,u₅,u₁₀}<x₁,x₃,x₆>;  c₂ = {u₃,u₅,u₁₂}<x₁,x₆,x₄>;  c₃ = {u₈,u₁₀,u₁₂}<x₄,x₆,x₃>;

c₄ = {u₈,u₉,u₁₁}<x₄,x₃,x₅>;  c₅ = {u₆,u₇,u₉}<x₃,x₂,x₅>;  c₆ = {u₃,u₄,u₁₁}<x₄,x₅,x₁>;

c₇ = {u₁,u₄,u₇}<x₁,x₅,x₂>;  c₈ = {u₁,u₂,u₆}<x₁,x₂,x₃>.

 

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

 

Рис. 3. Вращение вершины х₁

 

Определение 2.  Для данного графа G вращение вершины А графа G – это ориентированный циклический порядок (или циклическая перестановка) всех рёбер, инцидентных вершине А.

Вращение графа можно описывать и представлять следующим образом. Обозначим вершины x₁,x₂,...,x_n. Затем выпишем циклическую перестановку соседей для каждой вершины x_i. Эта перестановка порождается вращением вершины x_i, которое является циклической перестановкой рёбер, инцидентных вершине x_i.

Вращение вершины x_i будем обозначать . Вращение всех вершин описывается диаграммой вращения вершин . В нашем случае диаграмма вращения вершин имеет вид:

 : x₂   x₅   x₄   x₆   x₃

 : x₃   x₅   x₁

 : x₁   x₆   x₄   x₅   x₂

 : x₆   x₁   x₅   x₃

 : x₄   x₁   x₂   x₃

 : x₁   x₄   x₃

Пусть x₁ – вершина инцидентная ребру u₁ в графе G с вращением . Тогда можно построить в графе G замкнутый маршрут:

х₁,u₁,х₂,u₂,х₃,u₃,...,

(1)

где вершина х₂ – второй конец ребра u₁, а ребро u₂ следует за ребром u₁  во вращении  вершины х₂ определяемом вращением . Затем определяется х₃ как вершина инцидентная ребру u₂ и не равная х₂. После этого в качестве u₃ выбирается ребро, следующее за ребром u₂ во вращении вершины х₃ и т.д. Закончим процесс в точности перед тем моментом когда должна повториться пара х₁, u₁. Она должна повториться, так как граф G конечный, а наш процесс однозначно определён и в обратном направлении, а именно, если часть х_t-1,u_t,х_t,... известна, то ребро u_t-1 определяется вращением вокруг вершины х_t-1. Мы назовём такой замкнутый маршрут циклом, порождённым вершиной х₁ и ребром u₁ и индуцированным вращением .

Тем самым вращение вершин индуцирует (порождает) простые циклы. В свою очередь система независимых циклов и обод индуцируют вращение вершин .

Введём следующие понятия, связанные с метрикой графа.

Определение 3 [7]. Изометрический подграф – подграф G^* графа G, у которого все расстояния внутри G^* те же самые, что и в G.

Определение 4. Изометрическим циклом в графе называется простой цикл, для которого кратчайший путь между любыми двумя его вершинами состоит из рёбер этого цикла. Изометрический цикл – частный случай изометрического подграфа.

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

Теперь предположим, что планарный граф G вложен в евклидову плоскость, причём выполняется такое свойство:

Граница любой внутренней грани – изометрический цикл графа G.

Теперь можно дать определение топологического рисунка графа.

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

Перед тем как перейти к описанию алгоритма, рассмотрим вопросы необходимых действий над суграфами.

Любой суграф может быть записан как множество его рёбер. Что касается ориентированных циклов, то здесь возможно три вида записи цикла, например (см. рис. 4):

c₄ = {u₄,u₅,u₆,u₉,u₂₇}→ <x₂,x₃,x₄,x₁₅,x₁₄,x₂> → <x₂,x₃> + <x₃,x₄> + <x₄,x₁₅> + <x₁₅,x₁₄> + <x₁₄,x₂>.

Первая запись {u₄,u₅,u₆,u₉,u₂₇} характеризуется множеством рёбер. Вторая запись характеризует кортеж, состоящий из последовательности вершин. Третья запись представляет цикл в виде последовательного сложения ориентированных дуг.

 

Рис. 4. Граф G₁

 

Известно также, что любое неориентированное ребро в графе можно представить в виде двух разнонаправленных ориентированных рёбер [15-17]. Например, ребро u₄ можно записать как u₄ = {x₂,x₃} → <x₂,x₃> + <x₃,x₂>. Тогда сложение двух ориентированных циклов можно представить в виде последовательного сложения ориентированных рёбер, например (см. рис. 4):

 

c₄ ⊕ c₅ = {u₄,u₅,u₆,u₉,u₂₇} ⊕ { u₈,u₉,u₁₀,u₁₃,u₂₈} → < x₂,x₃,x₄,x₁₅,x₁₄,x₂> + < x₄,x₅,x₆,x₁₆,x₁₅,x₄> → <x₂,x₃> + <x₃,x₄> + <x₄,x₁₅> + <x₁₅,x₁₄> + <x₁₄,x₂> + <x₄,x₅> + <x₅,x₆> + <x₆,x₁₆> + <x₁₆,x₁₅> + <x₁₅,x₄>  = <x₂,x₃,x₄,x₅,x₆,x₁₆,x₁₅,x₁₄,x₂>.

 

В этой операции разнонаправленные ориентированные рёбра попарно сокращаются.

Другой важной операцией является включение ребра в цикл. Данная операция позволяет разбить цикл на две части. Например, в произвольный цикл c_i = <x₁₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₇,x₁,x₁₈> нужно включить ребро {x₁₀,x₁₇}. Для выполнения этой операции необходимо чтобы концевые вершины вновь введённого ребра (или совокупности рёбер) принадлежали циклу. Тогда к содержимому цикла можно добавить ориентированные дуги данного ребра (или совокупности рёбер):

 

c_i = <x₁₈,x₉> + <x₉,x₁₀> + <x₁₀,x₁₁> + <x₁₁,x₁₂> + <x₁₂,x₁₃> + <x₁₃,x₁₇> + <x₁₇,x₁> + <x₁,x₁₈> + <x₁₇,x₁₀> + <x₁₀,x₁₇>

 

При этом содержимое цикла разбивается на части, где концевые вершины ребра участвуют в формировании маршрутов:

 

<x₁₇,x₁> + <x₁,x₁₈> + <x₁₈,x₉> + <x₉,x₁₀>;

<x₁₀,x₁₁> + <x₁₁,x₁₂> + <x₁₂,x₁₃> + <x₁₃,x₁₇>.

 

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

 

<x₁₇,x₁> + <x₁,x₁₈> + <x₁₈,x₉> + <x₉,x₁₀>+ <x₁₀,x₁₇>;

<x₁₀,x₁₁> + <x₁₁,x₁₂> + <x₁₂,x₁₃> + <x₁₃,x₁₇> + <x₁₇,x₁₀>.

 

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

2. Распределение обратных путей по блокам

Рассмотрим следующий пример проверки на планарность графа G₁ представленного на рис. 4. Выделим DFS-дерево методом поиска в глубину (см. рис. 5).

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

Используя фундаментальную матрицу циклов, выберем самый длинный цикл, образованный ветвями дерева и одной хордой (см. рис. 5). Пусть это будет цикл <x₄,x₅,x₆,x₇,x₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₄,x₄>. Данный цикл будем называть опорным.

Определение 6. Обратным ребром – называется ориентированный маршрут, состоящий из одной хорды.

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

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

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

 

Рис. 5. DFS-дерево графа G₁, опорный цикл и обратные пути.

 

Фундаментальная подматрица  имеет вид:

 

 

Разбиваем подматрицу  на две части: часть, состоящую из ветвей дерева принадлежащих опорному циклу, и часть, состоящую из ветвей дерева не принадлежащих опорному циклу (выделены серым цветом). Строим обратные пути. Для этого объединяем ветви дерева, не включённые в опорный цикл и соответствующую хорду:

 

s₁ = {u₂₇,u₉}  <x₁₄,x₁₅,x₄>  <x₁₄,x₁₅> + <x₁₅,x₄>;

s₂ = {u₂₇,u₂₈,u₂₄}  <x₁₄,x₁₅,x₁₆,х₁₂>  <x₁₄,x₁₅> + <x₁₅,x₁₆> + <x₁₆,x₁₂>;

s₃ = {u₂₇,u₂₈,u₁₃}  <x₁₄,x₁₅,x₁₆,х₆>  <x₁₄,x₁₅> + <x₁₅,x₁₆> + <x₁₆,x₆>;

s₄ = {u₂₆,u₂₁}  <x₁₃,x₁₇,x₁₀>  <x₁₃,x₁₇> + <x₁₇,x₁₀>;

s₅ = {u₂₆,u₂,u₁}  <x₁₃,x₁₇,x₁,х₂>  <x₁₃,x₁₇> + <x₁₇,x₁> + <x₁,x₃>;

s₆ = {u₁₉,u₃,u₁}  <x₉,x₁₈,x₁,x₂>  <x₉,x₁₈> + <x₁₈,x₁> + <x₁,x₂>;

s₇ = {u₁₉,u₂₉,u₇}  <x₉,x₁₈,x₁₉,х₃>  <x₉,x₁₈> + <x₁₈,x₁₉> + <x₁₉,x₃>;

s₈ = {u₁₉,u₂₉,u₃₀,u₁₁}  <x₉,x₁₈,x₁₉,x₂₀,x₅>  <x₉,x₁₈> + <x₁₈,x₁₉> + <x₁₉,x₂₀> + <x₂₀,x₅>;

s₉ = {u₁₉,u₂₉,u₃₀,u₁₇}  <x₉,x₁₈,x₁₉,x₂₀,x₈>  <x₉,x₁₈> + <x₁₈,x₁₉> + <x₁₉,x₂₀> + <x₂₀,x₈>.

 

Объединяем обратные пути в блоки. Объединение в блоки осуществляется по первой вершине:

Блок B₁ включает следующие обратные пути:

{s₁ = <x₁₄,x₁₅,x₄>, s₂ = <x₁₄,x₁₅,x₁₆,х₁₂>, s₃ = <x₁₄,x₁₅,x₁₆,х₆>}.

Блок B₂ включает следующие обратные пути:

{s₄ = <x₁₃,x₁₇,x₁₀>, s₅ = <x₁₃,x₁₇,x₁,х₂>}.

Блок B₃ включает следующие обратные пути:

{s₆ = <x₉,x₁₈,x₁,x₂>, s₇ = <x₉,x₁₈,x₁₉,х₃>, s₈ = <x₉,x₁₈,x₁₉,x₂₀,x₅>, s₉ = <x₉,x₁₈,x₁₉,x₂₀,x₈>}.

В блоке обратных путей B₁ выбираем самый длинный путь, и называем его главным обратным путём для блока B₁. В данном случае это будет путь s₃ = <x₁₄,x₁₅,x₁₆,х₆>. Следующий обратный путь s₂ = <x₁₄,x₁₅,x₁₆,х₁₂> имеет последовательность вершин <x₁₄,x₁₅,x₁₆> уже включённую в главный обратный путь. Остаётся только блочное обратное ребро, состоящее из вершин <x₁₆,x₁₂>. Следующий обратный путь s₁ = <x₁₄,x₁₅,x₄> имеет последовательность вершин <x₁₄,x₁₅> уже включённую в главный обратный путь. Остаётся только блочное обратное ребро, состоящее из вершин <x₁₅,x₄>.

В блоке обратных путей B₂ выбираем самый длинный путь, и называем его главным обратным путём для блока B₂. В данном случае это будет путь s₅ = <x₁₃,x₁₇,x₁,х₂>. Следующий обратный путь s₄ = <x₁₃,x₁₇,x₁₀> имеет последовательность вершин <x₁₃,x₁₇> уже включённую в главный обратный путь. Остаётся только блочное обратное ребро, состоящее из вершин <x₁₇,x₁₀>.

В блоке обратных путей B₃ выбираем самый длинный путь, и называем его главным обратным путем для блока B₃. В данном случае выбираем путь s₉ = <x₉,x₁₈,x₁₉,x₂₀,x₈>. Следующий обратный путь s₈ = <x₉,x₁₈,x₁₉,x₂₀,x₅> имеет последовательность вершин <x₉,x₁₈,x₁₉,x₂₀> уже включённую в главный обратный путь. Остаётся только блочное обратное ребро, состоящее из вершин <x₂₀,x₅>. Следующий обратный путь s₇ = <x₉,x₁₈,x₁₉,х₃> имеет последовательность вершин <x₉,x₁₈,x₁₉> уже включённую в главный обратный путь. Остаётся только блочное обратное ребро состоящее из вершин <x₁₉,x₃>. Наконец, обратный путь s₆ = <x₉,x₁₈,x₁,x₂> имеет последовательность вершин <x₉,x₁₈> уже включённую в главный обратный путь, но вершины х₁ и х₂ не включены в главный обратный путь. Поэтому формируем частичный обратный путь <x₁₈,x₁,x₂> из концевой вершины х₁₈ и остатка х₁,х₂.

 

Рис. 6. Порождение обратных путей

 

Таким образом, можно сказать, что разбиение на блоки породило систему обратных маршрутов:

Блок B₁        {s₃ = <x₁₄,x₁₅,x₁₆,х₆> – главный обратный путь;

                           u₂₄ = <x₁₆,x₁₂> – блочное обратное ребро;

                           u₉ = <x₁₅,x₄>} – блочное обратное ребро.

Блок B₂        {s₅ = <x₁₃,x₁₇,x₁,х₂> – главный обратный путь;

                           u₂₁ = <x₁₇,x₁₀>} – блочное обратное ребро.

Блок B₃        {s₉ = <x₉,x₁₈,x₁₉,x₂₀,x₈> – главный обратный путь;

                           u₁₁ = <x₂₀,x₅> – блочное обратное ребро;

                           u₇ = <x₁₉,x₃> – блочное обратное ребро;

                           s₆ = <x₁₈,x₁,x₂>} – частичный обратный путь.

И обратные рёбра:    u₅ = <x₁₄,x₂>; u₁₅ = <x₁₁,x₇>.

Произведем расположение обратных маршрутов в следующем порядке: вначале разместим главные обратные пути, затем частичные обратные пути, затем блочные обратные рёбра и, наконец, обратные рёбра. Последовательно просматривая порядок расположения обратных маршрутов, производим их включение в обручи с дальнейшим разбиением. В нашем случае порядок расположения обратных маршрутов имеет вид: М = <s₉,s₃,s₅,s₆,u₁₁,u₇,u₂₄,u₉,u₂₁,u₅,u₁₃,u₁₅>. Кортеж M будем называть списком очередности обратных маршрутов.

3. Построение изометрических циклов

Опорный цикл разбивает поверхность R² на две области: внутреннюю и внешнюю. Границы этих областей могут быть описаны двумя симметричными циклами (обручами):

c₁ = <x₂,x₃,x₄,x₅,x₆,x₇,x₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₄,x₂>,

и

c₂ = <x₂,x₁₄,x₁₃,x₁₂,x₁₁,x₁₀,x₉,x₈,x₇,x₆,x₅,x₄,x₃,x₂>.

Определение 9. Обруч – это простой цикл, образованный кольцевой суммой изометрических циклов, каждый из которых имеет, по крайней мере, одно общее ребро с другим изометрическим циклом.

Заметим, что изометрический цикл можно рассматривать как частный случай обруча. В свою очередь, обратные ребра и обратные пути разбивают поверхности на грани, где границами граней служат обручи [8].

Применим операцию включения обратного ребра в обруч графа. Рассмотрим главный обратный путь s₉ = <x₉,x₁₈,x₁₉,x₂₀,x₈> в порядке расположения обратных маршрутов. Концевые вершины пути х₉ и х₈ включаются и в цикл с₁ и в цикл с₂. Учитывая то, что первый обратный маршрут может быть включен в любой цикл, выбираем цикл с₁. Включаем обратный маршрут s₉ в состав цикла с₁. Производим необходимое преобразование. В результате получим два новых цикла:

с₁: <x₂,x₃> + <x₃,x₄> + <x₄,x₅> + <x₅,x₆> + <x₆,x₇> + <x₇,x₈> + <x₈,x₉> + <x₉,x₁₀> + <x₁₀,x₁₁> + <x₁₁,x₁₂> + <x₁₂,x₁₃> + <x₁₃,x₁₄> + <x₁₄,x₂> + <x₉,x₁₈> + <x₁₈,x₁₉> + <x₁₉,x₂₀> + <x₂₀,x₈> + <x₈,x₂₀> + <x₂₀,x₁₉> + <x₁₉,x₁₈> + <x₁₈,x₉> = <x₂,x₃> + <x₃,x₄> + <x₄,x₅> + <x₅,x₆> + <x₆,x₇> + <x₇,x₈> + <x₈,x₂₀> + <x₂₀,x₁₉> + <x₁₉,x₁₈> + <x₁₈,x₉> + <x₉,x₁₀> + <x₁₀,x₁₁> + <x₁₁,x₁₂> + <x₁₂,x₁₃> + <x₁₃,x₁₄> + <x₁₄,x₂> + <x₉,x₁₈> + <x₁₈,x₁₉> + <x₁₉,x₂₀> + <x₂₀,x₈> + <x₈,x₉>;

c₁^' = <x₂,x₃,x₄,x₅,x₆,x₇,x₈,x₂₀,x₁₉,x₁₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₄,x₂>;

c₃ = <x₉,x₁₈,x₁₉,x₂₀,x₈,x₉>.

Таким образом, система сформированных обручей имеет вид:

c₁^' = <x₂,x₃,x₄,x₅,x₆,x₇,x₈,x₂₀,x₁₉,x₁₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₄,x₂>;

c₃ = <x₉,x₁₈,x₁₉,x₂₀,x₈,x₉>;

c₂ = <x₂,x₁₄,x₁₃,x₁₂,x₁₁,x₁₀,x₉,x₈,x₇,x₆,x₅,x₄,x₃,x₂>.

Будем размещать главный обратный цикл s₅ = <x₁₃,x₁₇,x₁,х₂>. Концевые вершины x₂,x₁₃ включаются и в цикл c₁^' и в цикл с₂. Возникла неопределенность. Тогда пробуем разместить главный обратный путь s₃ = <x₁₄,x₁₅,x₁₆,х₆>, обе концевые вершины x₁₄,x₆ обратного пути s₃ = <x₁₄,x₁₅,x₁₆,х₆> включаются и в цикл c₁^' и в цикл с₂. Снова возникла неопределенность. Пробуем поместить путь s₆ = <x₁₈,x₁,x₂>. Он размещается только в c₁ , так как только там имеются совместно две концевые вершины {x₁₈,x₂}. В результате получим два новых цикла:

c₁^': <x₂,x₃> + <x₃,x₄> + <x₄,x₅> + <x₅,x₆> + <x₆,x₇> + <x₇,x₈> + <x₈,x₂₀> + <x₂₀,x₁₉> + <x₁₉,x₁₈> + <x₁₈,x₉> + <x₉,x₁₀> + <x₁₀,x₁₁> + <x₁₁,x₁₂> + <x₁₂,x₁₃> + <x₁₃,x₁₄> + <x₁₄,x₂> + <x₁₈,x₁> + <x₁,x₂> + <x₂,x₁> + <x₁,x₁₈> = <x₂,x₃> + <x₃,x₄> + <x₄,x₅> + <x₅,x₆> + <x₆,x₇> + <x₇,x₈> + <x₈,x₂₀> + <x₂₀,x₁₉> + <x₁₉,x₁₈> + <x₁₈,x₁> + <x₁,x₂> + <x₁₈,x₉> + <x₉,x₁₀> + <x₁₀,x₁₁> + <x₁₁,x₁₂> + <x₁₂,x₁₃> + <x₁₃,x₁₄> + <x₁₄,x₂> + <x₂,x₁> + <x₁,x₁₈>;

с₁^'' = <x₂,x₃,x₄,x₅,x₆,x₇,x₈,x₂₀,x₁₉,x₁₈,x₁,x₂>;

c₄ = <x₁₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₄,x₂,x₁,x₁₈>.

Система обручей имеет вид:

с₁^'' = <x₂,x₃,x₄,x₅,x₆,x₇,x₈,x₂₀,x₁₉,x₁₈,x₁,x₂>;

c₄ = <x₁₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₄,x₂,x₁,x₁₈>;

c₃ = <x₉,x₁₈,x₁₉,x₂₀,x₈,x₉>;

c₂ = <x₂,x₁₄,x₁₃,x₁₂,x₁₁,x₁₀,x₉,x₈,x₇,x₆,x₅,x₄,x₃,x₂>.

Размещаем обратный маршрут s₃ = <x₁₄,x₁₅,x₁₆,х₆> в с₂. В результате получим два новых цикла:

с₂^' = <x₁₄,x₁₃x₁₂,x₁₁,x₁₀,x₉,x₈,x₇,x₆,x₁₆,x₁₅,x₁₄>;

c₅ = <x₂,x₁₄,x₁₅,x₁₆,x₆,x₅,x₄,x₃,x₂>.

Система обручей имеет вид:

с₂^' = <x₁₄,x₁₃x₁₂,x₁₁,x₁₀,x₉,x₈,x₇,x₆,x₁₆,x₁₅,x₁₄>;

c₅ = <x₂,x₁₄,x₁₅,x₁₆,x₆,x₅,x₄,x₃,x₂>;

с₁^'' = <x₂,x₃,x₄,x₅,x₆,x₇,x₈,x₂₀,x₁₉,x₁₈,x₁,x₂>;

c₄ = <x₁₈,x₉,x₁₀,x₁₁,x₁₂,x₁₃,x₁₄,x₂,x₁,x₁₈>;

c₃ = <x₉,x₁₈,x₁₉,x₂₀,x₈,x₉>.

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

Окончательная система изометрических циклов имеет вид:

с₂^''' = <x₁₂,x₁₁,x₇,x₆,x₁₆,x₁₂> → {u₂₂,u₁₅,u₁₂,u₁₃,u₂₄};

c₁₂ = <x₁₁,x₁₀,x₉,x₈,x₇,x₁₁> → {u₂₀,u₁₈,u₁₆,u₁₄,u₁₅};

с₁^'''' = <x₂,x₃,x₁₉,x₁₈,x₁,x₂> → {u₄,u₇,u₂₉,u₃,u₁};

c₁₁ = <x₃,x₄,x₅,x₂₀,x₁₉,x₃> → {u₆,u₈,u₁₁,u₃₀,u₇};

c₁₀ = <x₅,x₆,x₇,x₈,x₂₀,x₅> → {u₁₀,u₁₂,u₁₄,u₁₇,u₁₁};

с₄^'' = <x₁₈,x₉,x₁₀,x₁₇,x₁,x₁₈> → {u₁₉,u₁₈,u₂₁,u₂,u₃};

c₉ = <x₁₀,x₁₁,x₁₂,x₁₃,x₁₇,x₁₀> → {u₂₀,u₂₂,u₂₃,u₂₆,u₂₁};

с₅^' = <x₂,x₁₄,x₁₅,x₄,x₃,x₂> → {u₅,u₂₇,u₉,u₆,u₄};

c₈ = <x₁₅,x₁₆,x₆,x₅,x₄,x₁₅> → {u₂₈,u₁₃,u₁₀,u₈,u₉};

c₇ = <x₁₄,x₁₃,x₁₂,x₁₆,x₁₅,x₁₄> → {u₂₅,u₂₃,u₂₄,u₂₈,u₂₇};

c₆ = <x₂,x₁,x₁₇,x₁₃,x₁₄,x₂> → {u₁,u₂,u₂₆,u₂₅,u₅};

c₃ = <x₉,x₁₈,x₁₉,x₂₀,x₈,x₉> → {u₁₉,u₂₉,u₃₀,u₁₇,u₁₆}.

Так как кольцевая сумма циклов есть пустое множество, то данная система циклов характеризует топологический рисунок плоского графа [5,14]. Диаграмма вращения вершин представлена на рис. 7 [11], а топологический рисунок представлен на рис. 8.

 

4. Задача выбора опорного цикла

 

 

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

Рассмотрим следующий граф, представленный на рис. 9. Выделим DFS-дерево (см. рис. 10). Выберем самый длинный цикл <x₁,x₂,x₉,x₃,x₈,x₁₀,x₁> и назовем его опорным циклом. Будем рассматривать только подматрицу . Выделенный опорный цикл разбивает подматрицу  на две части. Ветви дерева, вошедшие в опорный цикл, образуют подмножество R₁. Ветви дерева, не вошедшие в опорный цикл – подмножество R₂ (серый цвет). Так как построение дерева определяет ориентированный граф, то в качестве элементов подматрицы будут выступать и ориентированные рёбра.

 

 

Будем строить обратные пути. С этой целью выпишем все фундаментальные циклы в виде множества ребер:

с₁ = {u₂,u₁,u₇,u₁₀,u₉}; с₂ = {u₃,u₁,u₇}; с₃ = {u₄,u₁,u₇,u₁₀,u₉,u₂₁}; с₄ = {u₅,u₇,u₁₀};

с₅ = {u₆,u₇,u₁₀,u₉,u₁₄}; с₆ = {u₈,u₉,u₁₄}; с₇ = {u₁₁,u₁₃,u₁₇,u₁₅}; с₈ = {u₁₂,u₁₃,u₁₇};

с₉ = {u₁₆,u₁₇,u₁₅}; с₁₀ = {u₁₈,u₁₄,u₁₃}; с₁₁ = {u₁₉,u₂₁,u₁₄,u₁₃}; с₁₂ = {u₂₀,u₁₀,u₉}.

Курсивом выделены хорды, жирным шрифтом выделены рёбра дерева, вошедшие в опорный цикл, простым шрифтом – рёбра дерева, не вошедшие в опорный цикл. Исключим из описания циклов ребра, вошедшие в опорный цикл. Получим следующие части циклов:

s₁ = {u₂}; s₂ = {u₃}; с₃ – опорный цикл; s₄ = {u₅};

s₅ = {u₆,u₁₄}; s₆ = {u₈,u₁₄}; s₇ = {u₁₁,u₁₃,u₁₇,u₁₅}; s₈ = {u₁₂,u₁₃,u₁₇};

s₉ = {u₁₆,u₁₇,u₁₅}; s₁₀ = {u₁₈,u₁₄,u₁₃}; s₁₁ = {u₁₉,u₁₄,u₁₃}; s₁₂ = {u₂₀}.

Запишем полученные части циклов как обратные рёбра в виде ориентированных маршрутов:

s₁ = {u₂}  <x₈,x₁>; s₂ = {u₃}  <x₉,x₁>; s₄ = {u₅}  <x₃,x₂>;

s₅ = {u₆,u₁₄} <x₄,x₂> + <x₈,x₄> = <x₈,x₄,x₂>;

s₆ = {u₈,u₁₄} <x₄,x₃> + <x₈,x₄> = <x₈,x₄,x₃>;

s₇ = {u₁₁,u₁₃,u₁₇,u₁₅} <x₅,x₄> + <x₄,x₇> + <x₇,x₆> + <x₆,x₅> = <x₅,x₄,x₇,x₆,x₅>;

s₈ = {u₁₂,u₁₃,u₁₇} <x₆,x₄> + <x₄,x₇> + <x₇,x₆> = <x₆,x₄,x₇,x₆>;

s₉ = {u₁₆,u₁₇,u₁₅} <x₅,x₇> + <x₇,x₆> + <x₆,x₅>= <x₅,x₇,x₆,x₅>;

s₁₀ = {u₁₈,u₁₄,u₁₃} <x₇,x₈> + <x₈,x₄> + <x₄,x₇>= <x₇,x₈,x₄,x₇>;

s₁₁ = {u₁₉,u₁₄,u₁₃} <x₈,x₄> + <x₄,x₇> + <x₇,x₁₀> += <x₈,x₄,x₇,x₁₀>;

s₁₂ = {u₂₀}  <x₈,x₉>.

 

Рис. 11. Построение обратных путей для выбранного опорного цикла

 

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

 

Рис. 12. Новое DFS-дерево графа G₂ и новый опорный цикл

 

Для преобразования ищем единственный элемент в строке подматрицы R₁. Такая подстрока имеется – это хорда u₁₉. Выбираем обратный маршрут s₁₁, так как в нем количество ветвей дерева, не вошедших в опорный цикл больше, чем в других случаях. Производим преобразования в подматрице . Объявляем хорду u₁₉ ребром дерева, принадлежащим опорному циклу, и включаем в подматрицу , а ребро дерева u₂₁ объявляем хордой и исключаем из подматрицы . Ветви дерева u₁₃ и u₁₄ включаем в опорный цикл. Тем самым преобразуем DFS-дерево графа G₂ (см. рис. 12).

Для нового дерева построим подматрицу :

 

 

Рис. 13. Новое DFS-дерево и новый опорный цикл

 

Продолжим увеличивать длину опорного цикла. Для преобразования выбираем обратный маршрут характеризующийся строкой матрицы c хордой u₁₁, так как в ней имеется единственный элемент в подматрице R₁ и количество ветвей дерева не вошедших в опорный цикл больше, чем в других случаях. Производим преобразования в подматрице . Объявляем хорду u₁₁ ребром дерева, принадлежащим опорному циклу, и включаем в подматрицу , а ребро дерева u₁₃ объявляем хордой и исключаем из подматрицы . Ветви дерева u₁₅ и u₁₇ включаем в опорный цикл, изменяя ориентацию. Тем самым преобразуем DFS-дерево графа G₂ (см. рис. 13).

Окончательно подматрица принимает вид:

 

 

В результате получаем множество, состоящее только из обратных рёбер.

Формируем множество обратных рёбер:

{u₂}  <x₈,x₁>; {u₃}  <x₉,x₁>; {u₅}  <x₃,x₂>;

{u₆} <x₄,x₂> ; {u₈} <x₄,x₃> ;

{u₁₃} <x₇,x₄>; {u₁₂} <x₆,x₄>;

{u₁₆} <x₇,x₅>; {u₁₈} <x₇,x₈>;

{u₂₀} <x₈,x₉>; {u₂₁}  <x₁₀,x₈>.

Будем формировать изометрические циклы графа, встраивая обратные рёбра в обручи (циклы).

c₁ = <x₁,x₂,x₉,x₃,x₄,x₅,x₆,x₇,x₈,x₁₀,x₁>;

c₂ = <x₁,x₁₀,x₈,x₇,x₆,x₅,x₄,x₃,x₉,x₂,x₁>

Вставим в цикл с₁ обратное ребро {u₂}  <x₈,x₁>.

c₁: <x₁,x₂> + <x₂,x₉> + <x₉,x₃> + <x₃,x₄> + <x₄,x₅> + <x₅,x₆> + <x₆,x₇> + <x₇,x₈> +

+ <x₈,x₁₀> + <x₁₀,x₁> + <x₈,x₁> + <x₁,x₈> = (<x₁,x₂> + <x₂,x₉> + <x₉,x₃> + <x₃,x₄> + <x₄,x₅> + <x₅,x₆> + <x₆,x₇> + <x₇,x₈> + <x₈,x₁> ) +

+ (<x₈,x₁₀> + <x₁₀,x₁> + <x₁,x₈>).

Образуются два новых обруча:

c₁^' = <x₁,x₂,x₉,x₃,x₄,x₅,x₆,x₇,x₈,x₁>;

c₃ = <x₈,x₁₀,x₁,x₈>.

Система обручей имеет вид:

c₁^' = <x₁,x₂,x₉,x₃,x₄,x₅,x₆,x₇,x₈,x₁>;

c₂ = <x₁,x₁₀,x₈,x₇,x₆,x₅,x₄,x₃,x₉,x₂,x₁>;

c₃ = <x₈,x₁₀,x₁,x₈>.

Продолжаем процесс введения обратных рёбер до полного их исчерпания. Окончательно система обручей имеет вид:

с₁^''''' = <x₆,x₇,x₈,x₄,x₆>;

с₂^'''' = <x₄,x₂,x₁,x₁₀,x₇,x₄>;

c₃ = <x₈,x₁₀,x₁,x₈>;

c₄ = <x₈,x₇,x₁₀,x₈>;

c₅^' = <x₁,x₂,x₉,x₁>;

c₆ = <x₃,x₉,x₂,x₃>;

c₇ = <x₉,x₈,x₁,x₉>;

c₈ = <x₄,x₃,x₂,x₄>;

c₉ = <x₉,x₃,x₈,x₉>;

c₁₀ = <x₈,x₃,x₄,x₈>;

с₁₁^' = <x₇,x₆,x₅,x₇>;

c₁₂ = <x₄,x₅,x₆,x₄>;

c₁₃ = <x₅,x₄,x₇,x₅>.

В результате получен плоский топологический рисунок графа G₂ состоящий из изометрических циклов (см. рис. 14).

 

Рис. 14. Топологический рисунок графа G₂.

 

5. Обоснование алгоритма

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

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

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

 

Рис. 15. Топологический рисунок плоского графа.

 

Например, для топологического рисунка графа, представленного на рис.15, вращение вершин описывается диаграммой:

x₁: u₃  u₂  u₄  u₁

x₂: u₆  u₅  u₅

x₃: u₈  u₂  u₇

x₄: u₁₃  u₇  u₉

x₅: u₁₂  u₁₁  u₅

x₆: u₁₁  u₁₃  u₉  u₃

x₇: u₁₅  u₁₄  u₈  u₁₀  u₁₃  u₁₂

x₈: u₄  u₁₄  u₁₇  u₁₆ 

x₉: u₁₉  u₆  u₁₆  u₁₈ 

x₁₀: u₂₀  u₁₈  u₁₇

x₁₁: u₁₅  u₁₉  u₂₀

Множество изометрических циклов и обод:

с₁ = {u₁,u₃,u₅,u₁₁}; с₂ = {u₁,u₄,u₆,u₁₆}; с₃ = {u₂,u₃,u₇,u₉};

с₄ = {u₂,u₄,u₈,u₁₄}; с₅ = {u₅,u₆,u₁₂,u₁₅,u₁₉}; с₆ = {u₇,u₈,u₁₀};

с₇ = {u₉,u₁₀,u₁₃}; с₈ = {u₁₁,u₁₂,u₁₃};

с₉ = {u₁₆,u₁₇,u₁₈}; с₁₀ = {u₁₈,u₁₉,u₂₀}; с₀ = {u₁₄,u₁₅,u₁₇,u₂₀}.

Выделим цикл {u₁₄,u₁₅,u₁₇,u₂₀}. Проведем разрезающий маршрут <u₃,u₄,u₁₃> вершины которого х₇ и х₈ принадлежат циклу. Тогда подмножество вершин {x₂,x₅,x₉} характеризует внутренность левой части, а подмножество вершин {x₃,x₄} характеризует внутренность правой части. В свою очередь инцидентные ребра левой части графа образуют подмножество {u₁,u₅,u₆,u₁₁,u₁₂,u₁₆,u₁₈,u₁₉}, а инцидентные ребра для правой части образуют подмножество {u₂,u₇,u₈,u₉,u₁₀}. Соответственно подмножество циклов {c₁,c₂,c₅,c₈,c₉,c₁₀} характеризует левую часть, а подмножество {c₃,c₄,c₆,c₇} характеризует правую часть. Тогда можно сформировать два цикла проходящих по ребрам маршрут и части выделенного цикла:

с₁  с₂  с₅  с₈  с₉  с₁₁ = {u₁,u₃,u₅,u₁₁} {u₁,u₄,u₆,u₁₆}  {u₅,u₆,u₁₂,u₁₅,u₁₉}  {u₁₁,u₁₂,u₁₃}  {u₁₆,u₁₇,u₁₈}  {u₁₈,u₁₉,u₂₀} = {u₃,u₄,u₁₅,u₁₃,u₁₇,u₂₀};

с₃  с₄  с₆  с₇ = {u₂,u₃,u₇,u₉}  {u₂,u₄,u₈,u₁₄}  {u₇,u₈,u₁₀}  {u₉,u₁₀,u₁₃} = {u₃,u₄,u₁₃,u₁₄}.

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

6. Алгоритм удлинения опорного цикла

Опишем алгоритм удлинения опорного цикла.

шаг 1. [Выбор максимального по длине цикла]. Строим матрицу фундаментальных циклов графа. Выбираем максимальный по длине цикл.

шаг 2. [Построение обратных маршрутов]. Формируем обратные маршруты графа. Для этого объединяем ветви дерева, не включенные в опорный цикл и соответствующую хорду.

шаг 3. [Проверка обратных маршрутов на замкнутость]. Проверяем обратные пути на замкнутость и соответствие концевых вершин опорному циклу. Если таких обратных путей нет, конец работы алгоритма.

шаг 4. [Построение нового опорного цикла]. Находим обратный маршрут, у которого количество ветвей дерева не вошедших в опорный цикл превышает количество вошедших. Одну из ветвей дерева входящих в опорный цикл объявляем хордой, а хорду данного обратного маршрута объявляем ветвью дерева, входящей в опорный цикл. Включаем ветви дерева данного обратного маршрута, не входящие в опорный цикл во множество ветвей дерева, входящих в опорный цикл с возможной их переориентацией. В случае необходимости переориентируем обратные ветви, иначе – окончательный опорный цикл выбран; конец работы алгоритма.

шаг 5. [Построение новой матрицы фундаментальных циклов]. Строим новое DFS-дерево и новую матрицу фундаментальных циклов графа и идем на шаг 4.

Конец алгоритма.

В общем случае, количество операций для выделения дерева графа поиском в глубину определяется величиной равной рангу графа  и не может быть больше количества ребер в графе [18]. Поэтому вычислительная сложность данного алгоритма может быть описана как f₁(m) = O(m).

7. Алгоритм метода нитей

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

Опишем алгоритм проверки графа на планарность методом нитей.

шаг 1. [Построение DFS-дерева]. Методом поиска в глубину строим DFS-дерево графа.

шаг 2. [Выбор опорного цикла]. Строим матрицу фундаментальных циклов графа и выбираем опорный цикл.

шаг 3. [Формирование обратных путей]. Формируем обратные пути графа относительно выбранного опорного цикла. Для этого объединяем не включённые в опорный цикл ветви дерева и соответствующую хорду. Если концевые вершины сформированных обратных путей не принадлежат опорному циклу и имеются обратные пути в виде замкнутых маршрутов, то производим удлинение опорного цикла и идём на шаг 2.

шаг 4. [Построение блоков обратных путей]. Обратные пути, имеющие одинаковые вершины в качестве истока, объединяем в блоки. Ранжируем обратные маршруты в блоках.

шаг 5. [Включение обратных маршрутов в обручи графа]. Последовательно подключаем обратные маршруты в обручи графа согласно рангу. При подключении образуем новые обручи графа.

шаг 6. [Построение системы изометрических циклов и топологического рисунка плоского графа]. В результате построения, если подключены все обратные пути и обратные рёбра, получаем систему изометрических циклов графа. Строим диаграмму вращения вершин. Если имеются неподключенные обратные маршруты, то граф непланарен.

Конец алгоритма.

В свою очередь, количество последовательно подключаемых обратных маршрутов (нитей) не может быть больше, чем количество рёбер графа. Поэтому вычислительную сложность алгоритма включения обратных маршрутов можно определить как f₂(m) = O(m).

Последовательное применение алгоритмов можно оценить как аддитивную сумму их вычислительных сложностей f₁(m) + f₂(m) = O(m).

8. Оценка сложности метода

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

Процесс построения такого списка состоит из перечисления всех ребер графа представленных в виде u_k = (x_i,x_j)  (x_j,x_i), k{1,…,m} с записью текущего номера ребра в ячейку соответствующую записи вершин (x_i,x_j) для прямого ребра, и в ячейку соответствующую записи вершин (x_j,x_i) для обратного ребра. Вычислительная сложность процесса может быть представлена как функция f₁ = m.  В крайнем случае, m = n(n-1)/2 и тогда вычислительная сложность данного процесса определяется как O(n²).

Трудоемкость процесса выделения DFS-дерева можно определить как перечисление всех веощин x  X для неоткрытых вершин, и первое, что она делает – это помечает переданную в качестве параметра вершину. Но для каждой вершины осуществляется просмотр и проверка на смежность всех остальных вершин. Вычислительная сложность процесса может быть представлена как функция f₂ = nn = n². Итого O(n²), где n - количество вершин в графе. Параллельно определяются хорды и ветви дерева.

Процесс построения фундаментальной подматрицы циклов  относительно множества хорд Н = {h₁,h₂,…,h_m-n+1} осуществляется процедурой поиска в ширину для каждой хорды (число которых равно цикломатическому числу графа) на ациклическом подграфе, состоящем только из ветвей дерева, и определением пути между двумя вершинами. Вычислительная сложность процесса может быть представлена функцией f₃ = (m-n+1)n = mn - n² + n. В наихудшем случае, m = n(n-1)/2, тогда f₃ = (n³ –3n²)/2 + n. Итого O(n³).

Задача выделения опорного цикла состоит из операции определения количества ребер в каждом цикле и выборе максимального по длине цикла. Длина максимально возможного цикла может быть определена как ранг графа (n-1). Вычислительная сложность процесса может быть представлена функцией f₄ = (m – n + 1)(n – 1) = m(n – 1) – n² + 2n – 1. В крайнем случае, m = n(n-1)/2, тогда f₄ = (n³ –4n²+5n–2)/2. Итого O(n³).

Процесс разделения элементов подматрицы  на ветви дерева, принадлежащие и не принадлежащие опорному циклу, касается всех элементов подматрицы циклов, число которых может быть определено как (m-n+1)(n-1). Параллельно с этим определяется количество ветвей дерева принадлежащих и не принадлежащих опорному циклу, проходящему по данной хорде. Тогда вычислительную сложность процесса можно представить функцией f₅ = (m-n+1)(n-1) = m(n – 1)-n²+2n-1 =(n³-4n²+5n-2)/2. Итого O(n³).

Увеличение длины опорного цикла приводит к преобразованию всех элементов подматрицы циклов  и добавлению к ней элементов. Общее число преобразуемых элементов может быть определено как (m-n+1)(n-1). Но так как операция увеличения длины опорного цикла производится для всех циклов, число которых равно количеству хорд графа, то выражение (m-n+1)(n-1) нужно умножить на величину (m-n+1). Тогда вычислительную сложность процесса можно представить функцией f₆ = (m-n+1)(m-n+1)(n-1) = (n⁵-7n⁴+19n³-25n²+16n-4)/4. Итого O(n⁵).

Формирование обратных ветвей и блоков обратных ветвей может быть произведено для множества хорд графа, количество которых равно числу m-n+1. Параллельно определяем общие вершины для обратных маршрутов, входящих в блок. Тогда вычислительную сложность процесса можно представить функцией f₇ = (m-n+1) = (n²-3n+2)/2. Итого O(n²).

Вычислительный процесс формирования множества изометрических циклов начинается с записи опорного цикла в виде последовательности ориентированных ребер для соответствующей хорды с последовательным порядком подключения входящих ветвей дерева. В результате формируется запись цикла в векторном виде. Для формирования другого цикла производится запись векторов цикла в обратном порядке. Очевидно, что функцию вычислительной сложности можно записать как f₈=2(n-1). Итого O(n).

Дальнейшее формирование изометрических циклов производится путем выбора единственного из вновь образованных циклов, содержащего концевые вершины обратного маршрута. Количество вновь образованных циклов не может превышать цикломатическое число графа и в наихудшем случае равно ему. Далее выбранный цикл разбивается на две части относительно концевых вершин с подключением соответствующих ориентированных обратных маршрутов. Число просматриваемых при этом ориентированных ребер можно определить, как 2(n-1). Параллельно определяется количество обратных маршрутов, еще не участвовавших в процессе формирования изометрических циклов. В конце расчета, если количество оставшихся обратных маршрутов не равно нулю, делается вывод о том, что исходный граф не планарный. Учитывая, что количество изометрических циклов равно цикломатическому числу графа, то вычислительную сложность процесса можно представить функцией f₉ = (m-n+1)(m-n+1)(n-1) = (n⁵-7n⁴+19n³-25n²+16n-4)/4. Итого O(n⁵).

Вычислительный процесс построения диаграммы вращения вершин, характеризующей топологический рисунок графа, заключается в последовательном просмотре всех ориентированных ребер в изометрическом цикле или ободе и записью для каждой вершины смежной вершины соответствующего ориентированного ребра. Вычислительную сложность алгоритма можно представить функцией f₁₀ = (m-n+2)(n-1)=(n³-4n²+7n-4)/2. Итого O(n³).

Общую вычислительную сложность алгоритма можно представить аддитивным сложением всех вычислительных сложностей процедур f = . Данная функция позволяет оценить общую вычислительную сложность алгоритма как O(n5).

Заключение

В данной работе рассматривается модифицированный алгоритм проверки графа на планарность с одновременным построением математических структур для описания топологического рисунка плоского графа. Основой расчета является выделение DFS-дерева графа. Затем производится выделение опорного цикла, который производит разбиение поверхности R² на внутреннюю и внешнюю области. Выделенное дерево позволяет построить фундаментальную матрицу циклов. В свою очередь, выделение опорного цикла разбивает подматрицу  фундаментальной матрицы циклов на две подматрицы: с ветвями дерева входящими, и с ветвями дерева не входящими в опорный цикл. Подматрица, состоящая только из ветвей дерева не вошедших в опорный цикл, позволяет формировать обратные маршруты. В случае существования обратных замкнутых маршрутов и обратных маршрутов с концевыми вершинами, не принадлежащими опорному циклу, алгоритмом удлинения опорного цикла строится новый опорный цикл, что порождает новое построение DFS-дерева графа и новую фундаментальную матрицу циклов. В случае отсутствия обратных замкнутых маршрутов и обратных маршрутов с концевыми вершинами, не принадлежащими опорному циклу, производится объединение обратных маршрутов в блоки и их ранжирование. Обратные маршруты последовательно просматриваются согласно их рангу, и в случае, если их концевые вершины принадлежат единственному обручу, производится размещение данного обратного маршрута с разбиением данного обруча на два обруча меньшей длины. Процесс продолжается рекурсивно до полного исчерпания списка обратных маршрутов. В этом случае граф планарен. Если список обратных маршрутов не исчерпан, то граф не планарен. Вычислительная сложность алгоритма оценивается как O(n⁵). Полученная система изометрических циклов графа индуцирует вращение вершин для описания топологического рисунка плоского графа. Топологический рисунок плоской части графа позволяет описывать процесс планаризации алгебраическими методами, не производя никаких геометрических построений на плоскости. Получение вращения вершин графа сразу решает две важнейшие задачи теории графов: задачу проверки графа на планарность и задачу построения топологического рисунка плоского графа.

В работах [5-7] нами показано, что задачу построения рисунка непланарного графа можно свести к задаче построения рисунка плоского графа с учетом введения дополнительных вершин характеризующих пересечение рёбер. Естественно, что применение этого подхода требует решения таких задач теории графов как проверка планарности графа, выделение максимально плоского суграфа, определение толщины графа, получение графа с минимальным количеством пересечений и т.д. Таким образом, на первый план по важности решения выдвигается задача визуализации плоского рисунка графа. Эта задача решается в два этапа: задаётся топологический рисунок плоского графа и производится геометрическое расположение вершин и рёбер, так чтобы не нарушить структуру топологического рисунка графа.

Список литературы

1. З. В. Апанович. От рисования графов к визуализации информации. Новосибирск, РАН, 2007. – 24 c.;
2. G. Di Battista. Algorithms for Drawing Graphs: an Annotated Bibliography / G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis // Comp. Geom., Theory and Appl. – 1994. – N 4. – P. 235–282.
3. R. Tamassia. Handbook of Graph Drawing and Visualization. C&H/CRC – 2013. – 844 p.
4. В. Н. Касьянов, В. А. Евстигнеев. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. – 1104 c.;
5. С. В. Курапов, А. В. Толок. Методы построения топологического рисунка графа // Автоматика и телемеханика. 2013. №9. C.78–97; англ. пер.: S. V. Kurapov, A. V. Tolok. The topological drawing of a graph: Construction methods // Autom. Remote Control. 2013. Vol. 74, Issue 9. – P. 1494–1509.
6. С. В. Курапов, М. В. Давидовский. Два подхода к проведению соединений в плоских конструктивах. Компоненты и технологии. 2015. № 7. С. 142–147;
7. С. В. Курапов, М. В. Давидовский. Топологический подход к проведению соединений в плоских конструктивах. Компоненты и технологии. 2015. № 11. С. 127–130;
8. С. В. Курапов, М. В. Давидовский. Проверка планарности и построение топологического рисунка плоского графа (поиском в глубину) // ПДМ. 2016. №2(32). С.100–115.
9. T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, et al. Cycle bases in graphs – characterization, algorithms, complexity, and applications // Comput. Sci. Rev. 2009. No.3. P.199–243.
10. М. Деза. Изометрические полиэдральные подграфы в гиперкубах и кубических решетках. / М. Деза, В. Гришухин, А.И. Штогрин – М.: МЦНМО, 2007. – 192 с.;
11. Г. Рингель. Теорема о раскраске карт. / Г. Рингель – М.: Мир. – 1977. – 126 с.;
12. M. Patrignani. Planarity testing and embedding. Chapter 1. Handbook of Graph Drawing and Visualization. Roberto Tamassia, Editor. CRC Press. June 24, 2013. – P.1–42.
13. Дж.Е., Хопкрофт, Р.Е. Тарьян. Изоморфизм планарных графов / Дж.Е. Хопкрофт, Р.Е. Тарьян // В кн.: Кибернетический сборник. Новая серия. Вып. 12. – 1975. – С.39–61;
14. С. Мак-Лейн. Комбинаторное условие для плоских графов / С. Мак-Лейн // В кн.: Кибернетический сборник. Новая серия. – 1970. Вып. 7. – С.133–144.;
15. А.А. Зыков. Теория конечных графов. Новосибирск: ГРФМЛ. – 1963. – 542 с.;
16. М. Свами. Графы, сети и алгоритмы. М.: Мир. – 1984. – 455 с.;
17. Ф. Харари. Теория графов. – Пер. с англ. Козырева В.П. / под ред. Гаврилова В.Г. / Ф. Харари – М.: Мир. – 1973. – 300 с.;
18. E. Korach, Z. Ostfeld. DFS tree construction: Algorithms and characterizations // In: van Leeuwen J. (eds) Graph-Theoretic Concepts in Computer Science. WG 1988. Lecture Notes in Computer Science. – Vol 344. – Springer, Berlin, Heidelberg. – 1989.

---

A modified algorithm for planarity testing and constructing the topological drawing of a graph. The thread method.

Authors: S.V. Kurapov^1,A, M.V. Davidovsky^2,B, A.V. Tolok^3,C

^A Zaporizhzhia National Universite, Ukraine

^B Zaporozhye Institute of Postgraduate Pedagogical Education, Ukraine

^C Moscow State Technological University «STANKIN», Russia

¹ ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru

² ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com

³ ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru

 

Abstract

In this article we present a modified algorithm for graph planarity testing with simultaneous con-struction of a mathematical framework for representing the topological drawing of a plane graph. This mathematical framework is based on the notions of graph isometric cycles and rotation of graph vertices. Obtaining the rotation of graph vertices solve two major problems: the problem of graph planarity testing and the problem of constructing the topological drawing of a planar graph. The system of graph isometric cycles, which is obtained as a result of the algorithm execution, induces the rotation of graph vertices for representing the topological drawing of the graph. The topological drawing is used subsequently for visualization of the plane graph. The topological drawing of the flat part of a graph allows describing the process of planarization by algebraic methods without making any geometric constructions on the plane. The proposed algorithm is based on the reconstruction of the reference cycle and construction of reverse path blocks. The basis for calculation is the selection of the DFS-tree of the graph by the depth-first-search meth-od. Visualization of planar graphs is one of the most important sub-tasks in addressing a number of topical applications, such as the design of complex products and systems, flat constructions, social network analysis and many others. The computational complexity of the algorithm is esti-mated as O(m) = f1(m) + f2(m), where m – is the number of graph edges.

 

Keywords: graph, planarity testing, graph visualization, topological graph drawing, vertices rotation diagram, isometric cycles, reference cycle.

References

               

1. Z.V. Apanovich. Ot risovaniya grafov k vizualizatsii informatsii [From Graph Drawing to Information Visualization], Novosibirsk: Nauka, 2007. – 24 s. [In Russian]
2. G. Di Battista. Algorithms for Drawing Graphs: an Annotated Bibliography / G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis // Comp. Geom., Theory and Appl. – 1994. – N 4. – P. 235–282.
3. R. Tamassia. Handbook of Graph Drawing and Visualization. C&H/CRC – 2013. – 844 p.
4. V. N. Kas'yanov, V. A. Evstigneev. Grafy v programmirovanii: obrabotka, vizualizaciya i primenenie. SPb.: BHV-Peterburg, 2003. – 1104 s. [In Russian]
5. S. V. Kurapov, A. V. Tolok. The topological drawing of a graph: Construction methods // Autom. Remote Control. 2013. Vol. 74, Issue 9. – P. 1494–1509. [In Russian]
6. S. V. Kurapov, M. V. Davidovskii. Dva podhoda k provedeniyu soedinenij v ploskih konstruktivah. Komponenty i tekhnologii. 2015. № 7. S. 142–147; [In Russian]
7. S. V. Kurapov, M. V. Davidovskii. Topologicheskij podhod k provedeniyu soedinenij v ploskih konstruktivah. Komponenty i tekhnologii. 2015. № 11. S. 127–130; [In Russian]
8. S. V. Kurapov, M. V. Davidovskii. Proverka planarnosti i postroenie topologicheskogo risunka ploskogo grafa (poiskom v glubinu) // PDM. 2016. №2(32). S.100–115. [In Russian]
9. T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, et al. Cycle bases in graphs – characterization, algorithms, complexity, and applications // Comput. Sci. Rev. 2009. No.3. P.199–243.
10. M. Deza, V. Grishukhin, M. Shtogrin. Scale-Isometric Polytopal Graphs in Hypercubes and Cubic Lattices. Imperial College Press, 2004. – 175 p.
11. G. Ringel. Map Color Theorem. Repr. of the orig. 1st ed. (1974), Springer, 2011. – 212 p.
12. M. Patrignani. Planarity testing and embedding. Chapter 1. Handbook of Graph Drawing and Visualization. Roberto Tamassia, Editor. CRC Press. June 24, 2013. – P.1–42.
13. J. E. Hopcroft, R. E. Tarjan. Isomorphism of Planar Graphs // Complexity of Computer Computations / The IBM Research Symposia Series. – 1972. – P.131–152.
14. S. MacLane. A combinatorial condition for planar graphs // Fund. Math., 28. – 1937. – P. 22–32.
15. A.A Zykov. Teoriya konechnykh grafov [Theory of Finite Graphs]. Novosibirsk: Nauka, 1963. [In Russian]
16. M. N. S. Swamy, K. Thulasiraman. Graphs, networks, and algorithms. – J. Wiley & Sons, 1981.
17. Harary, F. Graph Theory, Reading: Addison-Wesley. – 1969.
18. E. Korach, Z. Ostfeld. DFS tree construction: Algorithms and characterizations // In: van Leeuwen J. (eds) Graph-Theoretic Concepts in Computer Science. WG 1988. Lecture Notes in Computer Science. – Vol 344. – Springer, Berlin, Heidelberg. – 1989.