Из Википедии, бесплатной энциклопедии
  (Перенаправлено из графика асимметрии )
Перейти к навигации Перейти к поиску

На графике рисунка , выравнивающий представляет собой способ расширения методов рисования из плоских графов к графикам, которые не являются плоскими, путем погружения неплоских график в пределах большего плоского графа. [1] [2]

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

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

Нахождение самого большого плоского подграфа [ править ]

Использование инкрементальной планаризации для рисования графа наиболее эффективно, когда на первом этапе процесса обнаруживается как можно больший планарный граф. К сожалению, поиск плоского подграфа с максимально возможным числом ребер ( проблема максимального плоского подграфа [3] ) является NP-трудным , а MaxSNP-трудным , подразумевая, что, вероятно, не существует алгоритма полиномиального времени , который решает проблему точно или что произвольно хорошо аппроксимирует его. [4]

В связном графе с n вершинами самый большой плоский подграф имеет не более 3 n  - 6 ребер, а любое остовное дерево образует плоский подграф с n  - 1 ребром. Таким образом, можно легко приблизить максимально плоский подграф в пределах коэффициента аппроксимации одной трети, просто путем нахождения остовного дерева. Известен лучший коэффициент аппроксимации 9/4, основанный на методе нахождения большого частичного 2-дерева как подграфа данного графа. [1] [4] В качестве альтернативы, если ожидается, что плоский подграф будет включать почти все ребра данного графа, оставив только небольшое число kнеплоских ребер для процесса инкрементальной планаризации, то можно точно решить проблему, используя управляемый алгоритм с фиксированными параметрами , время работы которого линейно по размеру графа, но неполиномиально по параметру  k . [5] Проблема также может быть решена точно с помощью алгоритма ветвей и отсечений , без каких-либо гарантий времени выполнения, но с хорошей производительностью на практике. [1] [6] Этот параметр k известен как асимметрия графа. [3] [7]

Также было проведено некоторое исследование родственной проблемы - нахождение наибольшего плоского индуцированного подграфа данного графа. Опять же, это NP-сложный, но управляемый с фиксированным параметром, когда все вершины, кроме нескольких, принадлежат индуцированному подграфу. [8] Эдвардс и Фарр (2002) доказали точную оценку 3 n / (Δ + 1) размера самого большого плоского индуцированного подграфа в зависимости от n , числа вершин в данном графе и Δ, его максимальная степень ; их доказательство приводит к полиномиальному алгоритму поиска индуцированного подграфа такого размера. [9]

Добавление ребер в планаризацию [ править ]

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

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

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

Ссылки [ править ]

  1. ^ a b c d e f g h я Буххайм, Кристоф; Чимани, Маркус; Гутвенгер, Карстен; Юнгер, Михаэль; Муцель, Петра (2014), «Пересечения и планаризация», в Тамассии, Роберто (редактор), Справочник по рисованию и визуализации графиков , дискретной математике и ее приложениям (Бока-Ратон), CRC Press, Бока-Ратон, Флорида.
  2. ^ a b c d Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков (1-е изд.), Прентис Холл, стр. 215–218, ISBN 0133016153.
  3. ^ a b Чимани, Маркус (2008), Вычисление чисел пересечения (PDF) , доктор философии. диссертация, Технический университет Дортмунда , раздел 4.3.1, архивировано из оригинала (PDF) 16 ноября 2015 г. .
  4. ^ a b Кэлинеску, Груя; Fernandes, Cristina G .; Финклер, Ульрих; Карлофф, Говард (1998), "Лучший алгоритм аппроксимации для нахождения плоских подграфов", журнал алгоритмов , 27 (2): 269-302, DOI : 10,1006 / jagm.1997.0920 , MR 1622397 .
  5. ^ Kawarabayashi, Кэнъити ; Рид, Брюс (2007), «Вычисление числа пересечений в линейном времени», Труды тридцать девятой ежегодной ACM симпозиум по теории вычислений (STOC '07) , С. 382-390,. DOI : 10,1145 / 1250790,1250848 , MR 2402463 .
  6. ^ Юнгер, М .; Mutzel, П. (1996), "Максимальные плоские подграфы и хорошие вложения: практические инструменты компоновки", Algorithmica , 16 (1): 33-59, DOI : 10.1007 / s004539900036 , МР 1394493 .
  7. Перейти ↑ Weisstein, Eric W. Graph Skewness . MathWorld .
  8. ^ Kawarabayashi, Кэнъити (2009) "Planarity позволяет несколько вершин ошибок в линейном времени", пятидесятый ежегодный симпозиум IEEE по Основы информатики ('09) FOCS (PDF) , стр 639-648,. DOI : 10.1109 / РПД .2009.45 , Руководство по ремонту 2648441  .
  9. ^ Эдвардс, Кейт; Фарр, Грэм (2002), "Алгоритм для поиска больших индуцированных плоских подграфов", Рисование графа: 9-й Международный симпозиум, GD 2001 г. Вена, Австрия, 23–26 сентября 2001 г., Revised Papers , Lecture Notes in Comp. Sci . , 2265 ., Спрингер, С. 75-80, DOI : 10.1007 / 3-540-45848-4_6 , МР 1962420 .
  10. ^ Гутвенгер, Карстен; Муцель, Петра ; Weiskircher, Рене (2005), "Вставка края в планарного графа", Algorithmica , 41 (4): 289-308, DOI : 10.1007 / s00453-004-1128-8 , МР 2122529 .