En plan täckning av en finit graf G är en finit täckande graf av G som är en plan graf . Varje graf som kan bäddas in i det projektiva planet har ett plant lock. Seiya Negamis olösta gissningar säger att endast dessa grafer har plana omslag [1] .
Förekomsten av en plan täckning är en egenskap som är stängd under minderåriga [2] , och kan därför beskrivas av ett ändligt antal förbjudna minderåriga , men den exakta uppsättningen av förbjudna minderåriga är inte känd. Av samma skäl finns det en polynomtidsalgoritm för att testa om en given graf har en plan täckning, men ingen explicit beskrivning av denna algoritm är känd.
En täckande mappning från en graf C till en annan graf H kan beskrivas med en funktion f från hörnen av C till hörnen på H , som för varje vertex v i C skapar en bijektion mellan grannskapet av v och grannskapet av f ( v ) [3] . Om H är en sammankopplad graf måste varje vertex av H ha samma antal hörn i förbilden av C [2] . Detta nummer kallas antalet lager på kartan och C kallas täckande graf för G . Om både C och H är ändliga och C är en plan graf , kallas C en plan täckning av H.
Grafen för en vanlig dodekaeder har en symmetri som mappar varje vertex till en antipodal vertex. Uppsättningen av antipoda par av hörn och deras närliggande områden kan också ses som en graf, Petersen-grafen . Dodekaedern bildar en plan täckning av denna icke-plana graf [4] . Det här exemplet visar att inte varje graf med en plan täckning i sig är plan. När en plan graf täcker en icke-planär, måste antalet lager vara jämnt [5] [6] .
Grafen för ett k -gonalt prisma har 2k hörn och är plan med två k -gonala ytor och k fyrkantiga ytor. Om k = ab , och , så har grafen ett a -lager som täcker avbildning till ett b -sidigt prisma där två hörn av k -prismat mappas till samma vertex av b -prismat om de båda tillhör samma k -gonala ytor och avståndet från den ena till den andra är en multipel av b . Till exempel kan ett tvåsidigt prisma bilda en 2-lagers täckning av ett hexagonalt prisma , en 3-lagers täckning av en kub , eller en 4-lagers täckning av ett triangulärt prisma . Dessa exempel visar att en graf kan ha många olika plana omslag och kan vara en plan omslag för många grafer. Dessutom visar dessa exempel att fibern i en plan beläggning kan vara godtyckligt stor. De täcker inte bara prismor, till exempel kan ett hexagonalt prisma också täcka en icke-plan gemensam graf K 3,3 genom att identifiera antipodala hörnpar [7] .
Om grafen H har en plan täckning, så gäller samma sak för alla grafer i grafen H [2] . Ett mindre G av en graf H kan bildas genom att ta bort kanter och hörn från H och dra ihop kanterna till H . Den täckande grafen C kan transformeras på samma sätt - för varje borttagen vertex från H tar vi bort dess förbild i C , och för varje sammandragen kant eller vertex från H krymper vi dess förbild till C . Resultatet av dessa operationer på C blir en mindre av C som täcker G . Eftersom vilken moll som helst i en plan graf i sig själv är plan, ger detta en plan täckning av moll av G .
Eftersom grafer med plana beläggningar stängs under operationen att ta minderåriga, följer det av Robertson-Seymours sats att de kan beskrivas av en ändlig uppsättning förbjudna minderåriga [8] . En graf är en förbjuden minor för den här egenskapen om den inte har något plant hölje, men alla dess underordnade har plana höljen. Den här beskrivningen kan användas för att bevisa existensen av en polynomtidsalgoritm som testar förekomsten av ett plant täcke genom att söka efter varje förbjudet moll och returnerar "en plan täckning existerar" om den sökningen inte hittar någon [9] . Men eftersom den exakta uppsättningen av förbjudna minderåriga för denna egendom inte är känd, är detta existensbevis inte konstruktivt och leder inte till en explicit beskrivning av uppsättningen förbjudna minderåriga eller en algoritm baserad på dem [10]
En annan operation på grafer som bevarar existensen av en plan täckning är stjärntriangel-transformationen , som ersätter vilken vertex av grad tre som helst i H med en triangel med sina tre grannar [2] . Den omvända transformationen, delta-stjärnomvandlingen, bevarar dock inte nödvändigtvis plana beläggningar.
Dessutom kommer den disjunkta föreningen av två grafer som har omslag också att ha ett lock bildat som den disjunkta föreningen av de täckande graferna. Om två beläggningar har samma fiber, kommer det också att vara fibern i deras förening.
Om en graf H har en inbäddning i det projektiva planet , så har den nödvändigtvis en plan täckning som ges av den omvända bilden av H i det orienterbara dubbelhöljet det projektiva planet, vilket är en sfär. Negami [11] bevisade motsatsen, att om en sammankopplad graf H har en plan täckning i två lager, så måste H ha en inbäddning i det projektiva planet [11] [12] . Antagandet att H är anslutet är nödvändigt här, eftersom den disjunkta föreningen av projektivt plana grafer kanske inte är projektivt plana [13] men fortfarande har ett plant lock, den disjunkta föreningen av orienterbara dubbla lock.
En regelbunden täckning av en graf H är en täckning som härrör från symmetrigruppen i dess täckande graf – de omvända bilderna av varje vertex i H bildar en omloppsbana av gruppen. Negami [14] bevisade att vilken sammankopplad graf som helst med en plan regelbunden täckning kan bäddas in i ett projektivt plan [14] [15] . Baserat på dessa två resultat, förmodade han att i själva verket varje ansluten graf med en plan täckning är projektiv [14] [16] . Från och med 2013 förblev hypotesen olöst [17] . Det är också känt som " Negami-förmodan", eftersom det kan omformuleras som påståendet att det minsta antalet fibrer i en plan beläggning, om sådan finns, måste vara antingen 1 eller 2 [18] .
Liksom grafer med plana beläggningar kan grafer med inbäddningar i det projektiva planet beskrivas av förbjudna minderåriga. I det här fallet är den exakta uppsättningen av förbjudna minderåriga känd, det finns 35 av dem. 32 av dem är anslutna, och en av dessa 32 grafer uppträder nödvändigtvis som en moll i alla anslutna icke-projektiva plana grafer [19] [20] . När Negami presenterade sin gissning bevisades det att 31 av dessa 32 förbjudna minderåriga antingen inte har några plana höljen eller kan reduceras genom en stjärntriangel-transformation till enklare grafer från denna lista [14] [18] [21] [22 ] [ 23] . Den enda kvarvarande grafen för vilken detta ännu inte har gjorts är K 1,2,2,2 , en apexgraf med sju hörn som bildar skelettet av en fyrdimensionell oktaedrisk pyramid . Om vi visar att K 1,2,2,2 inte har några plana höljen, kommer detta att vara ett fullständigt bevis på gissningen. Å andra sidan, om gissningen inte är sann, kommer K 1,2,2,2 att vara ett minimalt motexempel [24] .
En relaterad gissning av Michael Fellows, som redan är löst, handlar om plana emulatorer , en generalisering av plana beläggningar där grafkvarter kartläggs surjektivt snarare än bijektivt [25] [26] [27] . Grafer med plana emulatorer, som grafer [29][28]med plana beläggningar, stängs under mindre och stjärntriangeltransformationer [30] . Gissningen är sann för vanliga emulatorer härledda från automorfismer av den underliggande täckande grafen, liknande Negamis resultat [14] för vanliga plana täckningar [26] . Det visade sig dock att några av de 32 anslutna förbjudna minorerna för projektivt plana grafer har plana emulatorer [31] [32] [17] . Därför är Fellowes hypotes inte korrekt. Att hitta den kompletta uppsättningen av förbjudna minderåriga för förekomsten av plana emulatorer är fortfarande ett öppet problem [33] .