Planaritetsproblemet är det algoritmiska problemet att kontrollera om en given graf är plan (det vill säga om den kan ritas på ett plan utan att korsa kanter). Problemet är väl studerat inom datavetenskap och många praktiska algoritmer har uppfunnits för det , varav många använder moderna datastrukturer . De flesta av dessa metoder körs i O( n ) tid (linjär tid), där n är antalet kanter (eller hörn) på grafen, vilket är en asymptotiskt optimal algoritm . Istället för ett enkelt booleskt värde kan utdata från planaritetskontrollerande algoritmer ge en grafinbäddning om grafen är plan, eller en planaritetssäkring som en Kuratowski-subgraf om grafen inte är plan.
Algoritmer för planaritetstestning använder vanligtvis grafteoretiska teorem som beskriver uppsättningen plana grafer i termer som är oberoende av grafritning. Detta inkluderar
De Fraisex-Rosenstil planaritetskriteriet kan användas direkt som en del av planaritetstestalgoritmen, medan Kuratowski- och Wagner-satserna tillämpas indirekt - om algoritmen kan hitta en kopia av K 5 eller K 3,3 i en given graf, en kan vara säker på att ingångsgrafen inte är plan
Andra planaritetskriterier som beskriver plana grafer matematiskt, men som är mindre lämpliga för planaritetstestningsalgoritmer, inkluderar Whitneys planaritetskriterium , att en graf är plan om och endast om dess grafmatroid också är kograf, McLanes planaritetskriterium , som beskriver plana grafer med baser av deras cykliska utrymmen , Schneiders sats , som beskriver plana grafer med ordningsdimensionen tillhörande partiellt ordnade uppsättningar , och Colin de Verdières kriterium för planaritet , med hjälp av spektralgrafteori .
Den första publicerade (1974) planaritetskontrollalgoritmen var Hopcroft och Tarjans klassiska vägadditionsmetod [1] , som kördes i linjär tid. Implementeringen av Hopcroft och Tarjans algoritm ingår i biblioteket av effektiva datatyper och algoritmer Mehlhorn , Muzel och Neher [2] [3] [4] . 2012 utökade Taylor [5] denna algoritm för att generera alla permutationer av cykliska kantorder för inbäddning av dubbelkopplade komponenter.
En metod för att lägga till hörn genom att skapa en datastruktur som representerar möjliga kapslingar av en given grafs genererade subgraf och lägga till hörn en i taget till denna datastruktur. Dessa metoder började med den ineffektiva O( n2 )-metoden som föreslogs av Lempel , Ewen och Zederbaum 1967 [6] . Metoden förbättrades av Ewen och Tarjan, som hittade en linjär tidslösning för steg s , t -numrering [7] , och sedan förbättrades av Booth och Luker, som utvecklade PQ-trädets datastruktur . Med dessa förbättringar blev metoden linjär med tiden och började i praktiken fungera snabbare än metoden att lägga till banor [8] . Denna metod har också utökats för att effektivt beräkna plan inbäddning (ritning) för plana grafer [9] . 1999 förenklade Shi och Xu dessa metoder genom att använda ett PC-träd (en icke-rotad version av PQ-trädet) och en fördröjd vertex -tree- traversal med djup-först-sökning [10] .
2004 utvecklade Boyer och Myhrvold [11] en förenklad algoritm med körtid O( n ), som var inspirerad av PQ-trädmetoden, men där PQ-trädet kasserades och algoritmen använder kantaddition för att beräkna en plan inbäddning, om möjligt. I annat fall beräknas Kuratowski-indelningen (antingen K 5 -grafen eller K 3,3- grafen ). Metoden är en av två för närvarande existerande algoritmer (den andra är de Freisex, de Mendes och Rosenstiel [12] [13] planaritetskontrollalgoritm ). Se Boyer, Cortese, Patrignami och Battista [14] för en experimentell jämförelse med en preliminär version av Boyer och Myhrvolds planaritetskontrollerande algoritm. Samtidigt utökades Boyer och Myhrvolds verifieringsalgoritm för att extrahera flera underavdelningar av Kuratovs icke-planära ingångsgraf med körtid linjärt beroende på utdatastorleken [15] . Källkoderna för planaritetskontrollen [16] [17] och urvalet av flera Kuratovsky-underavdelningar [16] är offentliga (i C++). En algoritm som bestämmer Kuratowski-subgrafen i tiden linjärt i antalet hörn utvecklades av Williamson på 1980 -talet [18] .
En annan metod använder konstruktionen av 3-kopplade grafer genom induktion för att sekventiellt konstruera en plan inbäddning av valfri 3-kopplad komponent av grafen G (och därför en plan inbäddning av själva grafen G ) [19] . Konstruktionen utgår från K 4 och är definierad på så sätt att varje mellangraf på vägen till hela komponenten återigen är 3-kopplad. Eftersom sådana grafer har en enda inbäddning (upp till valet av en yttre yta), måste nästa större graf, om den förblir plan, vara en förfining av föregående graf. Detta reducerar planaritetstestet till att helt enkelt kontrollera om nästa tillagda kant kommer att ha båda ändarna på utsidan av den aktuella kapslingen. Eftersom den är konceptuellt mycket enkel (och ger en linjär körtid), har metoden mycket komplexitet när det gäller att hitta konstruktionssekvensen.