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

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

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

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

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

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

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

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

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

Пример

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

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

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

Конструкции

Наложение слоев в ширину

Липтон и Тарьян (1979) при необходимости дополняют данный планарный граф дополнительными ребрами, чтобы он стал максимально планарным (каждая грань в плоском вложении представляет собой треугольник). Затем они выполняют поиск в ширину с корнем в произвольной вершине. $v$и разобьем вершины на уровни по их расстоянию от $v$. Если $l_{1}$ - медианный уровень (уровень, на котором количество вершин на более высоких и нижних уровнях не более $n/2$) то должны быть уровни $l_{0}$ и $l_{2}$ это $O({\sqrt {n}})$ шаги выше и ниже $l_{1}$ соответственно и которые содержат $O({\sqrt {n}})$ вершин соответственно, иначе их было бы больше, чем $n$ вершины на уровнях рядом $l_{1}$. Они показывают, что должен быть разделитель $S$ образованный союзом $l_{0}$ и $l_{2}$, концы ребра $e$ из $G$ которое не принадлежит дереву поиска в ширину и лежит между двумя уровнями, а вершины двух путей дерева поиска в ширину от конечных точек $e$ вернуться на уровень $l_{0}$. Размер сепаратора $S$ построенное таким образом, не более чем ${\sqrt {8n}}\approx 2.83{\sqrt {n}}$. Вершины разделителя и двух непересекающихся подграфов можно найти за линейное время .

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

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

Простые циклические сепараторы

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

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

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

Разделители кругов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Граф пересечений дисков, в котором не более $k=5$ диски, охватывающие любую точку плоскости

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

Если для наследственного семейства графов существует теорема о сепараторе с сепараторами размера $n^{c}$, для некоторых $c<1$, то оно обязательно имеет полиномиальное разложение , полиномиально ограниченное плотностью его мелких миноров . И наоборот, графы с полиномиальным разложением имеют теоремы о сублинейном разделителе.

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сжатие графа

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

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

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

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

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

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

См. также

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

Ссылки

• Альбер, Йохен; Фернау, Хеннинг; Нидермейер, Рольф (2003), «Разделители графов: параметризованное представление», Journal of Computer and System Sciences , 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", Proc. 9-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '98) , стр. 33–41, ISBN  9780898714104
• Бабай, Л. ; Чанг, Франция ; Эрдеш, П .; Грэм, РЛ ; Спенсер, Дж. Х. (1982), «О графах, которые содержат все разреженные графы», Роза, Александр; Сабидусси, Герт ; Турджен, Жан (ред.), Теория и практика комбинаторики: сборник статей в честь Антона Коцига по случаю его шестидесятилетия (PDF) , Annals of Discrete Mathematics, vol. 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: дата и год ( ссылка )
• Берн, Маршалл (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), «Компактные представления разделимых графов», Proc. 14-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '03) (PDF) , стр. 679–688
• Блеллок, Гай Э.; Фарзан, Араш (2010), «Краткое представление разделимых графов», в книге Амира, Амихуда; Парида, Лакшми (ред.), Proc. 21-й симпозиум по комбинаторному сопоставлению с образцом , Конспекты лекций по информатике, том. 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), «Детерминированный алгоритм с почти линейным временем для поиска минимальных разрезов в плоских графах», Proc. 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) , Journal of Information Processing , 4 (4): 203–207
• Чунг, Фан Р.К. (1990), «Теоремы о сепараторах и их приложения», Корте , Бернхард ; Ловас, Ласло ; Премель, Ханс Юрген; и др. (ред.), Пути, потоки и макет СБИС , Алгоритмы и комбинаторика, том. 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 Journal on Algebraic and Discrete Methods , 3 (2): 229–240, doi : 10.1137/0603022
• Джиджев, Христо Н.; Венкатесан, Шанкар М. (1997), «Приведенные константы для простого разделения графов циклов», Acta Informatica , 34 (3): 231–243, doi : 10.1007/s002360050082 , S2CID   8406777
• Донат, МЫ; Хоффман, AJ (1972), «Алгоритмы разделения графов и компьютерной логики на основе собственных векторов матриц связей», IBM Techn. Раскрытие информации. , 15 : 938–944 , цитируется Spielman & Teng (2007).
• Дорн, Фредерик; Пеннинккс, Элко; Бодлендер, Ганс Л .; Фомин, Федор В. (2005), "Эффективные точные алгоритмы на плоских графах: использование разложений ветвей разреза по сфере", Труды. 13-й Европейский симпозиум по алгоритмам (ESA '05) , Конспекты лекций по информатике, том. 3669, Springer-Verlag, стр. 95–106, номер документа : 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   27395 359
• Эппштейн, Дэвид ; Галил, Цви ; Итальяно, Джузеппе Ф .; Спенсер, Томас Х. (1996), «Разреженность на основе сепаратора. I. Проверка планарности и минимальные остовные деревья», Journal of Computer and System Sciences , 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) , Оксфорд: Пергамон, стр. 365–369
• Эспере, Луи; Жоре, Гвенаэль; Морин, Пэт (2020), Разреженные универсальные графы планарности , arXiv : 2010.05779
• Фидлер, Мирослав (1973), «Алгебраическая связность графов», Чехословацкий математический журнал , 23 (98): 298–305, doi : 10.21136/CMJ.1973.101168 , hdl : 10338.dmlcz/101168 , MR   0318007
• Фомин Федор Владимирович; Тиликос, Димитриос М. (2006a), «Новые верхние границы разложимости планарных графов» (PDF) , Journal of Graph Theory , 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), «Параллельное разделяй и властвуй на основе сепаратора в вычислительной геометрии», Proc. 4-й симпозиум ACM по параллельным алгоритмам и архитектуре (SPAA '92) (PDF) , стр. 420–429, doi : 10.1145/140901.141934 , ISBN  0-89791-483-Х , S2CID   10914749
• Газит, Гилель; Миллер, Гэри Л. (1990), «Плоские сепараторы и евклидова норма», Proc. Международный симпозиум по алгоритмам (SIGAL'90) (PDF) , Конспекты лекций по информатике, том. 450, Springer-Verlag, стр. 338–347, номер документа : 10.1007/3-540-52921-7_83 , ISBN.  978-3-540-52921-7
• Джордж, Дж. Алан (1973), «Вложенное рассечение регулярной сетки конечных элементов», SIAM Journal on Numerical Analysis , 10 (2): 345–363, Бибкод : 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), «Плоские сепараторы и триангуляция параллельных многоугольников», Journal of Computer and System Sciences , 51 (3): 374–389, doi : 10.1006/jcss.1995.1076
• Грембан, Кейт Д.; Миллер, Гэри Л .; Тенг, Шан-Хуа (1997), «Моменты инерции и разделители графов» (PDF) , Journal of Combinatorial Optimization , 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» , Журнал чистой и прикладной математики , 70 : 185–190 , цитируется Миллером и др. (1997)
• Каварабаяси, Кен-Ичи ; Рид, Брюс (2010), «Теорема о сепараторе в минорно-замкнутых классах», Proc. 51-й ежегодный симпозиум IEEE по основам информатики , doi : 10.1109/FOCS.2010.22 , S2CID   15860361
• Кляйн, Филип Н.; Мозес, Шей; Вейманн, Орен (2010), «Кратчайшие пути в ориентированных плоских графах с отрицательной длиной: линейное пространство $O(n\log ^{2}n)$-алгоритм времени», Транзакции ACM по алгоритмам , 6 (2): Ст. 30, 18, doi : 10.1145/1721837.1721846 , MR   2675697 , S2CID   3095131
• Кляйн, Филип; Рао, Сатиш; Раух, Моника; Субраманиан, Сайрам (1994), «Более быстрые алгоритмы поиска кратчайшего пути для плоских графов», Proc. 26-й симпозиум ACM по теории вычислений (STOC '94) , стр. 27–37, doi : 10.1145/195058.195092 , ISBN  0-89791-663-8 , S2CID   185739
• Лонцки, Якуб; Санковски, Петр (2011), «Минимальные разрезы и кратчайшие циклы в плоских графах в $O(n\log \log n)$ время», Proc. 19th Annual European Symposium on Algorithms , Lecture Notes in Computer Science, vol. 6942, Springer-Verlag, стр. 155–166, arXiv : 1104.4890 , doi : 10.1007/978-3-642-23719-5_14 , ISBN  978-3-642-23718-8 , S2CID   15152406
• Липтон, Ричард Дж .; Роуз, Дональд Дж.; Тарьян, Роберт Э. (1979), «Обобщенное вложенное рассечение», SIAM Journal on Numerical Analysis , 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) , Journal of Computer and System Sciences , 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 , дои : 10.1137/S1064827594262613
• Пах, Янош ; Агарвал, Панкадж К. (1995), «Теорема Липтона – Тарьяна о сепараторе», Комбинаторная геометрия , John Wiley & Sons, стр. 99–102
• Пападимитриу, Швейцария ; Сидери, М. (1996), «Ширина сеточных графов пополам», Theory of Computing Systems , 29 (2): 97–110, doi : 10.1007/BF01305310 , S2CID   15617963
• Плоткин, Серж; Рао, Сатиш; Смит, Уоррен Д. (1994), «Неглубокое исключение несовершеннолетних и улучшенное разложение графов», Proc. 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, стр. . 232–243, номер документа : 10.1109/SFCS.1998.743449 , S2CID   17962961.
• Спилман, Дэниел А .; Тенг, Шан-Хуа (1996), «Дисковые насадки и плоские сепараторы», Proc. 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), «Разделители ребер для графов ограниченного рода с приложениями», Theoretical Computer Science , 112 (2): 419–429, doi : 10.1016/0304-3975(93)90031-N , hdl : 11858/00-001M-0000-0014-B6DC-6
• Тазари, Сиамак; Мюллер-Ханнеманн, Маттиас (2009), «Кратчайшие пути за линейное время в классах малозамкнутых графов с применением к аппроксимации дерева Штейнера», Discrete Applied Mathematics , 157 (4): 673–684, doi : 10.1016/j. плотина.2008.08.002
• Унгар, Питер (1951), «Теорема о плоских графах», Журнал Лондонского математического общества , 1 (4): 256, doi : 10.1112/jlms/s1-26.4.256
• Вейманн, Орен; Юстер, Рафаэль (2010), «Вычисление обхвата плоского графа в $O(n\log n)$ время», SIAM Journal on Discrete Mathematics , 24 (2): 609, CiteSeerX   10.1.1.156.5730 , doi : 10.1137/090767868
• Вульф-Нильсен, Кристиан (2009), Обхват плоского орграфа с реальными весами ребер в $O(n\log ^{3}n)$ время , arXiv : 0908.0697 , Bibcode : 2009arXiv0908.0697W