Problema planarității este problema algoritmică de a verifica dacă un graf dat este plan (adică dacă poate fi desenat pe un plan fără margini încrucișate). Problema este bine studiată în informatică și pentru aceasta au fost inventați mulți algoritmi practici , dintre care mulți folosesc structuri moderne de date . Cele mai multe dintre aceste metode rulează în timp O( n ) (timp liniar), unde n este numărul de muchii (sau vârfuri) ale graficului, care este un algoritm optim asimptotic . În loc de o valoare booleană simplă, rezultatul algoritmilor de verificare a planarității poate produce o încorporare a graficului dacă graficul este plan sau o acoperire a planarității, cum ar fi un subgraf Kuratowski , dacă graficul nu este plan.
Algoritmii de testare a planarității folosesc de obicei teoreme de teoria grafurilor care descriu setul de grafuri plane în termeni care sunt independenți de desenarea grafurilor. Aceasta include
Criteriul de planaritate De Fraisex-Rosenstil poate fi utilizat direct ca parte a algoritmului de testare a planarității, în timp ce teoremele Kuratowski și Wagner sunt aplicate indirect - dacă algoritmul poate găsi o copie a lui K 5 sau K 3,3 într-un grafic dat, unul poate fi sigur că graficul de intrare nu este plan
Alte criterii de planaritate care descriu graficele planare din punct de vedere matematic, dar care sunt mai puțin potrivite pentru algoritmii de testare a planarității, includ criteriul de planaritate al lui Whitney , că un grafic este planar dacă și numai dacă matroida sa de grafic este și cograf, criteriul de planaritate al lui McLane , care descrie graficele plane după baze a spațiilor lor ciclice , Teorema lui Schneider , care descrie grafuri plane cu dimensiunea de ordine mulțimilor parțial ordonate asociate , și criteriul de planaritate al lui Colin de Verdière , folosind teoria grafurilor spectrale .
Primul algoritm de verificare a planarității publicat (în 1974) a fost metoda clasică de adăugare a căilor a lui Hopcroft și Tarjan [1] , care a rulat în timp liniar. Implementarea algoritmului lui Hopcroft și Tarjan este inclusă în biblioteca de tipuri de date efective și algoritmi Mehlhorn , Muzel și Neher [2] [3] [4] . În 2012, Taylor [5] a extins acest algoritm pentru a genera toate permutările ordinelor ciclice ale muchiilor pentru încorporarea componentelor dublu conectate.
O metodă de adăugare a nodurilor prin crearea unei structuri de date reprezentând imbricațiile posibile ale subgrafului generat de un graf dat și adăugarea de vârfuri pe rând la această structură de date. Aceste metode au început cu metoda ineficientă O( n 2 ) propusă de Lempel , Ewen și Zederbaum în 1967 [6] . Metoda a fost îmbunătățită de Ewen și Tarjan, care au găsit o soluție de timp liniară pentru pasul s , t -numbering [7] , iar apoi îmbunătățită de Booth și Luker, care au dezvoltat structura de date PQ-tree . Odată cu aceste îmbunătățiri, metoda a devenit liniară în timp și, în practică, a început să funcționeze mai repede decât metoda de adăugare a căilor [8] . Această metodă a fost, de asemenea, extinsă pentru a calcula eficient încorporarea plană (desen) pentru graficele plane [9] . În 1999, Shi și Xu au simplificat aceste metode utilizând un arbore PC (o versiune fără rădăcină a arborelui PQ) și o traversare întârziată a arborelui de vârf cu căutarea depth-first [10] .
În 2004, Boyer și Myhrvold [11] au dezvoltat un algoritm simplificat cu timp de rulare O( n ), care a fost inspirat de metoda arborelui PQ, dar în care arborele PQ a fost aruncat și algoritmul folosește adăugarea marginilor pentru a calcula o încorporare plană, dacă este posibil. În caz contrar, se calculează subdiviziunea Kuratowski (fie graficul K 5 , fie graficul K 3,3 ). Metoda este unul dintre cei doi algoritmi existenți în prezent (celălalt este algoritmul de verificare a planarității de Freisex, de Mendes și Rosenstiel [12] [13] ). Vezi Boyer, Cortese, Patrignami și Battista [14] pentru o comparație experimentală cu o versiune preliminară a algoritmului de verificare a planarității lui Boyer și Myhrvold. În același timp, algoritmul de verificare Boyer și Myhrvold a fost extins pentru a extrage mai multe subdiviziuni ale graficului de intrare neplanar Kuratov cu timpul de rulare dependent liniar de mărimea ieșirii [15] . Codurile sursă pentru verificarea planarității [16] [17] și selecția mai multor subdiviziuni Kuratovsky [16] sunt în domeniul public (în C++). Un algoritm care determină subgraful Kuratowski în timp liniar în numărul de vârfuri a fost dezvoltat de Williamson în anii 1980 [18] .
O altă metodă folosește construcția de grafuri 3-conectate prin inducție pentru a construi secvenţial o încorporare plană a oricărei componente 3-conectate a graficului G (și prin urmare o încorporare plană a graficului G însuși ) [19] . Construcția începe de la K 4 și este definită în așa fel încât orice grafic intermediar pe drumul către componenta completă să fie din nou 3-conectat. Deoarece astfel de grafice au o singură încorporare (până la alegerea unei fețe exterioare), următorul grafic mai mare, dacă rămâne plan, trebuie să fie o rafinare a graficului anterior. Acest lucru reduce testul de planaritate la simpla verificare dacă următoarea muchie adăugată va avea ambele capete pe fața exterioară a cuibării curente. Fiind foarte simplă din punct de vedere conceptual (și oferă un timp de rulare liniar), metoda are multă complexitate în găsirea secvenței de construcție.