Planaritetsproblemet er det algoritmiske problem med at kontrollere, om en given graf er plan (det vil sige, om den kan tegnes på et plan uden at krydse kanter). Problemet er velundersøgt inden for datalogi, og mange praktiske algoritmer er blevet opfundet til det , hvoraf mange bruger moderne datastrukturer . De fleste af disse metoder kører i O( n ) tid (lineær tid), hvor n er antallet af kanter (eller hjørner) af grafen, som er en asymptotisk optimal algoritme . I stedet for en simpel boolsk værdi kan outputtet af planaritetskontrolalgoritmer give en grafindlejring, hvis grafen er plan, eller en planaritetssikring, såsom en Kuratowski-undergraf , hvis grafen ikke er plan.
Planaritetstestalgoritmer bruger normalt grafteoretiske teoremer, der beskriver sættet af plane grafer i termer, der er uafhængige af graftegning. Dette omfatter
De Fraisex-Rosenstil planaritetskriteriet kan bruges direkte som en del af planaritetstestalgoritmen, mens Kuratowski- og Wagner-sætningerne anvendes indirekte - hvis algoritmen kan finde en kopi af K 5 eller K 3,3 i en given graf, kan være sikker på, at inputgrafen ikke er plan
Andre planaritetskriterier, der beskriver plane grafer matematisk, men som er mindre egnede til planaritetstestalgoritmer, omfatter Whitneys planaritetskriterium , at en graf er plan, hvis og kun hvis dens grafmatroide også er cograph, McLanes planaritetskriterium , som beskriver plane grafer efter baser. af deres cykliske rum , Schneiders sætning , som beskriver plane grafer med rækkefølgedimensionen tilhørende delvist ordnede mængder , og Colin de Verdières kriterium for planaritet , ved hjælp af spektralgrafteori .
Den første publicerede (i 1974) planaritetskontrolalgoritme var Hopcroft og Tarjans klassiske vejadditionsmetode [1] , som kørte i lineær tid. Implementeringen af Hopcroft og Tarjans algoritme er inkluderet i biblioteket af effektive datatyper og algoritmer Mehlhorn , Muzel og Neher [2] [3] [4] . I 2012 udvidede Taylor [5] denne algoritme til at generere alle permutationer af cykliske kantordrer til indlejring af dobbeltforbundne komponenter.
En metode til at tilføje toppunkter ved at skabe en datastruktur, der repræsenterer de mulige indlejringer af en given grafs genererede undergraf og tilføje toppunkter en ad gangen til denne datastruktur. Disse metoder begyndte med den ineffektive O( n 2 ) metode foreslået af Lempel , Ewen og Zederbaum i 1967 [6] . Metoden blev forbedret af Ewen og Tarjan, som fandt en lineær tidsløsning til trin s , t -nummerering [7] , og derefter forbedret af Booth og Luker, som udviklede PQ-træets datastruktur . Med disse forbedringer blev metoden lineær med tiden og begyndte i praksis at virke hurtigere end metoden med at tilføje stier [8] . Denne metode er også blevet udvidet til effektivt at beregne plan indlejring (tegning) for plane grafer [9] . I 1999 forenklede Shi og Xu disse metoder ved at bruge et PC-træ (en ikke-rodfæstet version af PQ-træet) og en forsinket vertex -trægennemgang med dybde-først søgning [10] .
I 2004 udviklede Boyer og Myhrvold [11] en forenklet algoritme med køretid O( n ), som var inspireret af PQ-træmetoden, men hvor PQ-træet blev kasseret og algoritmen bruger kantaddition til at beregne en plan indlejring, hvis det er muligt. Ellers beregnes Kuratowski-underinddelingen (enten K 5 - grafen eller K 3,3 -grafen ). Metoden er en af to eksisterende algoritmer (den anden er de Freisex, de Mendes og Rosenstiel [12] [13] planaritetskontrolalgoritmen ). Se Boyer, Cortese, Patrignami og Battista [14] for en eksperimentel sammenligning med en foreløbig version af Boyer og Myhrvolds planaritetskontrolalgoritme. Samtidig blev Boyer og Myhrvold-verifikationsalgoritmen udvidet til at udtrække flere underafdelinger af Kuratovs ikke-planære inputgraf med køretid lineært afhængig af outputstørrelsen [15] . Kildekoderne til planaritetskontrollen [16] [17] og udvælgelsen af flere Kuratovsky-underafdelinger [16] er i det offentlige domæne (i C++). En algoritme, der bestemmer Kuratowski-undergrafen i tid lineært i antallet af hjørner, blev udviklet af Williamson i 1980'erne [18] .
En anden metode bruger konstruktionen af 3-forbundne grafer ved induktion til sekventielt at konstruere en plan indlejring af enhver 3-forbundet komponent af grafen G (og derfor en plan indlejring af grafen G selv ) [19] . Konstruktionen starter fra K 4 og er defineret således, at enhver mellemgraf på vej til den komplette komponent igen er 3-forbundet. Da sådanne grafer har en enkelt indlejring (op til valget af en ydre flade), skal den næste større graf, hvis den forbliver plan, være en forfining af den foregående graf. Dette reducerer planaritetstesten til blot at kontrollere, om den næste tilføjede kant vil have begge ender på ydersiden af den aktuelle indlejring. Da den er konceptuelt meget enkel (og den giver en lineær køretid), har metoden en del kompleksitet i at finde konstruktionsrækkefølgen.