Теорема про планарне розбиття

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

Більш слабка форма теореми розбиття з  ${\displaystyle O({\sqrt {n}}\log(n))}$ вершинами в розбитті, а не ${\displaystyle O({\sqrt {n}})}$ була спочатку доведена Унгаро (1951), а форма з близьким асимптотична оцінка від розміру розбиття вперше доведено по Lipton і Tarjan (1979). З їх роботі, теорема розбиття був reproven кількома різними способами, постійна в ${\displaystyle O({\sqrt {n}})}$ термін теореми була покращена, і це був продовжений до певних класів не планарних графів.

Повторне застосування теореми розбиття виробляє роздільник ієрархії, які можуть набувати форми або розкладання дерева або гілкове розкладання графу. Розбиття ієрархії можуть бути використані для розробки ефективного алгоритму розділяю і володарю для планарних графів, і динамічне програмування на цих ієрархій може бути використаний для розробки експоненціальне час і фіксованою параметрів згідливим алгоритми для вирішення NP-важкою задачі оптимізації на цих графіках. Розбиття ієрархії також можуть бути використані в вкладених перетинів, ефективного варіанту Гаусса для вирішення розріджених систем лінійних рівнянь, що випливають з методів кінцевих елементів.

Теорія Двовимірності Демейна, Фоміна, Hajiaghayi і Thilikos узагальнює і значно розширює застосовність теореми розбиття для величезної множини задач мінімізації планарних графів і в більш загальному графі за винятком фіксованих графів-мінорів.

Формулювання теореми 

Як зазвичай вказується, теорема стверджує, що розбиття, в будь-якому n-вершиного планарного графа  ${\displaystyle G=(V,E)}$, існує розбиття вершин ${\displaystyle G}$ в трьох сетах ${\displaystyle A}$, ${\displaystyle S}$, і ${\displaystyle B}$, такі, що кожен з і ${\displaystyle B}$ має в більшості ${\displaystyle {\frac {2n}{3}}}$ вершин, ${\displaystyle S}$ має ${\displaystyle O({\sqrt {n}})}$ вершини, і немає ребер з однієї кінцевої точки в ${\displaystyle A}$ і однієї кінцевої точки в ${\displaystyle B}$. Це не потрібно, що  ${\displaystyle A}$ або ${\displaystyle B}$ зв'язні підграфи з ${\displaystyle G}$. ${\displaystyle S}$ називається розбиттям для цього розділу.

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

Постійна ${\displaystyle {\frac {2}{3}}}$ у формулюванні теореми розбиття є довільним і може бути замінений будь-яким іншим номером у відкритому проміжку ${\displaystyle ({\frac {1}{2}},1)}$, не змінюючи форму теореми: розділ в більш рівних підмножин можуть бути отримані від менш навіть розділу по кілька разів розділивши великі набори в нерівномірному розділу і перегрупування результаті зв'язкові компоненти.[1]

Приклад

планарне розбиття для сітки графів

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

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

Будівельні 

Ширина першого шару

Lipton & Тар'я (1979) доповнити даний планарний граф додатковими гранями, при необхідності, таким чином, що він стає максимальним планарними (кожна грань в планарному вкладенні являє собою трикутник). Потім вони виконують пошуку в ширину, з коренем у довільній вершини ${\displaystyle v}$, і розділити вершини в рівнях їх відстані від ${\displaystyle v}$. Якщо  ${\displaystyle l_{1}}$ є середній рівень (рівень, так що число вершин у вищих і нижчих рівнях як в найбільш ${\displaystyle {\frac {n}{2}}}$), тобто повинні бути рівні ${\displaystyle l_{0}}$ і ${\displaystyle l_{2}}$_, які ${\displaystyle O({\sqrt {n}})}$ кроків вище і нижче ${\displaystyle l_{1}}$_, відповідно, і які містять ${\displaystyle O({\sqrt {n}})}$ вершин, відповідно, в іншому випадку було б більше, ніж п вершин на рівнях поблизу ${\displaystyle l_{1}}$. Вони показують, що там має бути роздільник ${\displaystyle S}$ формується шляхом об'єднання  ${\displaystyle l_{0}}$ і ${\displaystyle l_{2}}$_, кінцеві точки з краю G, які не належать до пошук в ширину дерева і знаходиться між двома рівнями, а вершини на двох в ширину дерева пошуку шляхів від е назад до рівня ${\displaystyle l_{0}}$. Розмір розбиття ${\displaystyle S}$ побудована таким чином, не більше ${\displaystyle {\sqrt {8}}{\sqrt {n}}}$, або приблизно ${\displaystyle 2.83{\sqrt {n}}}$. Вершини розбиття і два непересічних подграфов можна знайти в лінійному часу.

Це доказ теореми розбиття застосовується також для зважених планарних графів, в якому кожна вершина має невід'ємне вартість. Графік може бути розділена на три групи ${\displaystyle A}$, ${\displaystyle S}$, і ${\displaystyle B}$ такі, що і ${\displaystyle B}$ у кожного є в більшості ${\displaystyle {\frac {2}{3}}}$ від загальної вартості і ${\displaystyle S}$ має ${\displaystyle O({\sqrt {n}})}$ вершин, без будь-яких ребер до ${\displaystyle B}$. Більш ретельного аналізу аналогічну конструкцію розбиття, Djidjev (1982) показує, що обмеження на розмір ${\displaystyle S}$ може бути зведена до ${\displaystyle {\sqrt {6}}{\sqrt {n}}}$, або приблизно ${\displaystyle 2.45{\sqrt {n}}}$.

Хольцер та ін. (2009) пропонують спрощену версію цього підходу: вони збільшують графік, щоб бути максимально планарною і побудувати широту в першу чергу дерево пошуку, як раніше. Тоді для кожного ребра е, який не є частиною дерева, вони утворюють цикл шляхом об'єднання е з шляху дерева, який з'єднує свої кінцеві точки. Потім вони використовують як роздільник вершини одного з цих циклів. Хоча цей підхід не може бути гарантована, щоб знайти невелике розбиття для планарних графів великого діаметра, їхні експерименти показують, що він перевершує за Lipton-Тар'я і Djidjev завширшки методи пошарового нанесення на багатьох видів планарного графа.

Прості розбиття циклу 

Для графа, який вже максимально планарний можна показати більш сильну конструкцію простого розбиття циклу, цикл малої довжини таким чином, що всередині і зовні циклу (в унікальному планарному вкладені графа) мають по крайней більшість ${\displaystyle {\frac {2n}{3}}}$ вершини. Міллер (1986) доводить це (з розміром розбиття ${\displaystyle {\sqrt {8}}{\sqrt {n}}}$), використовуючи техніку Ліптон-Тар'я для модифікованої версії широти першим пошуку, в якому рівні форма пошуку простих циклів.

Алон, Сеймур і Томас (1994) довели існування простих розбиттів циклу більш безпосередньо: вони дозволяють ${\displaystyle C}$ буде цикл на найбільш ${\displaystyle {\sqrt {8}}{\sqrt {n}}}$ вершин, з не більш ${\displaystyle {\frac {2n}{3}}}$ вершин поза ${\displaystyle C}$, що форми, як навіть розділу внутрішнього і зовнішнього, наскільки це можливо, і вони показують, що ці припущення змусить ${\displaystyle C}$ розбитися .В іншому випадку, в межах відстані ${\displaystyle C}$ повинен бути рівний відстані в диску, оточеній ${\displaystyle C}$ (коротший шлях через внутрішню частину диска стане частиною кордону кращого циклу). Крім того, ${\displaystyle C}$ повинні бути довжиною рівно ${\displaystyle {\sqrt {8}}{\sqrt {n}}}$, в іншому випадку вона може бути поліпшена шляхом заміни одного з його країв двох інших сторін трикутника. Якщо вершини в ${\displaystyle C}$ нумеруються (за годинниковою стрілкою) від ${\displaystyle 1}$ до ${\displaystyle {\sqrt {8}}{\sqrt {n}}}$  і вершини ${\displaystyle i}$ поєднується з вершини ${\displaystyle {\sqrt {8}}{\sqrt {n}}-i+1}$, то ці підібрані пари можуть бути пов'язані вершинних непересічних шляхів в межах диск, за формою теореми Менгера для планарних графів. Тим не менш, загальна довжина цих шляхів обов'язково перевищувати ${\displaystyle n}$, протиріччя. З деякою додаткової роботи, яку вони показують, аналогічним способом, що існує простий роздільник циклу розмір не більше ${\displaystyle ({\frac {3}{\sqrt {2}}}){\sqrt {n}}}$, приблизно ${\displaystyle 2.12{\sqrt {n}}}$.

Djidjev & Венкатесан (1997) далі вдосконалювали постійний коефіцієнт в простій теореми розбиття цикл ${\displaystyle 1.97{\sqrt {n}}}$. Їх метод також можете знайти прості розбиття циклу для графів з невід'ємними вагами вершин, з розміром розбиття не більше ${\displaystyle {\frac {2n}{3}}}$, і може генерувати розбиття з меншим розміром за рахунок більш нерівномірним розбиттям графа. У 2-зв'язний планарні графи, що не максимальна, існують прості розбиття циклу з розміром, пропорційним евклідової нормоювектора довжини обличчя, які можуть бути знайдені найближчим часом лінійний.

Коло розбиття

Згідно з теоремою Кебе-Андреев-Терстона коло-упаковки, будь-який планарний граф може бути представлений в упаковці круглих дисків в площині з непересічних інтер'єрів, наприклад, що дві вершини в графі суміжні тоді і тільки тоді, коли відповідна пара дисків взаємно дотичній. Як Міллер та ін. (1997) шоу, для такої насадки, існує коло, яке має більше ${\displaystyle {\frac {3n}{4}}}$ диски торкаючись або всередині неї, в найбільш ${\displaystyle {\frac {3n}{4}}}$ диски торкаючись або за її межами, і який перетинає ${\displaystyle O({\sqrt {n}})}$ (дисків).

Щоб довести це, Міллер та ін. використовували стереографічну проєкцію на карті упаковки на поверхні одиничної сфери у трьох вимірах. Ретельно вибираючи проєкцію, центром сфери можуть бути зроблені в центральній точки дискових центрів на його поверхні, так що будь-яка площина, що проходить через центр сфери розділів його в двох напівпросторів, що кожен містять або перетинають понад ${\displaystyle {\frac {3n}{4}}}$ з дисків. Якщо площина, що проходить через центр вибирається випадково рівномірно, диск буде перетинатися з імовірністю, пропорційною її радіусу. Таким чином, очікувана кількість дисків, які перетинаються пропорційна сумі радіусів кіл. Тим не менш, сума квадратів радіусів пропорційна сумарній площі дисків, який знаходиться на найбільш загальна площа поверхні одиничної сфери, постійне. Аргумент участю нерівність Дженсена показує, що, коли сума квадратів ${\displaystyle n}$ невід'ємних дійсних чисел обмежена константою, сума самих чисел ${\displaystyle O({\sqrt {n}})}$. Таким чином, очікуване число дисків, що перетинаються випадкової площині ${\displaystyle O({\sqrt {n}})}$ і існує площину, яка перетинає саме, що багато диски. Цей літак перетинає сферу в великий круг, який виступає вниз до колу в площині із заданими властивостями. ${\displaystyle O({\sqrt {n}})}$ диски схрещені цього кола відповідають вершинам планарного розбиття графа, який відокремлює вершин, диски всередині кола з вершин, диски поза колом, з не більш ${\displaystyle {\frac {3n}{4}}}$ вершин у кожній з цих двох підмножин. 

Цей метод призводить до рандомізованого алгоритму, який знаходить такий розбиття в лінійному часу, і менш практичним детермінований алгоритм з тією ж лінійної час пов'язані.  Аналізуючи цей алгоритм ретельно використовуючи відомі оцінки на щільність упаковки з кола упаковки, можна показати, щоб знайти розбиття розміру не більше

${\displaystyle {\sqrt {\frac {2\pi }{\sqrt {3}}}}\left({\frac {1+{\sqrt {3}}}{2{\sqrt {2}}}}+o(1)\right){\sqrt {n}}\approx 1.84{\sqrt {n}}.}$

Хоча це поліпшений розмір розбиття пов'язаний приходить на рахунок більш-нерівній розбиття графа, Шпільман і Ден (1996) стверджують, що воно забезпечує поліпшений постійний коефіцієнт в час за годинником для вкладених перетинів в порівнянні з розбиття Алон, Сеймур і Томас (1990). Розмір розбиття вона виробляє можуть бути додатково поліпшені, на практиці, за допомогою неоднорідний розподіл для випадкового ріжучих площин. 

Стереографічна проєкція в Міллер та ін. Аргумент можна уникнути, враховуючи маленький коло, що містить постійну частку центрами дисків, а потім розширювати його на константу підбирають рівномірно в діапазоні ${\displaystyle [1,2]}$. Легко стверджувати, як в Miller та ін., Що диски, перетинають розширений коло утворюють правильний роздільник, і що, в очікуванні, розбиття має правильний розмір. Отримані константи дещо гірше. 

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

Спектральні кластеризації методи, в яких вершини графа, згруповані за координатами векторів у матрицях, отриманих з графіка, вже давно використовується як евристика для поділу графік проблем непланарних графіків.  Як Шпільман та Ден (2007) показують, спектральний кластеризації також можуть бути використані для отримання альтернативного доказу по ослабленій формі теореми при планарне розиття який відноситься до планарних графів з обмеженою ступенем. У їхнього методу, вершини даного планарного графа упорядковано по другому координат векторів в Лапласа матриці графіка, і це сортується порядок розділена в точці, що зводить до мінімуму відношення числа ребер скоротити перегородкою до числа вершин на меншу сторону перегородки. Як вони показують, планарний граф обмеженій мірі має розбиття цього типу, в якому відношення ${\displaystyle O({\frac {1}{\sqrt {n}}})}$. Хоча цей розділ не може бути збалансованим, повторюючи розділів всередині більшого з двох сторін і приймаючи союз скорочень, що утворюються при кожному повторенні, в кінцевому рахунку призвести до збалансованого розділу з ${\displaystyle O({\sqrt {n}})}$ ребер. Кінці цих краях утворюють роздільник розмір ${\displaystyle O({\sqrt {n}})}$

Крайові розбиття

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

Просте розбиття циклу в неоднозначному графі планарної норми графіка край розкладання в оригінальній графіці. Застосування просту теорему розкладання цикл зGazit & Miller (1990) в неоднозначному графі даного планарного графа зміцнює ${\displaystyle O({\sqrt {\Delta n}})}$ пов'язані за розміром крайової розбиття, показуючи, що кожен планарний граф має ребро розкладання, розмір якого пропорційний евклідової нормою вектора його вершинних градусів.

Papadimitriou & Sideri (1996) описують поліноміальний алгоритм часу для знаходження найменшого краю розбиття, яка розділяє графік G на два подграфа однакового розміру, коли G є подграфа з сітки граф без отворів або з постійним числом отворів. Тим не менш, вони припустити, що проблема NP-повна для довільних планарних графів, і вони показують, що складність проблеми полягає в тому ж, для мережевих графіків з довільним числом отворів, так і для довільних планарних графів.

Нижні межі 

У ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ сітки графіка, встановленого ${\displaystyle S}$ з ${\displaystyle s<{\sqrt {n}}}$ точки можуть вкласти підмножина в більшості ${\displaystyle {\frac {s(s-1)}{2}}}$ точок сітки, де максимум досягається шляхом організації ${\displaystyle S}$ по діагоналі поруч кут сітки. Тому, для того щоб сформувати розбиття, що відокремлює принаймні ${\displaystyle {\frac {n}{3}}}$ точок з решти сітки, ${\displaystyle s}$ повинно бути принаймні ${\displaystyle {\sqrt {\frac {2n}{3}}}}$, приблизно ${\displaystyle 0.82{\sqrt {n}}}$.

Там є ${\displaystyle n}$-вершині планарні графи (для як завгодно великих значень ${\displaystyle n}$) таке, що для кожного розбиття ${\displaystyle S}$, що ділить залишилися графік в подграфов в більш ніж ${\displaystyle {\frac {2n}{3}}}$ вершин, ${\displaystyle S}$ має принаймні ${\displaystyle {\sqrt {(4\pi {\sqrt {3}})}}{\sqrt {n}}}$ вершини, приблизно ${\displaystyle 1.56{\sqrt {n}}}$. Будівництво включає в себе апроксимації сферу по опуклого багатогранника, змінюючи один з граней багатогранника трикутної сітки, і застосовуючиізопериметричні теореми для поверхні сфери.

Ієрархія розбиття

Розбиття можуть бути об'єднані в  ієрархії розбиття планарного графа, рекурсивного розкладання на більш дрібні графіків. Ієрархія розбиття може бути представлена ​​у вигляді бінарного дерева, в якому кореневий вузол являє саму дану графік, і двоє дітей кореня є корінням рекурсивно побудованих ієрархій розбиття для індукованих подграфов, утворених з двох підмножин ${\displaystyle A}$ і ${\displaystyle B}$ розбиття .

Ієрархія розбиття цього типу формує основу для дерева розбиття даного графа, в якому безліч вершин, пов'язаних з кожним вузлом дерева є об'єднанням розбиття на шляху від цього вузла до кореня дерева. Оскільки розміри графіків спуститися на постійний коефіцієнт на кожному рівні дерева, верхні межі за розмірами розбиття також спуститися на постійний коефіцієнт на кожному рівні, так що розміри розбиття на цих шляхах додати вгеометричній прогресії з ${\displaystyle O({\sqrt {n}})}$. Тобто, розбиття сформована таким чином, має ширину ${\displaystyle O({\sqrt {n}})}$, і може бути використаний, щоб показати, що кожен планарний граф має  ${\displaystyle O({\sqrt {n}})}$.

Побудова ієрархії розбиття безпосередньо, шляхом обходу двійкового дерева зверху вниз і застосування лінійної часу алгоритм планарний роздільник кожної з породжених подграфов, пов'язаних з кожним вузлом двійкового дерева, займе в цілому ${\displaystyle O(n\log(n))}$ часу. Тим не менш, можна побудувати всю ієрархію розбиття в лінійному часу, за допомогою в ширину пошарового підхід Lipton-Тар'я і за допомогою відповідних структур даних, щоб виконувати кожен крок розділу в сублінейного часу. 

Якщо утворює пов'язаний тип ієрархії на основі поділу замість розбиття, в яких двоє дітей кореневого вузла є корені рекурсивно сконструйовані ієрархії для двох подграфов  ${\displaystyle G_{1}}$ та ${\displaystyle G_{2}}$  з відділення даного графа, то загальне Структура формує філіальну-розкладання замість дерева розбиття. Ширина будь-якого поділу в це розкладання, знову ж, обмежений сумою розмірів розбиття на шляху від будь-якого вузла до кореня ієрархії, так що будь-якої гілки-розкладання утворюється таким чином, має ширину ${\displaystyle O({\sqrt {n}})}$ і будь планарний граф має branchwidth ${\displaystyle O({\sqrt {n}})}$. Хоча багато інші проблеми, навіть для планарних графів, можна знайти мінімальний ширини галузевих розкладання планарного графа за поліноміальний час. 

Застосовуючи методи Алон, Сеймур і Томас (1994) більш безпосередньо у будівництві розгалуження розкладань, Фомін & Thilikos (2006a) показують, що кожен планарний граф має branchwidth на найбільш ${\displaystyle 2.12{\sqrt {n}}}$, з тією ж постійною, як один в проста теорема розбиття циклу Алон ін. Оскільки treewidth будь-якого графа не перевищує ${\displaystyle {\frac {3}{2}}}$ його branchwidth, це також показує, що планарні графи treewidth більшою ${\displaystyle 3.18{\sqrt {n}}}$.

Інші класи графів

Деякі рідкісні графіки не мають розбиття сублінейного розміру: в розширювач графіці., Видалення до постійного фракції вершин раніше залишає тільки один зв'язну компоненту 

Можливо, саме раннє відома теорема про розбиття є результатом Йорданії (1869), що будь-яке дерево можна розбити на піддерев не більш ${\displaystyle {\frac {2n}{3}}}$ вершин кожного видаленням однієї вершини. Зокрема, вершина, мінімізує Максимальний розмір компонент володіє цією властивістю, бо, якщо він не зробив, то його сусід по унікальній великий поддерева б сформувати ще більш розділ. Застосовуючи той же метод до дерева розкладання довільного графа, можна показати, що будь граф має роздільник розміру на найбільш дорівнює його treewidth.

Якщо граф ${\displaystyle G}$ не плескатою, але може бути вбудований на поверхні роду ${\displaystyle g}$, тобто розбиття з ${\displaystyle O({\sqrt {gn}})}$^.вершини. Гілберт, Хатчінсон і Тар'я (1984) довести це за допомогою аналогічна Підхід, що і Lipton та Tarjan (1979). Вони група вершини графа в ширину першого рівнів і знайти два рівні видалення якої залишає не більше одного великого компонент, що складається з невеликого числа рівнів. Цей залишився компонент може бути зроблений шляхом видалення планарного ряд завширшки шляхів пропорційних до роду, після чого методом Lipton-Тар'я можуть бути застосовані до залишився планарного графа. Результат випливає з ретельного балансу розміру віддалених двох рівнях в порівнянні з кількістю рівнів між ними. Якщо граф вкладення задається як частина вхідних даних, його роздільник можна знайти в лінійному часу. Графіки роду г також краї розбиття розміру ${\displaystyle O({\sqrt {g\Delta n}})}$.

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

Додатки 

Розділяй і володарюй алгоритми 

Розбиття може бути використання при розробці ефективної розділяй і володарюй алгоритми для вирішення завдань на планарних графів. Як приклад, одна проблема, яка може бути вирішена таким чином, щоб знайти найкоротший цикл у ваговому планарною графа. Це може бути вирішена за допомогою наступних стадій:

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

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

Більш швидкий алгоритм, за тієї ж проблеми короткий цикл, працює в часу ${\displaystyle O(n(\log(n))^{3})}$), було дано Wulff-Нільсен (2009). Його алгоритм використовує той же роздільник на основі розділяй і володарюй структуру, але використовує прості розбиття циклу, а не довільних роздільників, так що вершини ${\displaystyle S}$ належать до однієї особи графіків всередині і зовні розбиття циклу. Потім він замінює ${\displaystyle O({\sqrt {n}})}$ окремих виклику до алгоритму Дейкстри з більш складними алгоритмами, щоб знайти найкоротші шляхи з усіх вершин на одній особі планарного графа і об'єднати відстані від двох подграфов. Для зважених, але неорієнтованих планарних графів, найкоротший цикл еквівалентно мінімальної розрізу в неоднозначному графі і можуть бути знайдені в ${\displaystyle O(n\log \log n)}$ час, і короткий цикл в незваженої неорієнтованого планарного графа (її обхват ) може бути знайдений за час ${\displaystyle O({\sqrt {n}})}$. (Проте, тим швидше алгоритм незважених графах не засновані на теоремі про розбиття .)

Фредріксон був запропонований інший більш швидкий алгоритм для одного джерела найкоротших за реалізації теорему роздільник в планарних графів в 1986 році. Це поліпшення алгоритму Дейкстри з итеративной пошуку по ретельно відібраним підмножини вершин. Ця версія має ${\displaystyle O(n{\sqrt {\log n}})}$ час в n-вершиному графі. Розбиття використовуються, щоб знайти поділ графа, тобто розбиття крайового встановити у двох або більше підмножин, називається регіонах. Вузол називається міститься в області, якщо деякі краю області падає на вузол. Вузол містяться в більш ніж однієї області, називається граничним вузлом областей, що містять його. Метод використовує поняття ${\displaystyle r}$-поділ якості ${\displaystyle n}$-виклик граф, поділ графа в ${\displaystyle O({\frac {n}{r}})}$  областей, кожна з яких містить ${\displaystyle O(r)}$ вузли, включаючи ${\displaystyle O({\sqrt {r}})}$ граничні вузли. Фредеріксон показали, що ${\displaystyle r}$-поділ можна знайти в ${\displaystyle O(n\log(n))}$ від часу рекурсивного застосування теореми про розбиття .

Ескіз його алгоритм вирішення проблеми полягає в наступному.

1. Попередня обробка фаза: Partition графік в ретельно відібраних підмножин вершин і визначити найкоротші шляхи між усіма парами вершин в цих підмножин, де проміжні вершини на цьому шляху, не в підгрупі. Цей етап вимагає планарний граф ${\displaystyle G_{0}}$    перетворитися в ${\displaystyle G}$ з вершиною, що має не більше ніж ступеня 3. З слідства Ейлера формули, число вершин у графі результуючої буде ${\displaystyle n\leq 6n_{0}-12}$, де ${\displaystyle n_{0}}$  є число вершин у ${\displaystyle G_{0}}$. Ця фаза також забезпечує наступні властивості підходящого ${\displaystyle r}$-поділу Відповідний ${\displaystyle r}$-поділу планарного графа є ${\displaystyle r}$-поділ таке, що

• кожна гранична вершина міститься в більш ніж трьох регіонах
• будь-який регіон, який не підключений складається з зв'язкових компонент, кожна з яких розділяють граничні вершини з точно таким же набором з однієї або двох з'єднаних областей.

2. Пошук фаза:

• Основний упор: Знайти Найкоротші відстані від джерела до кожної вершини в підгрупі. Коли вершина ${\displaystyle v}$ в підгрупі закритий, ${\displaystyle d(w)}$ повинні бути оновлені для всіх вершин ${\displaystyle w}$ в підгрупі, так що шлях існує з ${\displaystyle v}$ в ${\displaystyle w}$.
• Зачистки: Визначте найкоротші відстані, щоб кожен залишився вершини.

Henzinger  продовжив Фредеріксон  техніку ${\displaystyle r}$-поділу для одного джерела алгоритму найкоротший шлях в планарних графів для невід'ємних довжин ребер і запропонував лінійного часу алгоритм. Їх метод узагальнює поняття Фредеріксон граф-підрозділів, так що тепер ${\displaystyle (r,s)}$ -розподіл, ${\displaystyle n}$-вузов графа бути поділ на ${\displaystyle O({\frac {n}{r}})}$ поділів, кожен з яких містить  ${\displaystyle r^{O(1)}}$  вузли, кожен з яких має в більшості років граничних вузлів. Якщо ${\displaystyle (r,s)}$ -розподіл повторно розділити на більш дрібні ділянки, які називають отримати рекурсивний поділ. Цей алгоритм використовує приблизно ${\displaystyle \log *n}$ рівнів підрозділів. Рекурсивний поділ представляється кореневого дерева, чиє листя позначені виразним краєм ${\displaystyle G}$. Корінь дерева являє собою область, що складається з повноекранному ${\displaystyle G}$, діти кореня представляють субрегіонів, в якому цей регіон розділений і так далі. Кожен лист (атомна область) являє собою область, що містить точно одне ребро.

Вкладені розсічення є основі поділу розбиття і володарюй зміна Гаусса для вирішення розріджених симетричних систем лінійних рівнянь з планарною структурою графа, такі як ті, що випливають з методу кінцевих елементів. Це включає в себе пошук розбиття для графік, що описує систему рівнянь, рекурсивно виключення змінних в двох підзадач, відокремлених один від одного роздільником, а потім виключення змінних в розбитті . Наповнювач в даного методу (число ненульових коефіцієнтів в результаті розкладання Холецкого матриці) ${\displaystyle O(n\log n)}$,  дозволяє цей метод, щоб бути конкурентоспроможними з ітераційних методів для тих же проблем. 

Клейн, Мозес і Вайман  дав ${\displaystyle O(n\log ^{2}n)}$ -час, алгоритм лінійного простору, щоб знайти самі короткі відстані шлях від ${\displaystyle S}$ до всіх вузлів для спрямованого 2-планарного графа з позитивними і негативними дугових довжинах, що не містять жодного негативного циклів. Їх алгоритм використовує планарні розкладання графа, щоб знайти Жордана ${\displaystyle C}$, який проходить через ${\displaystyle O({\sqrt {n}})}$ вузлів (і не дуг), що між ${\displaystyle {\frac {n}{3}}}$  і ${\displaystyle {\frac {2n}{3}}}$ вузли укладені ${\displaystyle C}$.  Вузли, через який ${\displaystyle C}$ проходи граничні вузлами. Оригінальний графік ${\displaystyle G}$ розділяється на два подграфа ${\displaystyle G_{0}}$   і ${\displaystyle G_{1}}$   шляхом розрізання планарну вкладення уздовж З і дублювання граничні вузли. Для ${\displaystyle i=0}$ та ${\displaystyle 1}$, в ${\displaystyle G_{i}}$   граничні вузли лежать на межі однієї номінальної ${\displaystyle F_{i}}$. 

Огляд їх підходу, наводиться нижче.

• Рекурсивний виклик: Перший етап рекурсивно обчислює відстані від ${\displaystyle r}$ в ${\displaystyle G_{i}}$   для  ${\displaystyle i=0}$ та ${\displaystyle 1}$.
• Intra-частина крайової відстані: Для кожного графа ${\displaystyle G_{i}}$   обчислити всі відстані в ${\displaystyle G_{i}}$   між граничними вузлами. Це займе ${\displaystyle O(n\log n)}$ час.
• Одного джерела між частина граничні відстані: Найкоротший шлях в ${\displaystyle G}$ проходить взад і вперед між ${\displaystyle G_{0}}$   і ${\displaystyle G_{1}}$,  щоб обчислити відстань з ${\displaystyle G}$ до ${\displaystyle r}$ для всіх граничних вузлів. Змінний ітерації використовувати всі крайової відстані в ${\displaystyle \$G_{0}}$   і ${\displaystyle \$G_{1}}$. Число ітерацій ${\displaystyle O({\sqrt {n}})}$, так що загальний час цього етапу виведення  ${\displaystyle O(n{\boldsymbol {\alpha }}(n))}$, де ${\displaystyle {\boldsymbol {\alpha }}(n)}$ є зворотним функції Аккермана.
• Одного джерела між частину відстані: Відстані, розраховані на попередніх етапах використовуються разом з обчисленням Дейкстри в модифікованій версії кожної ${\displaystyle G_{i}}$, для обчислення відстані  з ${\displaystyle G}$ до ${\displaystyle r}$ для всіх вузлів. Цей етап займає ${\displaystyle O(n\log n)}$ час.
• Rerooting відстані одного джерела: Відстані від ${\displaystyle r}$ в ${\displaystyle G}$ перетворюються на невід'ємних довжин, і знову алгоритм Дейкстри використовується для обчислення відстані від ${\displaystyle S}$. Цей етап вимагає ${\displaystyle O(n\log n)}$ час.

Важливою частиною цього алгоритму є використання функцій і ціною Зниження довжини. Для орієнтованого графа ${\displaystyle G}$ з дуги довжини i (·), функція ціни функція ${\displaystyle \varphi }$ з вузлів ${\displaystyle G}$ до речових чисел. Для дугового ${\displaystyle uv}$, приведена довжина по відношенню до ${\displaystyle \varphi }$ ${\displaystyle i\varphi (uv)=i(uv)+\varphi (u)-\varphi (v)}$.

Допустима функція ціни функція ціни, що викликає невід'ємні зменшені довжини всіх дуг ${\displaystyle G}$. Це корисно в перетворенні проблеми найкоротших шляхів за участю позитивні і негативні довжини в одному участю тільки невід'ємні довжини, які потім можуть бути вирішені за допомогою алгоритму Дейкстри.

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

Точне рішення проблем NP-важкі оптимізації 

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

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

Наближені алгоритми 

Ліптон & Тар'я (1980) зауважив, що теорема про розбиття може бути використаний для отримання схем наближення до поліноміального часу для NP-важких задач оптимізації на планарнких графів, таких як знаходження максимального незалежного множини. Зокрема, шляхом усічення ієрархію роздільник на відповідному рівні, можна знайти роздільник розміру ${\displaystyle O({\frac {n}{\sqrt {logn}}})}$ видалення якої ділить графік в подграфов розмір  До теоремі чотирьох кольору, існує незалежне безліч розміру, принаймні ${\displaystyle {\frac {n}{4}}}$, так що віддалені вузли утворюють мізерну частку від максимального незалежного безлічі, а максимальні незалежні множини в інших подграфов можна знайти самостійно в момент експоненціального У їх розміру. Комбінуючи цей підхід з більш пізніми методами лінійної часу на будівництво ієрархії розбиття  і з настільним пошуку, щоб розділити обчислення незалежних наборів між ізоморфних подграфов, це може бути зроблено, щоб побудувати незалежних наборів розміру в межах фактора ${\displaystyle 1-O({\frac {1}{\sqrt {logn}}})}$ оптимальною, в лінійному часу. Тим не менш, для апроксимації співвідношень ще ближче до 1, ніж цей фактор, більш пізньому підході Baker (1994) (на основі деревної декомпозиції, а не на планарних розбиттів) забезпечує кращі компроміси часу в порівнянні з якістю апроксимації.

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

Графік стиснення 

Розбиття були використані як частини стиснення даних алгоритмів для представлення планарних графах та інші віддільні графіки, використовуючи невелику кількість бітів. Основний принцип цих алгоритмів є вибір номер ${\displaystyle k}$ і неодноразово розділити дану планарний граф, використовуючи роздільники в ${\displaystyle O({\frac {n}{k}})}$ подграфов розміру не більше ${\displaystyle k}$, з ${\displaystyle O({\frac {n}{\sqrt {k}}})}$ вершини в розбитті. При відповідному виборі до (не більше пропорційної логарифму від ${\displaystyle n}$) кількість неізоморфних ${\displaystyle n}$-вершивних планарних подграфов значно менше, ніж число подграфов в розкладанні, так що графік може бути стиснутий за допомогою побудови таблиці всі можливі неізоморфних підграфи і представляючи кожен підграф в розкладанні розбиття за його індексом в таблиці. Інша частина графіка, утворений вершинами розбиття, можуть бути представлені в явному вигляді або за допомогою рекурсивного версію тієї ж структури даних. За допомогою цього методу, планарні графи і безліч більш вузьких сімейств планарних графів можуть бути закодовані з використанням числа бітів, яке інформаційно-теоретично оптимальним: якщо є ${\displaystyle P_{n}n}$-вершині графіки в сім'ї графіків, які будуть представлені, то особа Графік в сім'ї можуть бути представлені з використанням тільки ${\displaystyle (1+O(n))\log _{2}P_{n}}$(1 + O (п)) увійти ₂ P _п біт.  Крім того, можна побудувати уявлення цього типу, в якому можна перевірити прилягання між вершинами, визначити ступінь а вершинні і список сусідів вершини в постійне час на запит, шляхом збільшення таблицю подграфов з додаткової таблиці інформації, що представляє відповіді на запити. 

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

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

Будівництво включає в себе посилену форму теореми про розбиття, в якому розмір трьох підмножин вершин в розбитті не залежить від структури графа: існує число ${\displaystyle C}$, величина яких не більше постійна раз ${\displaystyle {\sqrt {n}}}$, наприклад що вершини кожного ${\displaystyle n}$-вершині планарного графа можуть бути розділені на підмножини, ${\displaystyle S}$ і ${\displaystyle B}$, без ребер з до ${\displaystyle B}$, з ${\displaystyle \left\vert S\right\vert =c}$|, і з  ${\displaystyle \left\vert A\right\vert =\left\vert B\right\vert ={\frac {(n-c)}{2}}}$. Це може бути показано за допомогою звичайної форми теореми про розбиття кілька разів, щоб розділити граф, поки всі компоненти розділу не можуть бути організовані у двох підмножин менше, ніж ${\displaystyle {\frac {n}{2}}}$  вершин, а потім рухливих вершин з цих підмножин в розбиття, необхідно до тих пір, поки має заданий розмір.

Після того, як теорема про розбиття цього типу показано, він може бути використаний для отримання ієрархії роздільник для n-вершині планарних графів, що знову не залежить від структури графа: дерево-розкладання, сформований з цієї ієрархії має ширину ${\displaystyle O({\sqrt {n}})}$ і може бути використаний для будь планарного графа. Безліч всіх пар вершин в дереві-розкладання, що обидва належать до загального вузла дерева розкладання утворює тривіально ідеальний графік з ${\displaystyle O(n^{3/2})}$ ${\displaystyle n}$-вершини вершини, які містять всі ${\displaystyle n}$, ${\displaystyle n}$-вершини планарний граф як підграф. Подібна конструкція показує, що обмежена градусів планарні графи мають універсальні графи з ${\displaystyle O(n\log n)}$ краю, де постійна приховані впозначеннях O залежить від ступеня пов'язаного. Будь універсальний графік для планарних графів (або навіть дерев необмеженої ступеня) повинні Ω  ${\displaystyle \Omega (n\log n)}$ краю, але він як і раніше невідомо, чи буде ця нижня межа або ${\displaystyle O(n^{3/2})}$ верхня межа жорсткою для універсальних графах для довільні планарні графи.

Примітки

1. Djidjev, (1982).

Посилання

• Alber, Jochen; Fernau, Henning; Niedermeier, Rolf (2003), Graph separators: A parameterized view, Journal of Computer and System Sciences, 67 (4): 808—832, doi:10.1016/S0022-0000(03)00072-2.
• Alon, Noga; Seymour, Paul; Thomas, Robin (1990), A separator theorem for nonplanar graphs, J. Amer. Math. Soc., 3 (4): 801—808, doi:10.1090/S0894-0347-1990-1065053-0.
• Alon, Noga; Seymour, Paul; Thomas, Robin (1994), Planar separators, SIAM Journal on Discrete Mathematics, 7 (2): 184—193, doi:10.1137/S0895480191198768.
• Arora, Sanjeev; Grigni, Michelangelo; Karger, David; Klein, Philip; Woloszyn, Andrzej (1998), A polynomial-time approximation scheme for weighted planar graph TSP, Proc. 9th ACM-SIAM Symposium on Discrete algorithms (SODA '98), с. 33—41.
• Babai, L.; Chung, F. R. K.; Erdős, P.; Graham, R. L.; Spencer, J. H. (1982), On graphs which contain all sparse graphs, у Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean (ред.), Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday (PDF), Annals of Discrete Mathematics, т. 12, с. 21—26, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Baker, Brenda S. (1994), Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM, 41 (1): 153—180, doi:10.1145/174644.174650.
• Bar-Yehuda, R.; Even, S. (1982), On approximating a vertex cover for planar graphs, Proc. 14th ACM Symposium on Theory of Computing (STOC '82), с. 303—309, doi:10.1145/800070.802205, ISBN 0-89791-070-2.
• Bern, Marshall (1990), Faster exact algorithms for Steiner trees in planar networks, Networks, 20 (1): 109—120, doi:10.1002/net.3230200110.
• Bhatt, Sandeep N.; Chung, Fan R. K.; Leighton, F. T.; Rosenberg, Arnold L. (1989), Universal graphs for bounded-degree trees and planar graphs (PDF), SIAM Journal on Discrete Mathematics, 2 (2): 145, doi:10.1137/0402014, архів оригіналу (PDF) за 5 липня 2017, процитовано 30 грудня 2015.
• Blandford, Daniel K.; Blelloch, Guy E.; Kash, Ian A. (2003), Compact representations of separable graphs, Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA '03) (PDF), с. 679—688, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Blelloch, Guy E.; Farzan, Arash (2010), Succinct representations of separable graphs, у Amir, Amihood; Parida, Laxmi (ред.), Proc. 21st Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, т. 6129, Springer-Verlag, с. 138—150, doi:10.1007/978-3-642-13509-5_13, ISBN 978-3-642-13508-8.
• Chalermsook, Parinya; Fakcharoenphol, Jittat; Nanongkai, Danupon (2004), A deterministic near-linear time algorithm for finding minimum cuts in planar graphs, Proc. 15th ACM–SIAM Symposium on Discrete Algorithms (SODA'04), с. 828—829.
• Chang, Hsien-Chih; Lu, Hsueh-I (2011), Computing the girth of a planar graph in linear time, SIAM Journal on Computing, 42: 1077—1094, arXiv:1104.4892, doi:10.1137/110832033.
• Chiba, Norishige; Nishizeki, Takao; Saito, Nobuji (1981), Applications of the Lipton and Tarjan planar separator theorem (PDF), J. Inform. Process, 4 (4): 203—207, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Chung, Fan R. K. (1990), Separator theorems and their applications, у Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen та ін. (ред.), Paths, Flows, and VLSI-Layout, Algorithms and Combinatorics, т. 9, Springer-Verlag, с. 17–34, ISBN 978-0-387-52685-0.
• Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006), Exact algorithms for the Hamiltonian cycle problem in planar graphs, Operations Research Letters, 34 (3): 269—274, doi:10.1016/j.orl.2005.04.013.
• Diks, K.; Djidjev, H. N.; Sýkora, O.; Vrt'o, I. (1993), Edge separators of planar and outerplanar graphs with applications, Journal of Algorithms, 14 (2): 258—279, doi:10.1006/jagm.1993.1013.
• Djidjev, H. N. (1982), On the problem of partitioning planar graphs, SIAM Journal on Algebraic and Discrete Methods, 3 (2): 229—240, doi:10.1137/0603022.
• Djidjev, Hristo N.; Venkatesan, Shankar M. (1997), Reduced constants for simple cycle graph separation, Acta Informatica, 34 (3): 231—243, doi:10.1007/s002360050082.
• Donath, W. E.; Hoffman, A. J. (1972), Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices, IBM Techn. Disclosure Bull., 15: 938—944. As cited by Spielman та Teng, (2007).
• Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L.; Fomin, Fedor V. (2005), Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions, Proc. 13th European Symposium on Algorithms (ESA '05), Lecture Notes in Computer Science, т. 3669, Springer-Verlag, с. 95—106, doi:10.1007/11561071_11, ISBN 978-3-540-29118-3.
• Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. (1996), Separator based sparsification. I. Planarity testing and minimum spanning trees, Journal of Computer and System Sciences, 52 (1): 3—27, doi:10.1006/jcss.1996.0002.
• Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Spencer, Thomas H. (1998), Separator-based sparsification. II. Edge and vertex connectivity, SIAM Journal on Computing, 28: 341, doi:10.1137/S0097539794269072.
• Eppstein, David; Miller, Gary L.; Teng, Shang-Hua (1995), A deterministic linear time algorithm for geometric separators and its applications, Fundamenta Informaticae, 22 (4): 309—331, архів оригіналу за 3 березня 2016, процитовано 30 грудня 2015.
• Erdős, Paul; Graham, Ronald; Szemerédi, Endre (1976), On sparse graphs with dense long paths, Computers and mathematics with applications (PDF), Oxford: Pergamon, с. 365—369, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Fiedler, Miroslav (1973), Algebraic connectivity of graphs, Czechoslovak Math. J., 23 (98): 298—305. As cited by Spielman та Teng, (2007).
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2006a), New upper bounds on the decomposability of planar graphs (PDF), Journal of Graph Theory, 51 (1): 53—81, doi:10.1002/jgt.20121, архів оригіналу (PDF) за 5 липня 2017, процитовано 30 грудня 2015.
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2006b), Dominating sets in planar graphs: branch-width and exponential speed-up, SIAM Journal on Computing, 36 (2): 281, doi:10.1137/S0097539702419649.
• Frieze, Alan; Miller, Gary L.; Teng, Shang-Hua (1992), Separator based parallel divide and conquer in computational geometry, Proc. 4th ACM Symposium on Parallel Algorithms and Architecture (SPAA '92) (PDF), с. 420—429, doi:10.1145/140901.141934, ISBN 0-89791-483-X, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Gazit, Hillel; Miller, Gary L. (1990), Planar separators and the Euclidean norm, Proc. International Symposium on Algorithms (SIGAL'90) (PDF), Lecture Notes in Computer Science, т. 450, Springer-Verlag, с. 338—347, doi:10.1007/3-540-52921-7_83, ISBN 978-3-540-52921-7, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• George, J. Alan (1973), Nested dissection of a regular finite element mesh, SIAM Journal on Numerical Analysis, 10 (2): 345—363, doi:10.1137/0710032, JSTOR 2156361.
• Gilbert, John R.; Hutchinson, Joan P.; Tarjan, Robert E. (1984), A separator theorem for graphs of bounded genus, Journal of Algorithms, 5 (3): 391—407, doi:10.1016/0196-6774(84)90019-1.
• Gilbert, John R.; Tarjan, Robert E. (1986), The analysis of a nested dissection algorithm, Numerische Mathematik, 50 (4): 377—404, doi:10.1007/BF01396660.
• Goodrich, Michael T. (1995), Planar separators and parallel polygon triangulation, Journal of Computer and System Sciences, 51 (3): 374—389, doi:10.1006/jcss.1995.1076.
• Gremban, Keith D.; Miller, Gary L.; Teng, Shang-Hua (1997), Moments of inertia and graph separators (PDF), Journal of Combinatorial Optimization, 1 (1): 79—104, doi:10.1023/A:1009763020645, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Har-Peled, Sariel (2011), A Simple Proof of the Existence of a Planar Separator, arXiv:1105.0103.
• He, Xin; Kao, Ming-Yang; Lu, Hsueh-I (2000), A fast general methodology for information-theoretically optimal encodings of graphs, SIAM Journal on Computing, 30 (3): 838—846, doi:10.1137/S0097539799359117.
• Holzer, Martin; Schulz, Frank; Wagner, Dorothea; Prasinos, Grigorios; Zaroliagis, Christos (2009), Engineering planar separator algorithms, Journal of Experimental Algorithmics, 14: 1.5—1.31, doi:10.1145/1498698.1571635, архів оригіналу за 6 березня 2012, процитовано 30 грудня 2015.
• Jordan, Camille (1869), Sur les assemblages des lignes, Journal für die reine und angewandte Mathematik, 70: 185—190, As cited by Miller та ін., (1997), архів оригіналу за 27 червня 2015, процитовано 30 грудня 2015.
• Kawarabayashi, Ken-Ichi; Reed, Bruce (2010), A separator theorem in minor-closed classes, Proc. 51st Annual IEEE Symposium on. Foundations of Computer Science.
• Klein, Philip; Rao, Satish; Rauch, Monika; Subramanian, Sairam (1994), Faster shortest-path algorithms for planar graphs, Proc. 26th ACM Symposium on Theory of Computing (STOC '94), с. 27—37, doi:10.1145/195058.195092, ISBN 0-89791-663-8.
• Łącki, Jakub; Sankowski, Piotr (2011), Min-Cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time, Proc. 19th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, т. 6942, Springer-Verlag, с. 155—166, arXiv:1104.4890, doi:10.1007/978-3-642-23719-5_14, ISBN 978-3-642-23718-8.
• Lipton, Richard J.; Rose, Donald J.; Tarjan, Robert E. (1979), Generalized nested dissection, SIAM Journal on Numerical Analysis, 16 (2): 346—358, doi:10.1137/0716027, JSTOR 2156840.
• Lipton, Richard J.; Tarjan, Robert E. (1979), A separator theorem for planar graphs, SIAM Journal on Applied Mathematics, 36 (2): 177—189, doi:10.1137/0136016.
• Lipton, Richard J.; Tarjan, Robert E. (1980), Applications of a planar separator theorem, SIAM Journal on Computing, 9 (3): 615—627, doi:10.1137/0209046.
• Miller, Gary L. (1986), Finding small simple cycle separators for 2-connected planar graphs (PDF), Journal of Computer and System Sciences, 32 (3): 265—279, doi:10.1016/0022-0000(86)90030-9, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997), Separators for sphere-packings and nearest neighbor graphs, J. ACM, 44 (1): 1—29, doi:10.1145/256292.256294.
• Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1998), Geometric separators for finite-element meshes, SIAM Journal on Scientific Computing, 19 (2): 364—386, doi:10.1137/S1064827594262613.
• Pach, János; Agarwal, Pankaj K. (1995), Lipton–Tarjan Separator Theorem, Combinatorial Geometry, John Wiley & Sons, с. 99—102.
• Papadimitriou, C. H.; Sideri, M. (1996), The bisection width of grid graphs, Theory of Computing Systems, 29 (2): 97—110, doi:10.1007/BF01305310.
• Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), Shallow excluded minors and improved graph decompositions, Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA '94), с. 462—470.
• Reed, Bruce; Wood, David R. (2009), A linear-time algorithm to find a separator in a graph excluding a minor, ACM Transactions on Algorithms, 5 (4): 1—16, doi:10.1145/1597036.1597043.
• Seymour, Paul D.; Thomas, Robin (1994), Call routing and the ratcatcher, Combinatorica, 14 (2): 217—241, doi:10.1007/BF01215352.
• Smith, Warren D.; Wormald, Nicholas C. (1998), Geometric separator theorems & applications, 39th Annual Symposium on Foundations of Computer Science (FOCS '98), November 8-11, 1998, Palo Alto, California, USA, IEEE Computer Society, с. 232—243, doi:10.1109/SFCS.1998.743449.
• Spielman, Daniel A.; Teng, Shang-Hua (1996), Disk packings and planar separators, Proc. 12th ACM Symposium on Computational Geometry (SCG '96) (PDF), с. 349—358, doi:10.1145/237218.237404, ISBN 0-89791-804-5, архів оригіналу (PDF) за 3 березня 2016, процитовано 30 грудня 2015.
• Spielman, Daniel A.; Teng, Shang-Hua (2007), Spectral partitioning works: Planar graphs and finite element meshes, Linear Algebra and its Applications, 421 (2–3): 284—305, doi:10.1016/j.laa.2006.07.020.
• Sýkora, Ondrej; Vrt'o, Imrich (1993), Edge separators for graphs of bounded genus with applications, Theoretical Computer Science, 112 (2): 419—429, doi:10.1016/0304-3975(93)90031-N.
• Tazari, Siamak; Müller-Hannemann, Matthias (2009), Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Discrete Applied Mathematics, 157 (4): 673—684, doi:10.1016/j.dam.2008.08.002.
• Ungar, Peter (1951), A theorem on planar graphs, Journal of the London Mathematical Society, 1 (4): 256, doi:10.1112/jlms/s1-26.4.256.
• Weimann, Oren; Yuster, Raphael (2010), Computing the girth of a planar graph in O(n log n) time, SIAM Journal on Discrete Mathematics, 24 (2): 609, doi:10.1137/090767868.
• Wulff-Nilsen, Christian (2009), Girth of a planar digraph with real edge weights in O(n log^3n) time, arXiv:0908.0697.