Теорема о плоском сепараторе

Любой планарный граф можно разделить, удалив несколько вершин.

В теории графов теорема о плоском разделителе является формой изопериметрического неравенства для планарных графов , которая гласит, что любой планарный граф можно разбить на меньшие части, удалив небольшое количество вершин . В частности, удаление вершин ${\displaystyle O({\sqrt {n}})}$ из n -вершинного графа (где O вызывает обозначение большого O ) может разбить граф на непересекающиеся подграфы, каждый из которых имеет не более вершин ${\displaystyle 2n/3}$ .

Более слабая форма теоремы о сепараторе с ⁠ ⁠ ${\displaystyle O({\sqrt {n}}\log ^{3/2}n)}$ вершинами в сепараторе вместо ⁠ ⁠ ${\displaystyle O({\sqrt {n}})}$ была первоначально доказана Унгаром (1951), а форма с жесткой асимптотической границей размера сепаратора была впервые доказана Липтоном и Тарьяном (1979). Со времени их работы теорема о сепараторе была передоказана несколькими различными способами, константа в члене ⁠ ⁠ ${\displaystyle O({\sqrt {n}})}$ теоремы была улучшена, и она была распространена на некоторые классы непланарных графов.

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

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

Формулировка теоремы

Как обычно утверждается, теорема о разделителе утверждает, что в любом -вершинном плоском графе существует разбиение вершин на три множества , , и , такое, что каждое из и имеет не более вершин, имеет вершины и нет ребер с одной конечной точкой в ​​и одной конечной точкой в ​​. Не требуется, чтобы или образовывали связные подграфы . называется разделителем для этого разбиения. ${\displaystyle n}$ ${\displaystyle G=(V,E)}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 2n/3}$ ${\displaystyle S}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle S}$

Эквивалентная формулировка заключается в том, что ребра любого -вершинного планарного графа могут быть подразделены на два подграфа, не пересекающихся по ребрам , и таким образом, что оба подграфа имеют по крайней мере вершины и таким образом, что пересечение множеств вершин двух подграфов имеет вершины в нем. Такое разбиение известно как разделение . ^[1] Если задано разделение, то пересечение множеств вершин образует разделитель, а вершины, которые принадлежат одному подграфу, но не другому, образуют разделенные подмножества, каждое из которых имеет не более вершин. В другом направлении, если задано разбиение на три множества , , и , которые удовлетворяют условиям теоремы о плоском разделителе, то можно образовать разделение, в котором ребра с конечной точкой в ​​принадлежат , ребра с конечной точкой в ​​принадлежат , а оставшиеся ребра (с обеими конечными точками в ) разделены произвольно. ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle n/3}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle 2n/3}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle G_{1}}$ ${\displaystyle B}$ ${\displaystyle G_{2}}$ ${\displaystyle S}$

Константа в формулировке теоремы о разделителе произвольна и может быть заменена любым другим числом в открытом интервале без изменения формы теоремы: разбиение на более равные подмножества может быть получено из менее равномерного разбиения путем многократного разбиения больших множеств в неравномерном разбиении и перегруппировки полученных связных компонентов. ^[2] ${\displaystyle 2/3}$ ${\displaystyle (1/2,1)}$

Пример

Плоский разделитель для сетки графика

Рассмотрим граф сетки со строками и столбцами; число вершин равно . Например, на иллюстрации, , и . Если нечетно, есть одна центральная строка, а в противном случае есть две строки, одинаково близкие к центру; аналогично, если нечетно, есть один центральный столбец, а в противном случае есть два столбца, одинаково близкие к центру. Выбор в качестве любой из этих центральных строк или столбцов и удаление из графа разбивает граф на два меньших связанных подграфа и , каждый из которых имеет не более вершин. Если (как на иллюстрации), то выбор центрального столбца даст разделитель с вершинами, и аналогично, если то выбор центральной строки даст разделитель с не более вершин. Таким образом, каждый граф сетки имеет разделитель размера не более , удаление которого разбивает его на два связанных компонента, каждый из которых имеет размер не более . ^[3] ${\displaystyle r}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle rc}$ ${\displaystyle r=5}$ ${\displaystyle c=8}$ ${\displaystyle n=rc=40}$ ${\displaystyle r}$ ${\displaystyle c}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n/2}$ ${\displaystyle r\leq c}$ ${\displaystyle S}$ ${\displaystyle r\leq {\sqrt {n}}}$ ${\displaystyle c\leq r}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle S}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n/2}$

Теорема о плоском сепараторе утверждает, что аналогичное разбиение может быть построено в любом плоском графе. Случай произвольных плоских графов отличается от случая решетчатых графов тем, что сепаратор имеет размер , но может быть больше, чем , ограничение на размер двух подмножеств и (в наиболее распространенных версиях теоремы) скорее, чем , и два подмножества и не обязательно сами по себе образуют связные подграфы. ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 2n/3}$ ${\displaystyle n/2}$ ${\displaystyle A}$ ${\displaystyle B}$

Конструкции

Расслоение по принципу «сначала в ширину»

Lipton & Tarjan (1979) дополняют заданный планарный граф дополнительными ребрами, если необходимо, так что он становится максимально планарным (каждая грань в планарном вложении является треугольником). Затем они выполняют поиск в ширину , корнем которого является произвольная вершина , и разбивают вершины на уровни по их расстоянию от . Если — медианный уровень (уровень, такой, что количество вершин на более высоком и более низком уровнях не превышает ), то должны быть уровни и , которые являются ступенями выше и ниже соответственно и которые содержат вершины соответственно, иначе на уровнях около было бы больше вершин, чем . Они показывают, что должен быть сепаратор, образованный объединением и , конечных точек ребра , которое не принадлежит дереву поиска в ширину и которое лежит между двумя уровнями, и вершин на двух путях дерева поиска в ширину от конечных точек обратно до уровня . Размер сепаратора, построенного таким образом, не превышает . Вершины разделителя и два непересекающихся подграфа можно найти за линейное время . ^[4] ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle l_{1}}$ ${\displaystyle n/2}$ ${\displaystyle l_{0}}$ ${\displaystyle l_{2}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle l_{1}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle n}$ ${\displaystyle l_{1}}$ ${\displaystyle S}$ ${\displaystyle l_{0}}$ ${\displaystyle l_{2}}$ ${\displaystyle e}$ ${\displaystyle G}$ ${\displaystyle e}$ ${\displaystyle l_{0}}$ ${\displaystyle S}$ ${\displaystyle {\sqrt {8n}}\approx 2.83{\sqrt {n}}}$

Это доказательство теоремы о разделителе применимо также к взвешенным планарным графам, в которых каждая вершина имеет неотрицательную стоимость. Граф можно разбить на три множества , , и таким образом, что и каждое имеет не более общей стоимости и имеет вершины, без ребер из и . ^[4] Анализируя подобную конструкцию разделителя более тщательно, Джиджев (1982) показывает, что ограничение на размер может быть уменьшено до . ^[2] ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 2/3}$ ${\displaystyle S}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$ ${\displaystyle {\sqrt {6n}}\approx 2.45{\sqrt {n}}}$

Хольцер и др. (2009) предлагают упрощенную версию этого подхода: они дополняют граф до максимальной планарности и строят дерево поиска в ширину, как и раньше. Затем для каждого ребра , которое не является частью дерева, они формируют цикл, объединяя его с путем дерева, который соединяет его конечные точки. Затем они используют в качестве разделителя вершины одного из этих циклов. Хотя этот подход не может гарантировать нахождение небольшого разделителя для планарных графов большого диаметра, их эксперименты показывают, что он превосходит методы наложения слоев в ширину Липтона–Тарьяна и Джиджева на многих типах планарных графов. ^[5] ${\displaystyle e}$ ${\displaystyle e}$

Простые разделители циклов

Для графа, который уже является максимально планарным, можно показать более сильную конструкцию простого разделителя циклов , цикла малой длины, такого, что внутренняя и внешняя части цикла (в уникальном планарном вложении графа) имеют не более вершин . Миллер (1986) доказывает это (с размером разделителя ), используя технику Липтона–Тарьяна для модифицированной версии поиска в ширину, в которой уровни поиска образуют простые циклы. ^[6] ${\displaystyle 2n/3}$ ${\displaystyle {\sqrt {8n}}}$

Alon, Seymour & Thomas (1994) доказывают существование простых разделителей циклов более напрямую: пусть будет циклом из не более чем вершин, с не более чем вершинами снаружи , который образует как можно более равномерное разбиение внутри и снаружи. Они показывают, что эти предположения вынуждают быть разделителем. В противном случае расстояния внутри должны быть равны расстояниям в диске, заключенном в (более короткий путь через внутреннюю часть диска будет образовывать часть границы лучшего цикла). Кроме того, должен иметь длину ровно , так как в противном случае его можно было бы улучшить, заменив одно из его ребер двумя другими сторонами треугольника. Если вершины в пронумерованы (по часовой стрелке) от до , и вершина сопоставлена ​​с вершиной , то эти сопоставленные пары могут быть соединены вершинно-непересекающимися путями внутри диска, по форме теоремы Менгера для планарных графов. Однако общая длина этих путей обязательно превысит , противоречие. Проделав некоторую дополнительную работу, они с помощью аналогичного метода показывают, что существует простой разделитель циклов размером не более . ^[7] ${\displaystyle C}$ ${\displaystyle {\sqrt {8n}}}$ ${\displaystyle 2n/3}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle {\sqrt {8n}}}$ ${\displaystyle C}$ ${\displaystyle 1}$ ${\displaystyle {\sqrt {8n}}}$ ${\displaystyle i}$ ${\displaystyle {\sqrt {8n}}-i+1}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {9n/2}}\approx 2.12{\sqrt {n}}}$

Джиджев и Венкатесан (1997) дополнительно улучшили постоянный множитель в теореме о простом разделителе циклов до . Их метод также может находить простые разделители циклов для графов с неотрицательными весами вершин, с размером разделителя не более , и может генерировать разделители с меньшим размером за счет более неравномерного разбиения графа. ^[8] В двусвязных планарных графах, которые не являются максимальными, существуют простые разделители циклов с размером, пропорциональным евклидовой норме вектора длин граней, которые могут быть найдены за почти линейное время. ^[9] ${\displaystyle 1.97{\sqrt {n}}}$ ${\displaystyle 2{\sqrt {n}}}$

Круговые разделители

Согласно теореме об упаковке кругов Кёбе–Андреева–Тёрстона , любой плоский граф может быть представлен упаковкой круговых дисков на плоскости с непересекающимися внутренностями, так что две вершины в графе являются смежными тогда и только тогда, когда соответствующая пара дисков взаимно касается друг друга. Как показывают Миллер и др. (1997), для такой упаковки существует круг, который имеет не более дисков, касающихся или находящихся внутри него, не более дисков, касающихся или находящихся вне его, и который пересекает диски. ^[10] ${\displaystyle 3n/4}$ ${\displaystyle 3n/4}$ ${\displaystyle O({\sqrt {n}})}$

Чтобы доказать это, Миллер и др. используют стереографическую проекцию для отображения упаковки на поверхность единичной сферы в трех измерениях. Тщательно выбирая проекцию, центр сферы можно сделать центральной точкой центров дисков на ее поверхности, так что любая плоскость, проходящая через центр сферы, разбивает ее на два полупространства, каждое из которых содержит или пересекает большинство дисков. Если плоскость, проходящая через центр, выбрана равномерно случайным образом, диск будет пересечен с вероятностью, пропорциональной его радиусу. Следовательно, ожидаемое количество пересекаемых дисков пропорционально сумме радиусов дисков. Однако сумма квадратов радиусов пропорциональна общей площади дисков, которая не превышает общей площади поверхности единичной сферы, константы. Аргумент, включающий неравенство Йенсена, показывает, что когда сумма квадратов неотрицательных действительных чисел ограничена константой, сумма самих чисел равна . Следовательно, ожидаемое число дисков, пересекаемых случайной плоскостью, равно и существует плоскость, которая пересекает не более этого числа дисков. Эта плоскость пересекает сферу по большому кругу , который проецируется обратно вниз на круг в плоскости с требуемыми свойствами. Диски, пересекаемые этим кругом, соответствуют вершинам планарного графового сепаратора, который отделяет вершины, диски которых находятся внутри круга, от вершин, диски которых находятся вне круга, с не более чем вершинами в каждом из этих двух подмножеств. ^[11] ${\displaystyle 3n/4}$ ${\displaystyle n}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle 3n/4}$

Этот метод приводит к рандомизированному алгоритму , который находит такой сепаратор за линейное время , ^[10] и менее практичному детерминированному алгоритму с той же линейной временной границей. ^[12] Тщательно анализируя этот алгоритм с использованием известных границ плотности упаковки упаковок кругов , можно показать, что он находит сепараторы размера не более ^[13] Хотя эта улучшенная граница размера сепаратора достигается за счет более неравномерного разбиения графа, Шпильман и Тенг (1996) утверждают, что она обеспечивает улучшенный постоянный фактор в границах времени для вложенного рассечения по сравнению с сепараторами Алона, Сеймура и Томаса (1990). Размер сепараторов, которые он производит, может быть дополнительно улучшен на практике с помощью неравномерного распределения для случайных плоскостей разрезания. ^[14] $${\displaystyle {\sqrt {\frac {2\pi }{\sqrt {3}}}}\left({\frac {1+{\sqrt {3}}}{2{\sqrt {2}}}}+o(1)\right){\sqrt {n}}\approx 1.84{\sqrt {n}}.}$$

Стереографическую проекцию в аргументе Миллера и др. можно избежать, если рассмотреть наименьший круг, содержащий постоянную долю центров дисков, а затем расширить его на константу, выбранную равномерно в диапазоне . Как и в случае Миллера и др., диски, пересекающие расширенный круг, образуют допустимый сепаратор, и в ожидании сепаратор имеет правильный размер. Полученные константы несколько хуже. ^[15] ${\displaystyle [1,2]}$

Спектральное разбиение

Методы спектральной кластеризации , в которых вершины графа группируются по координатам собственных векторов матриц, полученных из графа, долгое время использовались в качестве эвристики для задач разбиения графа для непланарных графов. ^[16] Как показывают Шпильман и Тенг (2007), спектральная кластеризация также может быть использована для вывода альтернативного доказательства для ослабленной формы теоремы о плоском сепараторе, которая применяется к плоским графам с ограниченной степенью. В их методе вершины заданного плоского графа сортируются по вторым координатам собственных векторов матрицы Лапласа графа , и этот отсортированный порядок разбивается в точке, которая минимизирует отношение числа ребер, разрезаемых разбиением, к числу вершин на меньшей стороне разбиения. Как они показывают, каждый плоский граф ограниченной степени имеет разбиение этого типа, в котором отношение равно . Хотя это разделение может быть не сбалансированным, повторение раздела в пределах большей из двух сторон и взятие объединения разрезов, образованных при каждом повторении, в конечном итоге приведет к сбалансированному разделению с краями. Конечные точки этих краев образуют сепаратор размером . ^[17] ${\displaystyle O(1/{\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Разделители краев

Разновидность теоремы о плоском сепараторе включает в себя разделители ребер , небольшие наборы ребер, образующие разрез между двумя подмножествами и вершинами графа. Два множества и должны иметь размер не более постоянной доли числа вершин графа (обычно оба множества имеют размер не более ), и каждая вершина графа принадлежит ровно одному из и . Разделитель состоит из ребер, которые имеют одну конечную точку в и одну конечную точку в . Границы размера разделителя ребер включают степень вершин , а также количество вершин в графе: планарные графы, в которых одна вершина имеет степень , включая графы-колеса и графы-звезды , не имеют разделителя ребер с сублинейным числом ребер, потому что любой разделитель ребер должен был бы включать все ребра, соединяющие вершину высокой степени с вершинами на другой стороне разреза. Однако каждый планарный граф с максимальной степенью имеет разделитель ребер размера . ^[18] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle 2n/3}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n-1}$ ${\displaystyle \Delta }$ ${\displaystyle O({\sqrt {\Delta n}})}$

Простой разделитель циклов в двойственном графе планарного графа образует разделитель ребер в исходном графе. ^[19] Применение теоремы о простом разделителе циклов Газита и Миллера (1990) к двойственному графу заданного планарного графа усиливает границу для размера разделителя ребер, показывая, что каждый планарный граф имеет разделитель ребер, размер которого пропорционален евклидовой норме его вектора степеней вершин. ${\displaystyle O({\sqrt {\Delta n}})}$

Papadimitriou & Sideri (1996) описывают алгоритм полиномиального времени для поиска наименьшего разделителя ребер, который разбивает граф на два подграфа одинакового размера, когда является индуцированным подграфом графа сетки без отверстий или с постоянным числом отверстий. Однако они предполагают, что задача является NP-полной для произвольных планарных графов, и показывают, что сложность задачи одинакова для графов сетки с произвольным числом отверстий, как и для произвольных планарных графов. ${\displaystyle G}$ ${\displaystyle G}$

Нижние границы

Многогранник, образованный заменой каждой из граней икосаэдра сеткой из 100 треугольников, пример построения нижней границы Джиджева (1982)

В графе сетки набор точек может охватывать подмножество не более чем точек сетки, где максимум достигается путем расположения в диагональной линии около угла сетки. Поэтому, чтобы сформировать сепаратор, который отделяет по крайней мере из точек от остальной сетки, должно быть не менее . ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ ${\displaystyle S}$ ${\displaystyle s<{\sqrt {n}}}$ ${\displaystyle s(s-1)/2}$ ${\displaystyle S}$ ${\displaystyle n/3}$ ${\displaystyle s}$ ${\displaystyle {\sqrt {2n/3}}\approx 0.82{\sqrt {n}}}$

Существуют -вершинные планарные графы (для произвольно больших значений ), такие, что для каждого сепаратора , который разбивает оставшийся граф на подграфы с не более чем вершинами, имеется не менее . ^[2] Построение включает в себя аппроксимацию сферы выпуклым многогранником , замену каждой из граней многогранника треугольной сеткой и применение изопериметрических теорем для поверхности сферы. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle 2n/3}$ ${\displaystyle S}$ ${\displaystyle {\sqrt {4\pi n/{\sqrt {27}}}}\approx 1.56{\sqrt {n}}}$

Иерархии разделителей

Разделители могут быть объединены в иерархию разделителей планарного графа, рекурсивное разложение на меньшие графы. Иерархия разделителей может быть представлена ​​бинарным деревом , в котором корневой узел представляет сам данный граф, а два дочерних элемента корня являются корнями рекурсивно построенных иерархий разделителей для индуцированных подграфов, образованных из двух подмножеств и разделителя. ${\displaystyle A}$ ${\displaystyle B}$

Иерархия сепараторов такого типа образует основу для древовидной декомпозиции данного графа, в которой набор вершин, связанных с каждым узлом дерева, является объединением сепараторов на пути от этого узла к корню дерева. Поскольку размеры графов уменьшаются на постоянный множитель на каждом уровне дерева, верхние границы размеров сепараторов также уменьшаются на постоянный множитель на каждом уровне, поэтому размеры сепараторов на этих путях складываются в геометрической прогрессии с . То есть сепаратор, сформированный таким образом, имеет ширину , и его можно использовать для демонстрации того, что каждый плоский граф имеет древовидную ширину . ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Построение иерархии сепаратора напрямую, путем обхода бинарного дерева сверху вниз и применения линейно-временного алгоритма планарного сепаратора к каждому из индуцированных подграфов, связанных с каждым узлом бинарного дерева, заняло бы в общей сложности время. Однако возможно построить всю иерархию сепаратора за линейное время, используя подход Липтона-Тарьяна к наслаиванию в ширину и используя соответствующие структуры данных для выполнения каждого шага разбиения за сублинейное время. ^[20] ${\displaystyle O(n\log n)}$

Если сформировать связанный тип иерархии, основанный на разделениях вместо сепараторов, в котором два потомка корневого узла являются корнями рекурсивно построенных иерархий для двух подграфов и разделения данного графа, то общая структура образует разложение ветвей вместо разложения дерева. Ширина любого разделения в этом разложении, опять же, ограничена суммой размеров сепараторов на пути от любого узла к корню иерархии, поэтому любое разложение ветвей, сформированное таким образом, имеет ширину , а любой планарный граф имеет ширину ветви . Хотя многие другие связанные задачи разбиения графа являются NP-полными , даже для планарных графов можно найти разложение ветвей минимальной ширины планарного графа за полиномиальное время. ^[21] ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Применяя методы Алона, Сеймура и Томаса (1994) более непосредственно при построении разложений ветвей, Фомин и Тиликос (2006a) показывают, что каждый планарный граф имеет ширину ветвей не более , с той же константой, что и в теореме о простом разделителе циклов Алона и др. Поскольку древесная ширина любого графа не превышает его ширины ветвей, это также показывает, что планарные графы имеют древесную ширину не более . ${\displaystyle 2.12{\sqrt {n}}}$ ${\displaystyle 3/2}$ ${\displaystyle 3.18{\sqrt {n}}}$

Другие классы графов

Некоторые разреженные графы не имеют разделителей сублинейного размера: в графе-расширителе удаление до постоянной доли вершин все еще оставляет только один связный компонент. ^[22]

Возможно, самая ранняя известная теорема о разделителе является результатом Джордана (1869), согласно которому любое дерево можно разбить на поддеревья с не более чем вершинами каждое путем удаления одной вершины. ^[10] В частности, вершина, которая минимизирует максимальный размер компонента, обладает этим свойством, поскольку если бы она этого не делала, то ее сосед в уникальном большом поддереве образовал бы еще лучшее разбиение. Применяя ту же технику к древовидной декомпозиции произвольного графа, можно показать, что любой граф имеет разделитель размера, не превышающего его древовидную ширину . ${\displaystyle n/2}$

Если граф не является планарным, но может быть вложен в поверхность рода , то он имеет сепаратор с вершинами. Гилберт, Хатчинсон и Тарьян (1984) доказывают это, используя аналогичный подход Липтона и Тарьяна (1979). Они группируют вершины графа в уровни поиска в ширину и находят два уровня, удаление которых оставляет не более одного большого компонента, состоящего из небольшого числа уровней. Этот оставшийся компонент можно сделать планарным, удалив некоторое число путей поиска в ширину, пропорциональное роду, после чего метод Липтона–Тарьян может быть применен к оставшемуся планарному графу. Результат следует из тщательного балансирования размера удаленных двух уровней против числа уровней между ними. Если вложение графа задано как часть входных данных, его сепаратор можно найти за линейное время . Графы рода также имеют сепараторы ребер размера . ^[23] ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle O({\sqrt {gn}})}$ ${\displaystyle g}$ ${\displaystyle O({\sqrt {g\Delta n}})}$

Графы ограниченного рода образуют пример семейства графов, замкнутых относительно операции взятия миноров , и теоремы о сепараторе также применимы к произвольным замкнутым на миноры семействам графов. В частности, если семейство графов имеет запрещенный минор с вершинами, то оно имеет сепаратор с вершинами, и такой сепаратор может быть найден за время для любого . ^[24] ${\displaystyle h}$ ${\displaystyle O(h{\sqrt {n}})}$ ${\displaystyle O(n^{1+\varepsilon })}$ ${\displaystyle \varepsilon >0}$

Граф пересечений дисков, в котором не более дисков покрывают любую точку плоскости. ${\displaystyle k=5}$

Метод сепаратора окружности Миллера и др. (1997) обобщается на графы пересечений любой системы -мерных шаров со свойством, что любая точка в пространстве покрыта не более чем некоторым постоянным числом шаров, на -графы ближайших соседей в размерностях, ^[10] и на графы, возникающие из сеток конечных элементов . ^[25] Сепараторы сфер, построенные таким образом, разбивают входной граф на подграфы с не более чем вершинами. Размер сепараторов для -слойных графов пересечений шаров и для -графов ближайших соседей равен . ^[10] ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle n(d+1)/(d+2)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(k^{1/d}n^{1-1/d})}$

Если наследственное семейство графов имеет теорему о сепараторе с сепараторами размера , для некоторых , то оно обязательно имеет полиномиальное расширение , полиномиальную границу плотности его мелких миноров . Наоборот, графы с полиномиальным расширением имеют теоремы о сублинейных сепараторах. ^[26] ${\displaystyle n^{c}}$ ${\displaystyle c<1}$

Приложения

Алгоритмы «разделяй и властвуй»

Разделительные разложения могут быть полезны при разработке эффективных алгоритмов «разделяй и властвуй» для решения задач на планарных графах. Например, одна из задач, которая может быть решена таким образом, — это поиск кратчайшего цикла во взвешенном планарном орграфе. Это можно решить с помощью следующих шагов:

• Разобьем заданный граф на три подмножества , , согласно теореме о плоском разделителе ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$
• Рекурсивный поиск самых коротких циклов в и ${\displaystyle A}$ ${\displaystyle B}$
• Используйте алгоритм Дейкстры , чтобы найти для каждой вершины в кратчайший цикл через в . ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle G}$
• Верните самый короткий из циклов, найденных с помощью описанных выше шагов.

Время двух рекурсивных вызовов и в этом алгоритме определяется временем выполнения вызовов алгоритма Дейкстры, поэтому этот алгоритм находит самый короткий цикл по времени. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n^{3/2}\log n)}$

Более быстрый алгоритм для той же задачи на кратчайший цикл, работающий за время , был предложен Вульфом-Нильсеном (2009). Его алгоритм использует ту же структуру «разделяй и властвуй» на основе сепаратора, но использует простые сепараторы циклов вместо произвольных сепараторов, так что вершины принадлежат одной грани графов внутри и снаружи сепаратора циклов. Затем он заменяет отдельные вызовы алгоритма Дейкстры более сложными алгоритмами для поиска кратчайших путей из всех вершин на одной грани планарного графа и объединения расстояний от двух подграфов. Для взвешенных, но неориентированных планарных графов кратчайший цикл эквивалентен минимальному разрезу в двойственном графе и может быть найден за время ^[27] , а кратчайший цикл в невзвешенном неориентированном планарном графе (его обхват ) может быть найден за время [ ^28] (Однако более быстрый алгоритм для невзвешенных графов не основан на теореме о сепараторе.) ${\displaystyle O(n\log ^{3}n)}$ ${\displaystyle S}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n\log \log n)}$ ${\displaystyle O(n)}$

Фредериксон предложил другой более быстрый алгоритм для кратчайших путей из одного источника, реализуя теорему о разделителе в планарных графах. ^[29] Это улучшение алгоритма Дейкстры с итеративным поиском на тщательно выбранном подмножестве вершин. Эта версия занимает время в -вершинном графе. Разделители используются для нахождения разделения графа, то есть разбиения множества ребер на два или более подмножеств, называемых областями. Говорят, что узел содержится в области, если некоторое ребро области инцидентно узлу. Узел, содержащийся более чем в одной области, называется граничным узлом областей, содержащих его. Метод использует понятие -разделения -узлового графа, которое является разделением графа на области, каждая из которых содержит узлы, включая граничные узлы. Фредериксон показал, что -разделение может быть найдено со временем с помощью рекурсивного применения теоремы о разделителе. ${\displaystyle O(n{\sqrt {\log n}})}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle O(n/r)}$ ${\displaystyle O(r)}$ ${\displaystyle O({\sqrt {r}})}$ ${\displaystyle r}$ ${\displaystyle O(n\log n)}$

Схема его алгоритма решения задачи выглядит следующим образом.

1. Фаза предварительной обработки: Разбить граф на тщательно выбранные подмножества вершин и определить кратчайшие пути между всеми парами вершин в этих подмножествах, где промежуточные вершины на этом пути не находятся в подмножестве. Эта фаза требует преобразования планарного графа в , в котором ни одна вершина не имеет степени больше трех. Из следствия формулы Эйлера количество вершин в полученном графе будет равно , где — количество вершин в . Эта фаза также обеспечивает следующие свойства подходящего -разделения. Подходящее -разделение планарного графа — это -разделение такое, что, ${\displaystyle G_{0}}$ ${\displaystyle G}$ ${\displaystyle n\leq 6n_{0}-12}$ ${\displaystyle n_{0}}$ ${\displaystyle G_{0}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r}$
   • каждая граничная вершина содержится не более чем в трех областях, и
   • любая несвязанная область состоит из связанных компонентов, все из которых имеют общие граничные вершины с одним и тем же набором из одной или двух связанных областей.
2. Фаза поиска:
   • Основная задача: найти кратчайшие расстояния от источника до каждой вершины в подмножестве. Когда вершина в подмножестве закрыта, предварительное расстояние должно быть обновлено для всех вершин в подмножестве таким образом, чтобы существовал путь от до . ${\displaystyle v}$ ${\displaystyle d(w)}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$
   • Зачистка: определение кратчайших расстояний до каждой оставшейся вершины.

Хензингер и др. расширили технику -деления Фредериксона для алгоритма кратчайшего пути из одного источника в планарных графах для неотрицательных длин ребер и предложили алгоритм линейного времени . ^[30] Их метод обобщает понятие -деления Фредериксона таким образом, что теперь -деление -узлового графа является делением на регионы, каждый из которых содержит узлы, каждый из которых имеет не более граничных узлов. Если -деление многократно делится на меньшие регионы, это называется рекурсивным делением. Этот алгоритм использует приблизительно уровни делений, где обозначает функцию итерированного логарифма . Рекурсивное деление представлено корневым деревом , листья которого помечены различными ребрами . Корень дерева представляет регион, состоящий из всех , дочерние элементы корня представляют подрегионы, на которые разделен этот регион и так далее. Каждый лист (атомарный регион) представляет регион, содержащий ровно одно ребро. ${\displaystyle r}$ ${\displaystyle (r,s)}$ ${\displaystyle n}$ ${\displaystyle O(n/r)}$ ${\displaystyle r^{O(1)}}$ ${\displaystyle s}$ ${\displaystyle (r,s)}$ ${\displaystyle \log ^{*}n}$ ${\displaystyle \log ^{*}}$ ${\displaystyle G}$ ${\displaystyle G}$

Вложенное рассечение — это основанная на сепараторе вариация метода гауссовского исключения «разделяй и властвуй» для решения разреженных симметричных систем линейных уравнений с планарной структурой графа, например, тех, которые возникают из метода конечных элементов . Он включает в себя поиск сепаратора для графа, описывающего систему уравнений, рекурсивное исключение переменных в двух подзадачах, отделенных друг от друга сепаратором, а затем исключение переменных в сепараторе. ^[31] Заполнение этого метода (количество ненулевых коэффициентов результирующего разложения Холецкого матрицы) равно , ^[32] что позволяет этому методу конкурировать с итеративными методами для тех же задач. ^[31] ${\displaystyle O(n\log n)}$

Кляйн, Мозес и Вайман ^[33] предложили -временной алгоритм линейного пространства для поиска кратчайших расстояний пути от исходной вершины до всех других вершин для направленного планарного графа с положительными и отрицательными длинами дуг, не содержащего отрицательных циклов. Их алгоритм использует планарные разделители графа для поиска жордановой кривой , которая проходит через узлы (и не содержит дуг) таким образом, что между и узлами заключены . Узлы, через которые проходит , являются граничными узлами. Исходный граф разделяется на два подграфа и путем разрезания планарного вложения вдоль и дублирования граничных узлов. Граничные узлы в каждом графе лежат на границе одной грани . ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle s}$ ${\displaystyle C}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle n/3}$ ${\displaystyle 2n/3}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle G}$ ${\displaystyle G_{0}}$ ${\displaystyle G_{1}}$ ${\displaystyle C}$ ${\displaystyle G_{i}}$ ${\displaystyle F_{i}}$

Обзор их подхода представлен ниже.

• Рекурсивный вызов: на первом этапе рекурсивно вычисляются расстояния внутри каждого графа . ${\displaystyle r}$ ${\displaystyle G_{i}}$
• Внутричастные граничные расстояния: Для каждого графа вычислить все расстояния между граничными узлами. Это занимает время. ${\displaystyle G_{i}}$ ${\displaystyle G_{i}}$ ${\displaystyle O(n\log n)}$
• Граничные расстояния между частями с одним источником: кратчайший путь в проходит туда и обратно между и для вычисления расстояний в от до всех граничных узлов. Чередующиеся итерации используют все-граничные-расстояния в и . Количество итераций равно , а общее время для этого этапа равно , где — обратная функция Аккермана . ${\displaystyle G}$ ${\displaystyle G_{0}}$ ${\displaystyle G_{1}}$ ${\displaystyle G}$ ${\displaystyle r}$ ${\displaystyle G_{0}}$ ${\displaystyle G_{1}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n\alpha (n))}$ ${\displaystyle \alpha (n)}$
• Расстояния между частями с одним источником: Расстояния, вычисленные на предыдущих этапах, используются вместе с вычислением Дейкстры в модифицированной версии каждого G _i  для вычисления расстояний от до всех узлов. Этот этап занимает время. ${\displaystyle G}$ ${\displaystyle r}$ ${\displaystyle O(n\log n)}$
• Переустановка расстояний с одним источником: расстояния от в преобразуются в неотрицательные длины, и снова алгоритм Дейкстры используется для вычисления расстояний от . Этот этап требует времени. ${\displaystyle r}$ ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle O(n\log n)}$

Важной частью этого алгоритма является использование функций цены и сокращенных длин. Для направленного графа с длинами дуг функция цены — это функция от узлов до действительных чисел . Для дуги сокращенная длина относительно равна . Допустимая функция цены — это функция цены, которая индуцирует неотрицательные сокращенные длины на всех дугах . Она полезна для преобразования задачи о кратчайшем пути, включающей положительные и отрицательные длины, в задачу, включающую только неотрицательные длины, которую затем можно решить с помощью алгоритма Дейкстры. ${\displaystyle G}$ ${\displaystyle \ell (uv)}$ ${\displaystyle \varphi }$ ${\displaystyle G}$ ${\displaystyle uv}$ ${\displaystyle \varphi }$ ${\displaystyle \ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)}$ ${\displaystyle G}$

Парадигма «разделяй и властвуй», основанная на разделителе, также использовалась для проектирования структур данных для динамических алгоритмов графа ^[34] и алгоритмов определения местоположения точки , ^[35] для триангуляции полигонов , ^[20] кратчайших путей , ^[36] и построения графов ближайших соседей , ^[37] и алгоритмов аппроксимации для максимального независимого множества планарного графа. ^[35]

Точное решение NP-трудных задач оптимизации

Используя динамическое программирование на древовидной декомпозиции или ветвящейся декомпозиции планарного графа, многие NP-трудные задачи оптимизации могут быть решены за время, экспоненциальное за или . Например, границы этой формы известны для поиска максимальных независимых множеств , деревьев Штейнера и гамильтоновых циклов , а также для решения задачи коммивояжера на планарных графах. ^[38] Аналогичные методы, включающие теоремы о разделителе для геометрических графов, могут быть использованы для решения евклидовой задачи коммивояжера и задач построения дерева Штейнера за время той же формы. ^[39] ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}\log n}$

Для параметризованных задач, допускающих кернелизацию , которая сохраняет планарность и сводит входной граф к ядру размера, линейного по входному параметру, этот подход может быть использован для разработки фиксированно-параметрических трактуемых алгоритмов, время выполнения которых зависит полиномиально от размера входного графа и экспоненциально от , где — параметр алгоритма. Например, временные ограничения этой формы известны для поиска вершинных покрытий и доминирующих множеств размера . ^[40] ${\displaystyle {\sqrt {k}}}$ ${\displaystyle k}$ ${\displaystyle k}$

Алгоритмы аппроксимации

Липтон и Тарьян (1980) заметили, что теорема о разделителе может быть использована для получения схем аппроксимации полиномиального времени для NP-трудных задач оптимизации на планарных графах, таких как поиск максимального независимого множества . В частности, путем усечения иерархии разделителя на соответствующем уровне можно найти разделитель размера, удаление которого разбивает граф на подграфы размера не более , для любой константы . По теореме о четырех цветах существует независимое множество размера не менее , поэтому удаленные узлы образуют пренебрежимо малую долю максимального независимого множества, а максимальные независимые множества в оставшихся подграфах могут быть найдены независимо за время, экспоненциально зависящее от их размера. Объединив этот подход с более поздними методами линейного времени для построения иерархии разделителя ^[20] и с табличным поиском для разделения вычисления независимых множеств между изоморфными подграфами, можно построить независимые множества размера в пределах от оптимального, за линейное время. Однако для коэффициентов аппроксимации , даже более близких к единице, чем этот коэффициент, более поздний подход Бейкера (1994) (основанный на древовидной декомпозиции, а не на плоских сепараторах) обеспечивает лучшие компромиссы между временем и качеством аппроксимации. ${\displaystyle O(n/{\sqrt {\log n}})}$ ${\displaystyle c\log n}$ ${\displaystyle c}$ ${\displaystyle n/4}$ ${\displaystyle 1-1/{\sqrt {\log n}}}$

Аналогичные схемы аппроксимации на основе сепараторов также использовались для аппроксимации других сложных задач, таких как покрытие вершин . ^[41] Арора и др. (1998) используют сепараторы другим способом для аппроксимации задачи коммивояжера для метрики кратчайшего пути на взвешенных планарных графах; их алгоритм использует динамическое программирование для поиска кратчайшего тура, который на каждом уровне иерархии сепараторов пересекает сепаратор ограниченное число раз, и они показывают, что по мере увеличения границы пересечения туры, построенные таким образом, имеют длину, которая приближается к оптимальному туру.

Сжатие графиков

Разделители использовались как часть алгоритмов сжатия данных для представления планарных графов и других разделимых графов с использованием небольшого числа бит. Основной принцип этих алгоритмов заключается в выборе числа и многократном подразделении заданного планарного графа с использованием разделителей на подграфы размером не более , с вершинами в разделителях. При соответствующем выборе (не более пропорциональном логарифму ) количество неизоморфных -вершинных планарных подграфов значительно меньше количества подграфов в разложении, поэтому граф можно сжать, построив таблицу всех возможных неизоморфных подграфов и представив каждый подграф в разложении разделителя его индексом в таблице. Оставшаяся часть графа, образованная вершинами разделителя, может быть представлена ​​явно или с использованием рекурсивной версии той же структуры данных. Используя этот метод, планарные графы и многие другие ограниченные семейства графов могут быть закодированы с использованием числа битов, которое является оптимальным с точки зрения информации : если в семействе графов, которые необходимо представить, есть -вершинные графы, то отдельный граф в семействе может быть представлен с использованием только битов. ^[42] Также возможно построить представления этого типа, в которых можно проверить смежность между вершинами, определить степень вершины и составить список соседей вершин за постоянное время на запрос, дополнив таблицу подграфов дополнительной табличной информацией, представляющей ответы на запросы. ^[43] ${\displaystyle k}$ ${\displaystyle O(n/k)}$ ${\displaystyle k}$ ${\displaystyle O(n/{\sqrt {k}})}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle P_{n}}$ ${\displaystyle n}$ ${\displaystyle (1+o(1))\log _{2}P_{n}}$

Универсальные графики

Универсальный граф для семейства графов — это граф, который содержит каждый элемент в качестве подграфа. Разделители могут быть использованы для того, чтобы показать, что -вершинные планарные графы имеют универсальные графы с вершинами и ребрами. ^[44] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle O(n^{3/2})}$

Конструкция включает в себя усиленную форму теоремы о разделителе, в которой размер трех подмножеств вершин в разделителе не зависит от структуры графа: существует число , величина которого не превышает константу, умноженную на , такое, что вершины каждого -вершинного планарного графа могут быть разделены на подмножества , и , без ребер из в , с и с . Это можно показать, используя обычную форму теоремы о разделителе многократно для разбиения графа до тех пор, пока все компоненты разбиения не будут организованы в два подмножества с меньшим числом вершин, а затем перемещая вершины из этих подмножеств в разделитель по мере необходимости, пока он не достигнет заданного размера. ${\displaystyle c}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |S|=c}$ ${\displaystyle |A|=|B|=(n-c)/2}$ ${\displaystyle n/2}$

Как только теорема о разделителе такого типа показана, ее можно использовать для создания иерархии разделителей для -вершинных планарных графов, которая снова не зависит от структуры графа: древовидная декомпозиция, образованная из этой иерархии, имеет ширину и может быть использована для любого планарного графа. Множество всех пар вершин в этой древовидной декомпозиции, которые обе принадлежат общему узлу древовидной декомпозиции, образует тривиально совершенный граф с вершинами, который содержит каждый -вершинный планарный граф в качестве подграфа. Подобная конструкция показывает, что планарные графы ограниченной степени имеют универсальные графы с ребрами, где константа, скрытая в обозначении O, зависит от границы степени. Любой универсальный граф для планарных графов (или даже для деревьев неограниченной степени) должен иметь ребра. ^[44] ${\displaystyle n}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n^{3/2})}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle \Omega (n\log n)}$

Эспере, Жоре и Морен (2020) заявили, что конструкцию с использованием сепараторов можно улучшить до . ${\displaystyle O(n^{3/2})}$ ${\displaystyle n^{1+o(1)}}$

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

• Разделитель вершин
• Геометрический разделитель

Примечания

1. Алон, Сеймур и Томас (1990).
2. Джиджев (1982).
3. Джордж (1973). Вместо того, чтобы использовать строку или столбец сетки графика, Джордж разбивает график на четыре части, используя объединение строки и столбца в качестве разделителя.
4. Липтон и Тарьян (1979).
5. Хольцер и др. (2009).
6. Миллер (1986).
7. Алон, Сеймур и Томас (1994).
8. Джиджев и Венкатесан (1997).
9. Газит и Миллер (1990).
10. Миллер и др. (1997).
11. Миллер и др. (1997); Пах и Агарвал (1995)
12. Эппштейн, Миллер и Тенг (1995).
13. Спилман и Тенг (1996).
14. Грембан, Миллер и Тенг (1997).
15. Хар-Пелед (2011).
16. Донат и Хоффман (1972); Фидлер (1973).
17. Спилман и Тенг (2007).
18. Миллер (1986) доказал этот результат для 2-связных планарных графов, а Дикс и др. (1993) распространили его на все планарные графы.
19. Миллер (1986); Газит и Миллер (1990).
20. Goodrich (1995).
21. Сеймур и Томас (1994).
22. Липтон и Тарьян (1979); Эрдеш, Грэм и Семереди (1976).
23. Сикора и Врт'о (1993).
24. Каварабаяси и Рид (2010). Более ранние работы по разделителям в семьях с малым числом членов см. в Alon, Seymour и Thomas (1990), Plotkin, Rao и Smith (1994) и Reed и Wood (2009).
25. Миллер и др. (1998).
26. Дворжак и Норин (2016).
27. Лонцкий и Санковский (2011).
28. Чанг и Лу (2011).
29. Фредериксон (1987).
30. Хензингер и др. (1997).
31. Джордж (1973).
32. Липтон, Роуз и Тарьян (1979); Гилберт и Тарьян (1986).
33. Кляйн, Мозес и Вейманн (2010).
34. Эппштейн и др. (1996); Эппштейн и др. (1998).
35. Липтон и Тарьян (1980).
36. Кляйн и др. (1994); Тазари и Мюллер-Ханнеманн (2009).
37. Фриз, Миллер и Тенг (1992).
38. Берн (1990); Дейнеко, Клинц и Вегингер (2006); Дорн и др. (2005); Липтон и Тарьян (1980).
39. Смит и Вормолд (1998).
40. Альбер, Фернау и Нидермайер (2003); Фомин и Тиликос (2006б).
41. Бар-Иегуда и Эвен (1982); Тиба, Нисидзеки и Сайто (1981).
42. Хэ, Као и Лу (2000).
43. Бландфорд, Блеллох и Кэш (2003); Беллох и Фарзан (2010).
44. Бабай и др. (1982); Бхатт и др. (1989); Чанг (1990).

Ссылки

• Альбер, Йохен; Фернау, Хеннинг; Нидермейер, Рольф (2003), «Разделители графов: параметризованное представление», Журнал компьютерных и системных наук , 67 (4): 808–832, doi :10.1016/S0022-0000(03)00072-2
• Алон, Нога ; Сеймур, Пол ; Томас, Робин (1990), «Теорема о разделителе для непланарных графов», Журнал Американского математического общества , 3 (4): 801–808, doi : 10.1090/S0894-0347-1990-1065053-0
• Алон, Нога ; Сеймур, Пол ; Томас, Робин (1994), «Планарные сепараторы», SIAM Journal on Discrete Mathematics , 7 (2): 184–193, doi :10.1137/S0895480191198768
• Арора, Санджив ; Гриньи, Микеланджело; Каргер, Дэвид; Кляйн, Филипп; Волошин, Анджей (1998), «Схема аппроксимации полиномиального времени для взвешенного планарного графа TSP», Труды 9-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA '98), стр. 33–41, ISBN 9780898714104
• Бабай, Л .; Чунг, Ф. Р. К .; Эрдёш, П.; Грэхем , Р. Л .; Спенсер, Дж. Х. (1982), «О графах, содержащих все разреженные графы», в Rosa, Alexander; Sabidussi, Gert ; Turgeon, Jean (ред.), Теория и практика комбинаторики: сборник статей, посвященных Антону Коцигу по случаю его шестидесятилетия (PDF) , Annals of Discrete Mathematics, т. 12, стр. 21–26
• Бейкер, Бренда С. (1994), «Аппроксимационные алгоритмы для NP-полных задач на планарных графах», Журнал ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID  9706753
• Бар-Йехуда, Р.; Эвен, С. (1982), «Об аппроксимации вершинного покрытия для планарных графов», Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 , стр. 303–309, doi : 10.1145/800070.802205 , ISBN 0-89791-070-2, S2CID  2820550{{citation}}: CS1 maint: date and year (link)
• Берн, Маршалл (1990), «Более быстрые точные алгоритмы для деревьев Штейнера в плоских сетях», Networks , 20 (1): 109–120, doi :10.1002/net.3230200110
• Бхатт, Сандип Н.; Чунг, Фань Р.К .; Лейтон, Ф.Т.; Розенберг , Арнольд Л. (1989), «Универсальные графы для деревьев ограниченной степени и планарных графов» (PDF) , SIAM Journal on Discrete Mathematics , 2 (2): 145, doi :10.1137/0402014
• Блэндфорд, Дэниел К.; Блеллох, Гай Э.; Кэш, Ян А. (2003), «Компактные представления разделимых графов», Труды 14-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA '03) (PDF) , стр. 679–688
• Blelloch, Guy E.; Farzan, Arash (2010), "Краткие представления разделимых графов", в Amir, Amihood; Parida, Laxmi (ред.), Proc. 21st Symposium on Combinatory Pattern Matching , Lecture Notes in Computer Science, т. 6129, Springer-Verlag, стр. 138–150, Bibcode : 2010LNCS.6129..138B, CiteSeerX  10.1.1.307.6710 , doi : 10.1007/978-3-642-13509-5_13, ISBN 978-3-642-13508-8
• Чалермсук, Паринья; Факчароенпхол, Джиттат; Нанонгкай, Данупон (2004), «Детерминированный алгоритм почти линейного времени для поиска минимальных разрезов в планарных графах», Труды 15-го симпозиума ACM–SIAM по дискретным алгоритмам (SODA'04), стр. 828–829
• Чанг, Сянь-Чи; Лу, Сюэ-И (2011), «Вычисление обхвата планарного графа за линейное время», SIAM Journal on Computing , 42 (3): 1077–1094, arXiv : 1104.4892 , doi : 10.1137/110832033, S2CID  2493979
• Чиба, Норисигэ; Нисидзеки, Такао ; Сайто, Нобудзи (1981), «Применение теоремы Липтона и Тарьяна о плоском сепараторе» (PDF) , Журнал обработки информации , 4 (4): 203–207
• Chung, Fan RK (1990), «Теоремы о разделителе и их приложения», в Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; et al. (ред.), Paths, Flows, and VLSI-Layout, Algorithms and Combinatorics, т. 9, Springer-Verlag, стр. 17–34, ISBN 978-0-387-52685-0
• Дейнеко, Владимир Г.; Клинц, Беттина; Вёгингер, Герхард Й. (2006), «Точные алгоритмы для задачи о гамильтоновом цикле в планарных графах», Operations Research Letters , 34 (3): 269–274, doi :10.1016/j.orl.2005.04.013
• Дикс, К.; Джиджев, Х.Н.; Сикора, О.; Врт'о, И. (1993), «Реберные разделители плоских и внешнепланарных графов с приложениями», Журнал алгоритмов , 14 (2): 258–279, doi : 10.1006/jagm.1993.1013
• Джиджев, Х.Н. (1982), «О проблеме разбиения планарных графов», Журнал SIAM по алгебраическим и дискретным методам , 3 (2): 229–240, doi :10.1137/0603022
• Джиджев, Христо Н.; Венкатесан, Шанкар М. (1997), «Приведенные константы для разделения простых циклических графов», Acta Informatica , 34 (3): 231–243, doi :10.1007/s002360050082, S2CID  8406777
• Донат, В. Э.; Хоффман, А. Дж. (1972), «Алгоритмы разбиения графов и компьютерная логика на основе собственных векторов матриц связей», IBM Techn. Disclosure Bull. , 15 : 938–944, как цитируют Спилман и Тенг (2007)
• Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005), "Эффективные точные алгоритмы на планарных графах: использование разложений ветвей с разрезом сферы", Proc. 13th European Symposium on Algorithms (ESA '05) , Lecture Notes in Computer Science, т. 3669, Springer-Verlag, стр. 95–106, doi :10.1007/11561071_11, ISBN 978-3-540-29118-3
• Дворжак, Зденек; Норин, Сергей (2016), «Строго сублинейные сепараторы и полиномиальное разложение», SIAM Journal on Discrete Mathematics , 30 (2): 1095–1101, arXiv : 1504.04821 , doi : 10.1137/15M1017569, MR  3504982, S2CID  27395359
• Эппштейн, Дэвид ; Галил, Цви ; Итальяно, Джузеппе Ф.; Спенсер, Томас Х. (1996), «Разрежение на основе разделителей. I. Тестирование планарности и минимальные остовные деревья», Журнал компьютерных и системных наук , 52 (1): 3–27, doi : 10.1006/jcss.1996.0002
• Эппштейн, Дэвид ; Галиль, Цви ; Итальяно, Джузеппе Ф.; Спенсер, Томас Х. (1998), «Разрежение на основе разделителей. II. Связность ребер и вершин», SIAM Journal on Computing , 28 : 341, doi :10.1137/S0097539794269072
• Эппштейн, Дэвид ; Миллер, Гэри Л.; Тенг , Шан-Хуа (1995), «Детерминированный линейный алгоритм времени для геометрических сепараторов и его приложения», Fundamenta Informaticae , 22 (4): 309–331, doi :10.3233/FI-1995-2241
• Эрдёш, Пол ; Грэм, Рональд ; Семереди, Эндре (1976), «О разреженных графах с плотными длинными путями», Компьютеры и математика с приложениями (PDF) , Оксфорд: Pergamon, стр. 365–369
• Эспере, Луи; Жоре, Гвенаэль; Морин, Пэт (2020), Разреженные универсальные графы планарности , arXiv : 2010.05779
• Фидлер, Мирослав (1973), «Алгебраическая связность графов», Czechoslovak Mathematical Journal , 23 (98): 298–305, doi : 10.21136/CMJ.1973.101168 , hdl :10338.dmlcz/101168, MR  0318007
• Фомин, Федор В.; Тиликос, Димитриос М. (2006a), «Новые верхние оценки разложимости планарных графов» (PDF) , Журнал теории графов , 51 (1): 53–81, doi :10.1002/jgt.20121, S2CID  260481159
• Фомин, Федор В.; Тиликос, Димитриос М. (2006b), «Доминирующие множества в планарных графах: ширина ветвей и экспоненциальное ускорение», SIAM Journal on Computing , 36 (2): 281, doi :10.1137/S0097539702419649, S2CID  5232238
• Фредериксон, Грег Н. (1987), «Быстрые алгоритмы для кратчайших путей в планарных графах с приложениями», SIAM Journal on Computing , 16 (6): 1004–1022, doi :10.1137/0216064, MR  0917037
• Фриз, Алан ; Миллер, Гэри Л.; Тенг , Шан-Хуа (1992), «Параллельный подход «разделяй и властвуй» на основе разделителей в вычислительной геометрии», Труды 4-го симпозиума ACM по параллельным алгоритмам и архитектуре (SPAA '92) (PDF) , стр. 420–429, doi :10.1145/140901.141934, ISBN 0-89791-483-X, S2CID  10914749
• Газит, Хиллел; Миллер, Гэри Л. (1990), «Планарные сепараторы и евклидова норма», Труды Международного симпозиума по алгоритмам (SIGAL'90) (PDF) , Lecture Notes in Computer Science, т. 450, Springer-Verlag, стр. 338–347, doi :10.1007/3-540-52921-7_83, ISBN 978-3-540-52921-7
• Джордж, Дж. Алан (1973), «Вложенное рассечение регулярной сетки конечных элементов», SIAM Journal on Numerical Analysis , 10 (2): 345–363, Bibcode : 1973SJNA...10..345G, doi : 10.1137/0710032, JSTOR  2156361
• Гилберт, Джон Р.; Хатчинсон, Джоан П .; Тарьян, Роберт Э. (1984), «Теорема о разделителе для графов ограниченного рода», Журнал алгоритмов , 5 (3): 391–407, doi :10.1016/0196-6774(84)90019-1, hdl : 1813/6346
• Гилберт, Джон Р.; Тарьян, Роберт Э. (1986), «Анализ алгоритма вложенного рассечения», Numerische Mathematik , 50 (4): 377–404, doi : 10.1007/BF01396660, S2CID  122591105
• Гудрич, Майкл Т. (1995), «Планарные сепараторы и триангуляция параллельных полигонов», Журнал компьютерных и системных наук , 51 (3): 374–389, doi : 10.1006/jcss.1995.1076
• Грембан, Кит Д.; Миллер, Гэри Л .; Тенг, Шан-Хуа (1997), «Моменты инерции и разделители графов» (PDF) , Журнал комбинаторной оптимизации , 1 (1): 79–104, doi :10.1023/A:1009763020645, S2CID  37829
• Хар-Пелед, Сариэль (2011), Простое доказательство существования плоского сепаратора , arXiv : 1105.0103 , Bibcode : 2011arXiv1105.0103H
• Хэ, Синь; Као, Мин-Ян; Лу, Сюэ-И (2000), «Быстрая общая методология для теоретически оптимального кодирования графов», SIAM Journal on Computing , 30 (3): 838–846, arXiv : cs/0101021 , doi :10.1137/S0097539799359117
• Хензингер, Моника Р.; Кляйн, Филип; Рао, Сатиш; Субраманиан, Сайрам (1997), «Быстрые алгоритмы поиска кратчайших путей для планарных графов», Журнал компьютерных и системных наук , 55 (1, часть 1): 3–23, doi : 10.1006/jcss.1997.1493 , MR  1473046
• Хольцер, Мартин; Шульц, Франк; Вагнер, Доротея ; Прасинос, Григориос; Заролиагис, Христос (2009), «Разработка алгоритмов планарного сепаратора», Журнал экспериментальной алгоритмики , 14 : 1.5–1.31, doi :10.1145/1498698.1571635, S2CID  6782855
• Джордан, Камилла (1869), «Sur les assemblages des lignes», Journal für die reine und angewandte Mathematik , 70 : 185–190., как цитируют Миллер и др. (1997)
• Каварабаяси, Кен-Ичи ; Рид, Брюс (2010), «Теорема о разделителе в замкнутых по минору классах», Труды 51-го ежегодного симпозиума IEEE по основам компьютерной науки , doi :10.1109/FOCS.2010.22, S2CID  15860361
• Кляйн, Филип Н.; Мозес, Шей; Вайман, Орен (2010), «Кратчайшие пути в ориентированных планарных графах с отрицательной длиной: алгоритм линейного пространства и времени», ACM Transactions on Algorithms , 6 (2): Art. 30, 18, doi :10.1145/1721837.1721846, MR  2675697, S2CID  3095131 ${\displaystyle O(n\log ^{2}n)}$
• Кляйн, Филип; Рао, Сатиш; Раух, Моника; Субраманиан, Сайрам (1994), «Быстрые алгоритмы поиска кратчайших путей для планарных графов», Труды 26-го симпозиума ACM по теории вычислений (STOC '94) , стр. 27–37, doi :10.1145/195058.195092, ISBN 0-89791-663-8, S2CID  185739
• Łącki, Jakub; Sankowski, Piotr (2011), "Min-cuts and shortest cycles in planar graphs in time", Proc. 19th Annual European Symposium on Algorithms , Lecture Notes in Computer Science, т. 6942, Springer-Verlag, стр. 155–166, arXiv : 1104.4890 , doi : 10.1007/978-3-642-23719-5_14, ISBN ${\displaystyle O(n\log \log n)}$ 978-3-642-23718-8, S2CID  15152406
• Липтон, Ричард Дж .; Роуз, Дональд Дж.; Тарьян, Роберт Э. (1979), «Обобщенное вложенное рассечение», Журнал SIAM по численному анализу , 16 (2): 346–358, Bibcode : 1979SJNA...16..346L, doi : 10.1137/0716027, JSTOR  2156840
• Липтон, Ричард Дж.; Тарьян , Роберт Э. (1979), «Теорема о разделителе для планарных графов», SIAM Journal on Applied Mathematics , 36 (2): 177–189, doi :10.1137/0136016
• Липтон, Ричард Дж.; Тарьян , Роберт Э. (1980), «Применение теоремы о плоском сепараторе», SIAM Journal on Computing , 9 (3): 615–627, doi :10.1137/0209046, S2CID  12961628
• Миллер, Гэри Л. (1986), «Поиск небольших простых разделителей циклов для 2-связных планарных графов» (PDF) , Журнал компьютерных и системных наук , 32 (3): 265–279, doi : 10.1016/0022-0000(86)90030-9
• Миллер, Гэри Л.; Тэн , Шан-Хуа ; Терстон, Уильям ; Вавасис, Стивен А. (1997), «Сепараторы для сферических упаковок и графов ближайших соседей», Журнал ACM , 44 (1): 1–29, doi : 10.1145/256292.256294 , S2CID  17331739
• Миллер, Гэри Л.; Тэн , Шан-Хуа ; Терстон, Уильям ; Вавасис, Стивен А. (1998), «Геометрические сепараторы для конечно-элементных сеток», SIAM Journal on Scientific Computing , 19 (2): 364–386, Bibcode : 1998SJSC...19..364M, CiteSeerX  10.1.1.307.2357 , doi : 10.1137/S1064827594262613
• Пах, Янош ; Агарвал, Панкадж К. (1995), «Теорема Липтона–Тарьяна о разделителе», Комбинаторная геометрия , John Wiley & Sons, стр. 99–102
• Пападимитриу, CH ; Сидери, М. (1996), «Ширина деления пополам графов сетки», Теория вычислительных систем , 29 (2): 97–110, doi :10.1007/BF01305310, S2CID  15617963
• Плоткин, Серж; Рао, Сатиш; Смит, Уоррен Д. (1994), «Неглубокие исключенные миноры и улучшенные разложения графов», Труды 5-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA '94), стр. 462–470, ISBN 9780898713299
• Рид, Брюс ; Вуд, Дэвид Р. (2009), «Линейный алгоритм поиска сепаратора в графе, исключающий минор», ACM Transactions on Algorithms , 5 (4): 1–16, doi : 10.1145/1597036.1597043, S2CID  760001
• Сеймур, Пол Д.; Томас, Робин (1994), «Маршрутизация вызовов и крысолов», Combinatorica , 14 (2): 217–241, doi :10.1007/BF01215352, S2CID  7508434
• Смит, Уоррен Д.; Вормальд, Николас К. (1998), «Геометрические теоремы о разделителях и их применение», 39-й ежегодный симпозиум по основам компьютерной науки (FOCS '98), 8-11 ноября 1998 г., Пало-Альто, Калифорния, США , IEEE Computer Society, стр. 232–243, doi :10.1109/SFCS.1998.743449, S2CID  17962961
• Шпильман, Дэниел А.; Тенг , Шан-Хуа (1996), «Дисковые упаковки и плоские сепараторы», Труды 12-го симпозиума ACM по вычислительной геометрии (SCG '96) (PDF) , стр. 349–358, doi :10.1145/237218.237404, ISBN 0-89791-804-5, S2CID  15937001
• Шпильман, Дэниел А.; Тенг , Шан-Хуа (2007), «Работы по спектральному разбиению: планарные графы и сетки конечных элементов», Линейная алгебра и ее приложения , 421 (2–3): 284–305, doi : 10.1016/j.laa.2006.07.020
• Сикора, Ондрей; Врт'о, Имрих (1993), «Разделители рёбер для графов ограниченного рода с приложениями», Теоретическая информатика , 112 (2): 419–429, doi : 10.1016/0304-3975(93)90031-N , hdl : 11858/00-001M-0000-0014-B6DC-6
• Тазари, Сиамак; Мюллер-Ханнеманн, Маттиас (2009), «Кратчайшие пути за линейное время на классах графов с замкнутыми минорами, с приложением к аппроксимации дерева Штейнера», Дискретная прикладная математика , 157 (4): 673–684, doi : 10.1016/j.dam.2008.08.002
• Унгар, Питер (1951), «Теорема о планарных графах», Журнал Лондонского математического общества , 1 (4): 256, doi :10.1112/jlms/s1-26.4.256
• Вайман, Орен; Юстер, Рафаэль (2010), «Вычисление обхвата планарного графа во времени», SIAM Journal on Discrete Mathematics , 24 (2): 609, CiteSeerX 10.1.1.156.5730 , doi : 10.1137/090767868 ${\displaystyle O(n\log n)}$ 
• Вульф-Нильсен, Кристиан (2009), Обхват плоского орграфа с реальными весами ребер во времени ${\displaystyle O(n\log ^{3}n)}$ , arXiv : 0908.0697 , Bibcode : 2009arXiv0908.0697W