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

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-повна для довільних планарних графів, і вони показують, що складність проблеми полягає в тому ж, для мережевих графіків з довільним числом отворів, так і для довільних планарних графів.

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

• 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-важкі задачі оптимізації може бути вирішена за час експоненціального в ${\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})}$ верхня межа жорсткою для універсальних графах для довільні планарні графи.