У теорији графова, тестирање планарности је алгоритмички проблем испитивања да ли је дати граф планарни граф (то јест, да ли се може нацртати у равни без укрштања ивица). Ово је добро истражен проблем у информатици за који су се појавили многи практични Алгоритам, многи користећи нове структура података . Већина ових метода се извршава у О (n) времену (линеарно време), где је n број ивица (или чворова) на графику, који је асимптотски оптималан. Уместо да само буде једна тачно-нетачна вредност, излаз од алгоритма планарног тестирања може бити уградња планарног графа, уколико граф је планаран, или препрека планарности попут Куратовски подграфа ако није.

Критеријуми планарности Тестирање планарности алгоритама обично користи теореме из теорије графова које карактеришу скуп планарних графова у смислу да су независни од цртежа графа.

Ово укључује Теорема Куратовског да је граф планаран ако и само ако не садржи подграф који је потподела од К 5 (комплетан граф од пет чворова) или К 3,3 (комплетан бипартитиван граф са шест чворова, од којих су три чвора повезана са друга три чвора). Теорема Вагнера да је граф планаран ако и само ако не садржи минор (подграф контракције) који је изоморфан са К 5 или К 3,3 . Фрајсикс-Росенстил критеријум планарности, карактерише планарне графове у смислу лево-десне оријентације чворова код претраге у дубину стабла.

Фрајсикс-Росенстил критеријум планарности се може директно користити као део алгоритама за тестирање планарности, док Куратовскијеве и Вагнерове теореме имају индиректне додатке: ако алгоритам може наћи примерак К 5 или К 3,3 у оквиру датог графа, може бити сигуран да улазни граф није планаран и вратити се без даљег рачунања.

Алгоритми Метода додавања путева Класична метода додавања путева Хопкрофта и Тарјана је први објављени алгоритам за планарно тестирање који се извршавао за линеарно време 1974. године.

Метода додавања врха Методе за додавање врха раде на принципу одржавања структуре података која представља могућа уграђивања у индуковани подграф датог графа и додавање чворова један по један на ове структуре података. Ове методе почињу са неефикасном О (n 2 ) методом коју је осмислио Лемпел, Евен и Цедербаум 1967. године. Њу су побољшали Евен и Тарјан, који су пронашли линеарно временско решење за s,t- нумерисаних корака, и Бут. И Луекер, који су развили структуру података-PQ стабло. Са овим побољшањима линеарно-временско је и превазилази методу додавања путева у пракси. стр. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms.” Ова метода је такође проширена да би омогућила да се планарно уграћивање(цртање) ефикасно извршава за планарни граф 1999. Схих и Хсу су поједноставили ове методе помоћу PC стабла (бескоренске варијанте PQ стабла).

Метода додавања ивице 2004. године, Бојер и Мирволд су развили поједностављени О(n) алгоритам, првобитно инспирисан PQ методом стабла, који се ослобађа PQ стабла и користи додавање ивица за планарно уграђивање, ако је то могуће. У супротном, извршава се Куратовски потподела (или К 5 или К 3,3 ). Ово је дан-данас један од два најнапреднија алгоритма (други је алгоритам за планарно тестирање који је направио Fraysseix, de Mendez and Rosenstiehl).. Видети за експериментално поређење са прелиминарном верзијом Боиер и Мирволдовог тестирања планарности. Осим тога, Бојер-Мирволд тест је побољшан да може да издвоји више Куратовски подграфова из непланарног улазног графа у времену које је линеарно зависно од излазног формата. Изворни код за тест планарностиOGDF - Open Graph Drawing Framework: startBoost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0 и проналажење више Куратовски подгрупа је доступан јавности. Алгоритме који проналазе Куратовски подграф у линеарном времену од темена је изумео Williamson 1980.

Референце

Литература

Категорија:Планарни графови Категорија:Графовски алгоритми Категорија:Рачунарски проблеми у теорији графова