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

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

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

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

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

Формулировка теоремы [ править ]

As it is usually stated, the separator theorem states that, in any ${\displaystyle n}$-vertex planar graph ${\displaystyle G=(V,E)}$, there exists a partition of the vertices of ${\displaystyle G}$ into three sets ${\displaystyle A}$, ${\displaystyle S}$, and ${\displaystyle B}$, such that each of ${\displaystyle A}$ and ${\displaystyle B}$ has at most ${\displaystyle 2n/3}$ vertices, ${\displaystyle S}$ has ${\displaystyle O({\sqrt {n}})}$ vertices, and there are no edges with one endpoint in ${\displaystyle A}$ and one endpoint in ${\displaystyle B}$. It is not required that ${\displaystyle A}$ or ${\displaystyle B}$ form connected subgraphs of ${\displaystyle G}$. ${\displaystyle S}$ is called the separator for this partition.

Эквивалентная формулировка состоит в том, что ребра плоского графа с любой вершиной могут быть подразделены на два подграфа, не пересекающихся по ребрам, и таким образом, чтобы оба подграфа имели по крайней мере вершины и чтобы пересечение множеств вершин двух подграфов имело вершины в Это. Такая перегородка называется разделением . ^[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)}$

Пример [ править ]

Рассмотрим сетку графа со строками и столбцами; количество вершин равно . Так , например, на рисунке, , , и . Если нечетное, есть один центральный ряд, в противном случае есть два ряда, одинаково близких к центру; аналогично, если нечетное, есть один центральный столбец, а в противном случае есть два столбца, одинаково близких к центру. Выбрав любую из этих центральных строк или столбцов и удалив их из графа, он разбивает граф на два меньших связанных подграфа и , каждый из которых имеет самое большее количество вершин. Если (как на рисунке), то выбор центрального столбца даст разделитель${\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}$с вершинами, и аналогично, если тогда выбор центральной строки даст разделитель с не более чем вершинами. Таким образом, каждый сеточный граф имеет разделитель максимального размера , при удалении которого он разбивается на две связанные компоненты, каждая из которых имеет размер не более . ^[3]${\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}$

Конструкции [ править ]

Слои в ширину [ править ]

Липтон и Тарьян (1979) при необходимости дополняют данный плоский граф дополнительными ребрами, чтобы он стал максимально плоским (каждая грань в плоском вложении является треугольником). Затем они выполняют поиск в ширину , начиная с произвольной вершины , и разбивают вершины на уровни по их расстоянию от . Если это средний уровень (уровень таким образом, что число вершин на более высоких и более низких уровней являются не более ) , то должно быть уровни , и которые являются шаги выше и ниже , соответственно , и которые содержат вершины, соответственно, ибо в противном случае было бы больше чем вершины на уровнях около${\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}}$. Они показывают , что должно быть разделитель , образованное объединением и , на концах ребра в том , что не принадлежит к широте-первых дереву поиска и что лежит между двумя уровнями, а вершины на два поиске в ширине древовидные пути от конечных точек до уровня . Размер сконструированного таким образом разделителя не больше . Вершины разделителя и двух непересекающихся подграфов могут быть найдены за линейное время . ^[4]${\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}}}$

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

Простые разделители цикла [ править ]

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

Алон, Сеймур и Томас (1994) доказывают существование простых разделителей циклов более прямо: они позволяют быть циклом не более чем из вершин, с не более чем вершинами снаружи , который образует как можно более равномерное разделение внутреннего и внешнего, и они показывают что эти предположения заставляют быть разделителем. В противном случае расстояния внутри должны равняться расстояниям в диске, окруженном (более короткий путь через внутреннюю часть диска будет составлять часть границы лучшего цикла). Кроме того, он должен иметь ровную длину , иначе его можно улучшить, заменив одно из его ребер двумя другими сторонами треугольника. Если вершины в пронумерованы (по часовой стрелке) от${\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}$к , и вершина сопоставляется с вершиной , то эти согласованные пары могут быть соединены путями, не пересекающимися с вершинами, внутри диска в соответствии с формой теоремы Менгера для плоских графов. Однако общая длина этих путей обязательно будет больше , противоречие. С помощью некоторой дополнительной работы они показывают аналогичным методом, что существует простой разделитель циклов размером не более . ^[7]${\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}}}$

Разделители кругов [ править ]

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

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

Этот метод приводит к рандомизированному алгоритму , который находит такой разделитель линейного времени , ^[10] и менее практичный детерминированный алгоритм с тем же линейным временем , связанным. ^[12] На основе анализа этого алгоритма тщательно , используя известные оценки на плотности упаковки из окружности упаковки , можно показать , чтобы найти сепараторы размера не более ^[13]

Хотя эта улучшенная граница размера разделителя достигается за счет более неравномерного разбиения графа, Spielman & Teng (1996) утверждают, что она обеспечивает улучшенный постоянный коэффициент во временных рамках для вложенного рассечения по сравнению с разделителями Alon, Seymour & Томас (1990) . Размер производимых разделителей может быть дополнительно улучшен на практике за счет использования неравномерного распределения для произвольных плоскостей резания. ^[14]

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

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

Spectral clustering methods, in which the vertices of a graph are grouped by the coordinates of the eigenvectors of matrices derived from the graph, have long been used as a heuristic for graph partitioning problems for nonplanar graphs.^[16] As Spielman & Teng (2007) show, spectral clustering can also be used to derive an alternative proof for a weakened form of the planar separator theorem that applies to planar graphs with bounded degree. In their method, the vertices of a given planar graph are sorted by the second coordinates of the eigenvectors of the Laplacian matrixграфа, и этот отсортированный порядок разбивается в точке, которая минимизирует отношение количества ребер, вырезанных разбиением, к числу вершин на меньшей стороне разбиения. Как они показывают, каждый плоский граф ограниченной степени имеет такое разбиение, в котором отношение равно . Хотя это разделение может не быть сбалансированным, повторение разделения в пределах большей из двух сторон и объединение разрезов, образованных при каждом повторении, в конечном итоге приведет к сбалансированному разделению с краями. Концы этих ребер образуют разделитель размера . ^[17]${\displaystyle O(1/{\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$${\displaystyle O({\sqrt {n}})}$

Разделители краев [ править ]

Вариант теоремы о плоском разделителе включает разделители ребер , небольшие наборы ребер, образующие разрез между двумя подмножествами и вершинами графа. Каждый из двух наборов и должен иметь размер не более постоянной доли от числа вершин графа (обычно оба набора имеют размер не более ), и каждая вершина графа принадлежит ровно одному из и . Разделитель состоит из ребер, имеющих одну конечную точку внутрь и одну конечную точку внутри . Границы размера разделителя ребер включают степень вершин, а также количество вершин в графе: плоские графы, в которых одна вершина имеет степень${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n}$${\displaystyle 2n/3}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n-1}$, including the wheel graphs and star graphs, have no edge separator with a sublinear number of edges, because any edge separator would have to include all the edges connecting the high degree vertex to the vertices on the other side of the cut. However, every planar graph with maximum degree ${\displaystyle \Delta }$ has an edge separator of size ${\displaystyle O({\sqrt {\Delta n}})}$.^[18]

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

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

Нижние границы [ править ]

В сетке графика, набор из точек можно заключить подмножество в большинстве точек сетки, где максимум достигается путем расположения в диагональной линии вблизи угла сетки. Следовательно, чтобы сформировать разделитель, который отделяет хотя бы точки от оставшейся сетки, должен быть как минимум .${\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}$

A separator hierarchy of this type forms the basis for a tree decomposition of the given graph, in which the set of vertices associated with each tree node is the union of the separators on the path from that node to the root of the tree. Since the sizes of the graphs go down by a constant factor at each level of the tree, the upper bounds on the sizes of the separators also go down by a constant factor at each level, so the sizes of the separators on these paths add in a geometric series to ${\displaystyle O({\sqrt {n}})}$. That is, a separator formed in this way has width ${\displaystyle O({\sqrt {n}})}$, and can be used to show that every planar graph has treewidth ${\displaystyle O({\sqrt {n}})}$.

Constructing a separator hierarchy directly, by traversing the binary tree top down and applying a linear-time planar separator algorithm to each of the induced subgraphs associated with each node of the binary tree, would take a total of ${\displaystyle O(n\log n)}$ time. However, it is possible to construct an entire separator hierarchy in linear time, by using the Lipton–Tarjan breadth-first layering approach and by using appropriate data structures to perform each partition step in sublinear time.^[20]

If one forms a related type of hierarchy based on separations instead of separators, in which the two children of the root node are roots of recursively constructed hierarchies for the two subgraphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ of a separation of the given graph, then the overall structure forms a branch-decomposition instead of a tree decomposition. The width of any separation in this decomposition is, again, bounded by the sum of the sizes of the separators on a path from any node to the root of the hierarchy, so any branch-decomposition formed in this way has width ${\displaystyle O({\sqrt {n}})}$ and any planar graph has branchwidth ${\displaystyle O({\sqrt {n}})}$. Although many other related graph partitioning problems are NP-complete, even for planar graphs, it is possible to find a minimum-width branch-decomposition of a planar graph in polynomial time.^[21]

By applying methods of Alon, Seymour & Thomas (1994) more directly in the construction of branch-decompositions, Fomin & Thilikos (2006a) show that every planar graph has branchwidth at most ${\displaystyle 2.12{\sqrt {n}}}$, with the same constant as the one in the simple cycle separator theorem of Alon et al. Since the treewidth of any graph is at most ${\displaystyle 3/2}$ its branchwidth, this also shows that planar graphs have treewidth at most ${\displaystyle 3.18{\sqrt {n}}}$.

Other classes of graphs[edit]

Some sparse graphs do not have separators of sublinear size: in an expander graph, deleting up to a constant fraction of the vertices still leaves only one connected component.^[22]

Possibly the earliest known separator theorem is a result of Jordan (1869) that any tree can be partitioned into subtrees of at most ${\displaystyle n/2}$ vertices each by the removal of a single vertex.^[10] In particular, the vertex that minimizes the maximum component size has this property, for if it did not then its neighbor in the unique large subtree would form an even better partition. By applying the same technique to a tree decomposition of an arbitrary graph, it is possible to show that any graph has a separator of size at most equal to its treewidth.

If a graph ${\displaystyle G}$ is not planar, but can be embedded on a surface of genus ${\displaystyle g}$, then it has a separator with ${\displaystyle O({\sqrt {gn}})}$ vertices. Gilbert, Hutchinson & Tarjan (1984) prove this by using a similar approach to that of Lipton & Tarjan (1979). They group the vertices of the graph into breadth-first levels and find two levels the removal of which leaves at most one large component consisting of a small number of levels. This remaining component can be made planar by removing a number of breadth-first paths proportional to the genus, after which the Lipton–Tarjan method can be applied to the remaining planar graph. The result follows from a careful balancing of the size of the removed two levels against the number of levels between them. If the graph embedding is given as part of the input, its separator can be found in linear time. Graphs of genus ${\displaystyle g}$ also have edge separators of size ${\displaystyle O({\sqrt {g\Delta n}})}$.^[23]

Graphs of bounded genus form an example of a family of graphs closed under the operation of taking minors, and separator theorems also apply to arbitrary minor-closed graph families. In particular, if a graph family has a forbidden minor with ${\displaystyle h}$ vertices, then it has a separator with ${\displaystyle O(h{\sqrt {n}})}$ vertices, and such a separator can be found in time ${\displaystyle O(n^{1+\varepsilon })}$ for any ${\displaystyle \varepsilon >0}$.^[24]

The circle separator method of Miller et al. (1997) generalizes to the intersection graphs of any system of ${\displaystyle d}$-dimensional balls with the property that any point in space is covered by at most some constant number ${\displaystyle k}$ of balls, to ${\displaystyle k}$-nearest-neighbor graphs in ${\displaystyle d}$ dimensions,^[10] and to the graphs arising from finite element meshes.^[25] The sphere separators constructed in this way partition the input graph into subgraphs of at most ${\displaystyle n(d+1)/(d+2)}$ vertices. The size of the separators for ${\displaystyle k}$-ply ball intersection graphs and for ${\displaystyle k}$-nearest-neighbor graphs is ${\displaystyle O(k^{1/d}n^{1-1/d})}$.^[10]

If a hereditary family of graphs has a separator theorem with separators of size ${\displaystyle n^{c}}$, for some ${\displaystyle c<1}$, then it necessarily has polynomial expansion, a polynomial bound on the density of its shallow minors. Conversely, graphs with polynomial expansion have sublinear separator theorems.^[26]

Applications[edit]

Divide and conquer algorithms[edit]

Separator decompositions can be of use in designing efficient divide and conquer algorithms for solving problems on planar graphs. As an example, one problem that can be solved in this way is to find the shortest cycle in a weighted planar digraph. This may be solved by the following steps:

• Partition the given graph ${\displaystyle G}$ into three subsets ${\displaystyle S}$, ${\displaystyle A}$, ${\displaystyle B}$ according to the planar separator theorem
• Recursively search for the shortest cycles in ${\displaystyle A}$ and ${\displaystyle B}$
• Use Dijkstra's algorithm to find, for each vertex ${\displaystyle s}$ in ${\displaystyle S}$, the shortest cycle through ${\displaystyle s}$ in ${\displaystyle G}$.
• Return the shortest of the cycles found by the above steps.

The time for the two recursive calls to ${\displaystyle A}$ and ${\displaystyle B}$ in this algorithm is dominated by the time to perform the ${\displaystyle O({\sqrt {n}})}$ calls to Dijkstra's algorithm, so this algorithm finds the shortest cycle in ${\displaystyle O(n^{3/2}\log n)}$ time.

A faster algorithm for the same shortest cycle problem, running in time ${\displaystyle O(n\log ^{3}n)}$, was given by Wulff-Nilsen (2009). His algorithm uses the same separator-based divide and conquer structure, but uses simple cycle separators rather than arbitrary separators, so that the vertices of ${\displaystyle S}$ belong to a single face of the graphs inside and outside the cycle separator. He then replaces the ${\displaystyle O({\sqrt {n}})}$ separate calls to Dijkstra's algorithm with more sophisticated algorithms to find shortest paths from all vertices on a single face of a planar graph and to combine the distances from the two subgraphs. For weighted but undirected planar graphs, the shortest cycle is equivalent to the minimum cut in the dual graph and can be found in ${\displaystyle O(n\log \log n)}$ time,^[27] and the shortest cycle in an unweighted undirected planar graph (its girth) may be found in time ${\displaystyle O(n)}$.^[28] (However, the faster algorithm for unweighted graphs is not based on the separator theorem.)

Frederickson proposed another faster algorithm for single source shortest paths by implementing separator theorem in planar graphs.^[29] This is an improvement of Dijkstra's algorithm with iterative search on a carefully selected subset of the vertices. This version takes ${\displaystyle O(n{\sqrt {\log n}})}$ time in an ${\displaystyle n}$-vertex graph. Separators are used to find a division of a graph, that is, a partition of the edge-set into two or more subsets, called regions. A node is said to be contained in a region if some edge of the region is incident to the node. A node contained in more than one region is called a boundary node of the regions containing it. The method uses the notion of a ${\displaystyle r}$-division of an ${\displaystyle n}$-node graph that is a graph division into ${\displaystyle O(n/r)}$ regions, each containing ${\displaystyle O(r)}$ nodes including ${\displaystyle O({\sqrt {r}})}$ boundary nodes. Frederickson showed that an ${\displaystyle r}$-division can be found in ${\displaystyle O(n\log n)}$ time by recursive application of separator theorem.

The sketch of his algorithm to solve the problem is as follows.

1. Preprocessing Phase: Partition the graph into carefully selected subsets of vertices and determine the shortest paths between all pairs of vertices in these subsets, where intermediate vertices on this path are not in the subset. This phase requires a planar graph ${\displaystyle G_{0}}$ to be transformed into ${\displaystyle G}$ with no vertex having degree greater than three. From a corollary of Euler's formula, the number of vertices in the resulting graph will be ${\displaystyle n\leq 6n_{0}-12}$, where ${\displaystyle n_{0}}$ is the number of vertices in ${\displaystyle G_{0}}$. This phase also ensures the following properties of a suitable ${\displaystyle r}$-division. A suitable ${\displaystyle r}$-division of a planar graph is an ${\displaystyle r}$-division such that,
   • each boundary vertex is contained in at most three regions, and
   • any region that is not connected consists of connected components, all of which share boundary vertices with exactly the same set of either one or two connected regions.
2. Search Phase:
   • Main Thrust: Find shortest distances from the source to each vertex in the subset. When a vertex ${\displaystyle v}$ in the subset is closed, the tentative distance ${\displaystyle d(w)}$ must be updated for all vertices ${\displaystyle w}$ in the subset such that a path exists from ${\displaystyle v}$ to ${\displaystyle w}$.
   • Mop-up: Determine shortest distances to every remaining vertex.

Henzinger et al. extended Frederickson's ${\displaystyle r}$-division technique for the single source shortest path algorithm in planar graphs for nonnegative edge-lengths and proposed a linear time algorithm.^[30] Their method generalizes Frederickson's notion of graph-divisions such that now an ${\displaystyle (r,s)}$-division of an ${\displaystyle n}$-node graph is a division into ${\displaystyle O(n/r)}$ regions, each containing ${\displaystyle r^{O(1)}}$ nodes, each having at most ${\displaystyle s}$ boundary nodes. If an ${\displaystyle (r,s)}$-division is repeatedly divided into smaller regions, that is called a recursive division. This algorithm uses approximately ${\displaystyle \log ^{*}n}$ levels of divisions, where ${\displaystyle \log ^{*}}$ denotes the iterated logarithm function. The recursive division is represented by a rooted tree whose leaves are labeled by distinct edge of ${\displaystyle G}$. The root of the tree represents the region consisting of all of ${\displaystyle G}$, the children of the root represent the subregions into which that region is divided and so on. Each leaf (atomic region) represents a region containing exactly one edge.

Nested dissection is a separator based divide and conquer variation of Gaussian elimination for solving sparse symmetric systems of linear equations with a planar graph structure, such as the ones arising from the finite element method. It involves finding a separator for the graph describing the system of equations, recursively eliminating the variables in the two subproblems separated from each other by the separator, and then eliminating the variables in the separator.^[31] The fill-in of this method (the number of nonzero coefficients of the resulting Cholesky decomposition of the matrix) is ${\displaystyle O(n\log n)}$,^[32] allowing this method to be competitive with iterative methods for the same problems.^[31]

Klein, Mozes and Weimann^[33] gave an ${\displaystyle O(n\log ^{2}n)}$-time, linear-space algorithm to find the shortest path distances from a source vertex ${\displaystyle s}$ to all other vertices for a directed planar graph with positive and negative arc-lengths containing no negative cycles. Their algorithm uses planar graph separators to find a Jordan curve ${\displaystyle C}$ that passes through ${\displaystyle O({\sqrt {n}})}$ nodes (and no arcs) such that between ${\displaystyle n/3}$ and ${\displaystyle 2n/3}$ nodes are enclosed by ${\displaystyle C}$. Nodes through which ${\displaystyle C}$ passes are boundary nodes. The original graph ${\displaystyle G}$ is separated into two subgraphs ${\displaystyle G_{0}}$ and ${\displaystyle G_{1}}$ by cutting the planar embedding along ${\displaystyle C}$ and duplicating the boundary nodes. The boundary nodes in each graph ${\displaystyle G_{i}}$ lie on the boundary of a single face ${\displaystyle F_{i}}$.

The overview of their approach is given below.

• Recursive call: The first stage recursively computes the distances from ${\displaystyle r}$ within each graph ${\displaystyle G_{i}}$.
• Intra-part boundary-distances: For each graph ${\displaystyle G_{i}}$ compute all distances in ${\displaystyle G_{i}}$ between boundary nodes. This takes ${\displaystyle O(n\log n)}$ time.
• Single-source inter-part boundary distances: A shortest path in ${\displaystyle G}$ passes back and forth between ${\displaystyle G_{0}}$ and ${\displaystyle G_{1}}$ to compute the distances in ${\displaystyle G}$ from ${\displaystyle r}$ to all the boundary nodes. Alternating iterations use the all-boundary-distances in ${\displaystyle G_{0}}$ and ${\displaystyle G_{1}}$. The number of iterations is ${\displaystyle O({\sqrt {n}})}$, and the overall time for this stage is ${\displaystyle O(n\alpha (n))}$ where ${\displaystyle \alpha (n)}$ is the inverse Ackermann function.
• Single-source inter-part distances: The distances computed in the previous stages are used, together with a Dijkstra computation within a modified version of each G_i , to compute the distances in ${\displaystyle G}$ from ${\displaystyle r}$ to all the nodes. This stage takes ${\displaystyle O(n\log n)}$ time.
• Rerooting single-source distances: The distances from ${\displaystyle r}$ in ${\displaystyle G}$ are transformed into nonnegative lengths, and again Dijkstra's algorithm is used to compute distances from ${\displaystyle s}$. This stage requires ${\displaystyle O(n\log n)}$ time.

An important part of this algorithm is the use of price functions and reduced lengths. For a directed graph ${\displaystyle G}$ with arc-lengths ${\displaystyle \ell (uv)}$, a price function is a function ${\displaystyle \varphi }$ from the nodes of ${\displaystyle G}$ to the real numbers. For an arc ${\displaystyle uv}$, the reduced length with respect to ${\displaystyle \varphi }$ is ${\displaystyle \ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)}$. A feasible price function is a price function that induces nonnegative reduced lengths on all arcs of ${\displaystyle G}$. It is useful in transforming a shortest-path problem involving positive and negative lengths into one involving only nonnegative lengths, which can then be solved using Dijkstra's algorithm.

The separator based divide and conquer paradigm has also been used to design data structures for dynamic graph algorithms^[34] and point location,^[35] algorithms for polygon triangulation,^[20] shortest paths,^[36] and the construction of nearest neighbor graphs,^[37] and approximation algorithms for the maximum independent set of a planar graph.^[35]

Exact solution of NP-hard optimization problems[edit]

By using dynamic programming on a tree decomposition or branch-decomposition of a planar graph, many NP-hard optimization problems may be solved in time exponential in ${\displaystyle {\sqrt {n}}}$ or ${\displaystyle {\sqrt {n}}\log n}$. For instance, bounds of this form are known for finding maximum independent sets, Steiner trees, and Hamiltonian cycles, and for solving the travelling salesman problem on planar graphs.^[38] Similar methods involving separator theorems for geometric graphs may be used to solve Euclidean travelling salesman problem and Steiner tree construction problems in time bounds of the same form.^[39]

For parameterized problems that admit a kernelization that preserves planarity and reduces the input graph to a kernel of size linear in the input parameter, this approach can be used to design fixed-parameter tractable algorithms the running time of which depends polynomially on the size of the input graph and exponentially on ${\displaystyle {\sqrt {k}}}$, where ${\displaystyle k}$ is the parameter of the algorithm. For instance, time bounds of this form are known for finding vertex covers and dominating sets of size ${\displaystyle k}$.^[40]

Approximation algorithms[edit]

Lipton & Tarjan (1980) observed that the separator theorem may be used to obtain polynomial time approximation schemes for NP-hard optimization problems on planar graphs such as finding the maximum independent set. Specifically, by truncating a separator hierarchy at an appropriate level, one may find a separator of size ${\displaystyle O(n/{\sqrt {\log n}})}$ the removal of which partitions the graph into subgraphs of size at most ${\displaystyle c\log n}$, for any constant ${\displaystyle c}$. By the four-color theorem, there exists an independent set of size at least ${\displaystyle n/4}$, so the removed nodes form a negligible fraction of the maximum independent set, and the maximum independent sets in the remaining subgraphs can be found independently in time exponential in their size. By combining this approach with later linear-time methods for separator hierarchy construction^[20] and with table lookup to share the computation of independent sets between isomorphic subgraphs, it can be made to construct independent sets of size within a factor of ${\displaystyle 1-1/{\sqrt {\log n}}}$ of optimal, in linear time. However, for approximation ratios even closer to one than this factor, a later approach of Baker (1994) (based on tree-decomposition but not on planar separators) provides better tradeoffs of time versus approximation quality.

Similar separator-based approximation schemes have also been used to approximate other hard problems such as vertex cover.^[41] Arora et al. (1998) use separators in a different way to approximate the travelling salesman problem for the shortest path metric on weighted planar graphs; their algorithm uses dynamic programming to find the shortest tour that, at each level of a separator hierarchy, crosses the separator a bounded number of times, and they show that as the crossing bound increases the tours constructed in this way have lengths that approximate the optimal tour.

Graph compression[edit]

Separators have been used as part of data compression algorithms for representing planar graphs and other separable graphs using a small number of bits. The basic principle of these algorithms is to choose a number ${\displaystyle k}$ and repeatedly subdivide the given planar graph using separators into ${\displaystyle O(n/k)}$ subgraphs of size at most ${\displaystyle k}$, with ${\displaystyle O(n/{\sqrt {k}})}$ vertices in the separators. With an appropriate choice of ${\displaystyle k}$ (at most proportional to the logarithm of ${\displaystyle n}$) the number of non-isomorphic ${\displaystyle k}$-vertex planar subgraphs is significantly less than the number of subgraphs in the decomposition, so the graph can be compressed by constructing a table of all the possible non-isomorphic subgraphs and representing each subgraph in the separator decomposition by its index into the table. The remainder of the graph, formed by the separator vertices, may be represented explicitly or by using a recursive version of the same data structure. Using this method, planar graphs and many more restricted families of graphs may be encoded using a number of bits that is information-theoretically optimal: if there are ${\displaystyle P_{n}}$ ${\displaystyle n}$-vertex graphs in the family of graphs to be represented, then an individual graph in the family can be represented using only ${\displaystyle (1+o(1))\log _{2}P_{n}}$ bits.^[42] It is also possible to construct representations of this type in which one may test adjacency between vertices, determine the degree of a vertex, and list neighbors of vertices in constant time per query, by augmenting the table of subgraphs with additional tabular information representing the answers to the queries.^[43]

Universal graphs[edit]

A universal graph for a family ${\displaystyle {\mathcal {F}}}$ of graphs is a graph that contains every member of ${\displaystyle {\mathcal {F}}}$ as a subgraphs. Separators can be used to show that the ${\displaystyle n}$-vertex planar graphs have universal graphs with ${\displaystyle n}$ vertices and ${\displaystyle O(n^{3/2})}$ edges.^[44]

The construction involves a strengthened form of the separator theorem in which the size of the three subsets of vertices in the separator does not depend on the graph structure: there exists a number ${\displaystyle c}$, the magnitude of which at most a constant times ${\displaystyle {\sqrt {n}}}$, such that the vertices of every ${\displaystyle n}$-vertex planar graph can be separated into subsets ${\displaystyle A}$, ${\displaystyle S}$, and ${\displaystyle B}$, with no edges from ${\displaystyle A}$ to ${\displaystyle B}$, with ${\displaystyle |S|=c}$, and with ${\displaystyle |A|=|B|=(n-c)/2}$. This may be shown by using the usual form of the separator theorem repeatedly to partition the graph until all the components of the partition can be arranged into two subsets of fewer than ${\displaystyle n/2}$ vertices, and then moving vertices from these subsets into the separator as necessary until it has the given size.

Once a separator theorem of this type is shown, it can be used to produce a separator hierarchy for ${\displaystyle n}$-vertex planar graphs that again does not depend on the graph structure: the tree-decomposition formed from this hierarchy has width ${\displaystyle O({\sqrt {n}})}$ and can be used for any planar graph. The set of all pairs of vertices in this tree-decomposition that both belong to a common node of the tree-decomposition forms a trivially perfect graph with ${\displaystyle O(n^{3/2})}$ vertices that contains every ${\displaystyle n}$-vertex planar graph as a subgraph. A similar construction shows that bounded-degree planar graphs have universal graphs with ${\displaystyle O(n\log n)}$ edges, where the constant hidden in the O notation depends on the degree bound. Any universal graph for planar graphs (or even for trees of unbounded degree) must have ${\displaystyle \Omega (n\log n)}$ edges.^[44]

Esperet, Joret & Morin (2020) announced that the ${\displaystyle O(n^{3/2})}$ construction using separators can be improved, to ${\displaystyle n^{1+o(1)}}$.

See also[edit]

• Vertex separator
• Geometric separator

Notes[edit]

References[edit]