Problém rovinnosti je algoritmický problém kontroly, zda je daný graf rovinný (to znamená, zda jej lze nakreslit v rovině bez křížení hran). Tento problém je dobře prostudován v informatice a bylo pro něj vynalezeno mnoho praktických algoritmů , z nichž mnohé využívají moderní datové struktury . Většina těchto metod běží v čase O( n ) (lineárním čase), kde n je počet hran (nebo vrcholů) grafu, což je asymptoticky optimální algoritmus . Místo jednoduché booleovské hodnoty může výstup algoritmů pro kontrolu planarity poskytnout vložení grafu , pokud je graf rovinný, nebo zajištění rovinnosti, jako je Kuratowskiho podgraf , pokud graf rovinný není.
Algoritmy testování rovinnosti obvykle používají teorémy teorie grafů, které popisují množinu rovinných grafů v pojmech, které jsou nezávislé na kreslení grafu. To zahrnuje
De Fraisexovo-Rosenstilovo kritérium rovinnosti lze použít přímo jako součást algoritmu testu rovinnosti, zatímco Kuratowského a Wagnerova věta se aplikuje nepřímo – pokud algoritmus dokáže najít kopii K 5 nebo K 3,3 v daném grafu, můžete si být jisti, že vstupní graf není rovinný
Mezi další kritéria rovinnosti, která popisují rovinné grafy matematicky, ale která jsou méně vhodná pro algoritmy testování rovinnosti, patří Whitneyho kritérium rovinnosti , že graf je rovinný právě tehdy, když je jeho matroid grafu také cograph, McLaneovo kritérium rovinnosti , které popisuje rovinné grafy pomocí základen. jejich cyklických prostorů , Schneiderova věta , která popisuje rovinné grafy s uspořádanou dimenzí sdružených částečně uspořádaných množin , a Colin de Verdièreovo kritérium pro rovinnost využívající spektrální teorii grafů .
První publikovaný (v roce 1974) algoritmus kontroly planarity byl Hopcroftův a Tarjanův klasický způsob sčítání cest [1] , který běžel v lineárním čase. Implementace Hopcroftova a Tarjanova algoritmu je zahrnuta v knihovně efektivních datových typů a algoritmů Mehlhorn , Muzel a Neher [2] [3] [4] . V roce 2012 Taylor [5] rozšířil tento algoritmus o generování všech permutací řádů cyklických hran pro vkládání dvojitě spojených komponent.
Metoda přidávání vrcholů vytvořením datové struktury představující možné vnoření podgrafu vygenerovaného daného grafu a přidáváním vrcholů jeden po druhém do této datové struktury. Tyto metody začaly neefektivní metodou O( n 2 ), kterou navrhli Lempel , Ewen a Zederbaum v roce 1967 [6] . Metodu vylepšili Ewen a Tarjan, kteří našli lineární časové řešení pro krok s , t -číslování [7] , a poté ji zlepšili Booth a Luker, kteří vyvinuli datovou strukturu PQ-tree . Díky těmto vylepšením se metoda stala v čase lineární a v praxi začala fungovat rychleji než metoda sčítání cest [8] . Tato metoda byla také rozšířena pro efektivní výpočet rovinného vnoření (kreslení) pro rovinné grafy [9] . V roce 1999 Shi a Xu zjednodušili tyto metody použitím PC-stromu (nerootovaná verze PQ-stromu) a zpožděného procházení vertexovým stromem s prohledáváním do hloubky [10] .
V roce 2004 Boyer a Myhrvold [11] vyvinuli zjednodušený algoritmus s dobou běhu O( n ), který byl inspirován metodou stromu PQ, ale ve kterém byl strom PQ zahozen a algoritmus používá sčítání hran pro výpočet rovinného vnoření, Pokud možno. V opačném případě se vypočítá Kuratowského poddělení (buď graf K 5 nebo graf K 3,3 ). Metoda je jedním ze dvou aktuálně existujících algoritmů (druhým je de Freisex, de Mendes a Rosenstiel [12] [13] algoritmus kontroly planarity ). Viz Boyer, Cortese, Patrignami a Battista [14] pro experimentální srovnání s předběžnou verzí Boyerova a Myhrvoldova algoritmu kontroly planarity. Zároveň byl Boyerův a Myhrvoldův ověřovací algoritmus rozšířen o extrahování několika poddělení Kuratovova neplanárního vstupního grafu s dobou běhu lineárně závislou na velikosti výstupu [15] . Zdrojové kódy pro kontrolu planarity [16] [17] a výběr několika Kuratovského pododdílů [16] jsou ve veřejné doméně (v C++). Algoritmus, který určuje Kuratowského podgraf v čase lineární v počtu vrcholů, byl vyvinut Williamsonem v 80. letech [18] .
Jiná metoda využívá konstrukci 3-souvislých grafů indukcí k sekvenčnímu sestrojení rovinného vnoření libovolné 3-souvislé složky grafu G (a tedy rovinného vnoření samotného grafu G ) [19] . Konstrukce začíná od K 4 a je definována tak, že jakýkoli mezigraf na cestě ke kompletní součásti je opět 3-souvislý. Protože takové grafy mají jediné vložení (až do výběru vnější plochy), další větší graf, pokud zůstane rovinný, musí být upřesněním předchozího grafu. To redukuje test rovinnosti na jednoduchou kontrolu, zda další přidaná hrana bude mít oba konce na vnější ploše aktuálního vnoření. Vzhledem k tomu, že metoda je koncepčně velmi jednoduchá (a poskytuje lineární dobu běhu), je velmi složitá při hledání konstrukční sekvence.