Inom topologisk grafteori är en 1-planar graf en graf som kan ritas i det euklidiska planet på ett sådant sätt att varje kant har högst en skärning med endast en annan kant.
1-planära grafer övervägdes först av Ringel, som visade att de kan färgas med högst sju färger [1] . Senare reducerades det exakta antalet färger som behövdes för att färga dessa grafer (i värsta fall) till sex [2] . Ett exempel på en komplett K 6 -graf som är 1-planar visar att 1-planära grafer ibland kan kräva sex färger för att färga. Det är dock inte lätt att bevisa att sex färger är tillräckliga.
Anledningen till att Ringel övervägde 1-plana grafer var ett försök att lösa en variant av det totala färgproblemet för plana grafer , där hörn och ytor på en plan graf är färgade på ett sådant sätt att inte två angränsande hörn har samma färg och två intilliggande ytor måste också färgas i olika färger. Färgerna, såväl som färgerna på hörnen och ytorna intill dem, måste vara olika. Uppenbarligen kan detta göras med åtta färger om vi tillämpar fyrafärgssatsen för en graf och dess dubbla graf separat, med två disjunkta uppsättningar av fyra färger. Du kan dock få färre färger om du bildar en hjälpgraf som har en vertex för varje vertex och yta av den ursprungliga plana grafen, och där två hörn av hjälpgrafen ligger intill om de motsvarar intilliggande objekt i den givna plana grafen . Hörnets färgning av hjälpgrafen motsvarar färgen på den ursprungliga plana grafen. Hjälpgrafen är 1-planar, vilket betyder att Ringels vertex- och ansiktsfärgningsproblem kan lösas med sex färger [2] . Grafen K 6 kan inte erhållas som en hjälpgraf på detta sätt, men problemet med färgläggning av hörn och ytor kräver ibland sex färger. Till exempel, om du färglägger den plana grafen för ett triangulärt prisma kräver dess 6 hörn + 5 ytor sex färger [3] .
Varje 1-plan graf med n hörn har som mest 4n − 8 kanter [4] . Mer strikt, varje ritning av en 1-planar graf har högst n − 2 skärningspunkter . Att ta bort en kant från varje korsande par av kanter lämnar en plan graf som har högst 3n − 6 kanter, vilket omedelbart innebär 4n − 8 kantgränsen för den ursprungliga 1-planar grafen [5] . Men till skillnad från plana grafer (för vilka alla maximala plana grafer på en given uppsättning hörn har samma antal kanter), finns det maximala 1-planära grafer (grafer till vilka en kant inte kan läggas till med bibehållen 1-planaritet) som har väsentligt mindre än 4 n − 8 kanter [6] . De 4 n − 8 bundna på maximalt möjliga antal kanter i en 1-planar graf kan användas för att visa att hela grafen K 7 med sju hörn inte är 1-plan, eftersom denna graf har 21 kanter, och sedan 4 n − 8 = 20 < 21 [7] .
En 1-planar graf sägs vara en optimal 1-planar graf om den har exakt 4n − 8 kanter, det högsta möjliga antalet. I en 1-plans inbäddning av en optimal 1-planar graf, bildar icke-korsande kanter nödvändigtvis en sida vid sida i fyrkanter (dvs. bildar en polyedrisk graf där varje yta är en fyrhörning ). Varje kvadrering genererar en 1-plan graf genom att lägga till två diagonaler till varje kvadratisk yta. Det följer att varje optimal 1-planar graf är Eulerian (alla dess hörn har jämn grad ), att den minsta graden i sådana grafer är 6, och att varje optimal 1-planar graf har minst åtta hörn med exakt sex grader. Dessutom är varje optimal 1-planar graf 4-vertex-ansluten , och varje 4-vertex-sektion i en sådan graf är en skärcykel i den underliggande fyrhörningen [8] .
Grafer som har rätlinjiga 1-plana ritningar (dvs ritningar där varje kant representeras av ett rakt linjesegment och varje segment skärs av högst en annan kant) har en något starkare gräns på 4 n − 9 på det maximala antalet kanter, vilket uppnås på ett oändligt antal grafer [ 9] .
En fullständig klassificering av 1-planar kompletta grafer , kompletta tvådelade grafer och mer generella kompletta flerdelade grafer är känd. Varje komplett tvådelad graf av formen K 2, n är 1-plan, liksom varje komplett tredelad graf av formen K 1,1, n . Förutom dessa oändliga uppsättningar är de kompletta flerdelade 1-planära graferna K 6 , K 1,1,1,6 , K 1,1,2,3 , K 2,2,2,2 , K 1,1,1, 2 ,2 och deras subgrafer. De minimala kompletta flerdelade graferna som inte är 1-planära är K 3,7 , K 4,5 , K 1,3,4 , K 2,3,3 och K 1,1,1,1,3 . Till exempel är den kompletta tvådelade grafen K 3,6 1-planar eftersom den är en subgraf av K 1,1,1,6 , men K 3,7 är inte 1-planar [7] .
Att kontrollera om en graf är 1-plan är NP-komplett [10] [11] och problemet förblir NP-komplett även för grafer erhållna från plana grafer genom att lägga till en enda kant [12] och för grafer med begränsad bredd [ 13] .
Problemet är fast-parametriskt lösbart om det parametriseras av cyklomatiskt antal eller träddjup , så att det kan lösas i polynomtid om dessa parametrar är begränsade [13] .
Till skillnad från Faree-satsen för plana grafer kan inte alla 1-planära grafer ritas 1-plana med linjesegment som kanter [14] [15] . Att kontrollera om en 1-plan graf med raka kanter kan ritas kan dock göras i polynomtid [16] . Dessutom har alla vertex-3-kopplade 1-planar grafer en 1-planar ritning där högst en kant på den yttre sidan har en kink . En sådan ritning kan byggas i linjär tid , baserat på en 1-plans grafinbäddning [17] . 1-plana grafer har en begränsad boktjocklek [18] , men vissa 1-planar grafer, inklusive K 2,2,2,2 , har en boktjocklek på minst fyra [19] .
1-planära grafer har en begränsad lokal trädbredd , vilket betyder att det finns en (linjär) funktion f så att 1-planära grafer med diameter d har en trädbredd som mest f ( d ). Samma egenskap gäller för mer allmänna grafer som kan bäddas in i en yta av begränsat släkte med ett begränsat antal korsningar per kant. De har också separatorer , en liten uppsättning hörn vars borttagning bryter grafen i anslutna komponenter vars storlek är en konstant bråkdel av hela grafen. Baserat på dessa egenskaper kan många plana grafalgoritmer, såsom Brenda Sue Bakers teknik för att konstruera approximationsalgoritmer , utökas till 1-planära grafer. Till exempel leder denna metod till ett ungefärligt polynomtidsschema för att hitta den största oberoende uppsättningen av en 1-planar graf [20] .
Klassen av grafer som är analoga med ytterplanära grafer för 1-planaritet kallas ytterplanära grafer . Detta är grafer som kan ritas på en skiva med hörn på skivgränsen och med kanter som har högst en skärning per kant. Dessa grafer kan alltid ritas (som en externt 1-plan graf) med raka kanter och rätvinkliga skärningar [21] . Genom att använda dynamisk programmering på SPQR-trädet för en given graf är det möjligt att kontrollera om grafen är externt 1-plan i linjär tid [22] [23] . Trekopplade grafkomponenter (SPQR-trädnoder) kan bara bestå av cykler , bondgrafer och kompletta grafer med fyra hörn, vilket innebär att externt 1-plana grafer är plana och har högst tre trädbredder . Till skillnad från 1-planära grafer har extrinsiska 1-planära grafer en karaktärisering i termer av grafmolor - en graf är extrinsisk 1-planar om och bara om den inte innehåller någon av de fem förbjudna mollorna [23] .
Klassen av 1-planära grafer inkluderar 4-kartsgrafer , grafer bildade från angränsande områden av planet med villkoret att ingen punkt ligger på gränsen till mer än fyra regioner (hörn (regioner) är förbundna med en kant om regiongränsen). Omvänt är varje optimal 1-planar graf en 4-kartsgraf. 1-planära grafer som inte är optimala 1-planar kanske inte är kartdiagram [24] .
1-planära grafer generaliseras till k -planära grafer, där varje kant korsas av andra kanter högst k gånger. Ringel definierade det lokala skärningsnumret för en graf G som den minsta icke-negativa k så att G har en k -plan ritning. Eftersom det lokala antalet skärningar är lika med den största graden av skärningsdiagrammet för kanterna på det optimala mönstret, och tjockleken (det minsta antalet plana grafer till vilka kanterna kan dekomponeras) kan betraktas som det kromatiska antalet av skärningsgrafen för det lämpliga mönstret, följer det av Brooks sats att tjockleken är högst en större än det lokala antalet skärningar [25] . k -planära grafer med n hörn har maximalt O ( k 1/2 n ) kanter [26] och en trädbredd på O (( kn ) 1/2 ) [27] . Den grunda mollfärgen i en k -planar graf med djup d är sig själv ( 2d + 1) k -planar, så de grunda mollorna i 1-planar grafer och k -planar grafer är glesa grafer , vilket här betyder att 1-planar och k- plana grafer har en begränsad förlängning [28] .
För icke-plana grafer kan du också ställa in parametern antalet skärningar , det minsta antalet kanter som skär varandra i en grafritning. En graf med k skärningspunkter är nödvändigtvis k -plan, men det omvända är inte nödvändigtvis sant. Till exempel har Heawood-grafen 3 skärningar, men dessa korsningar behöver inte vara med en kant, den är 1-plan och kan ritas med samtidig optimering av det totala antalet korsningar och skärningar per en kant.
Ett annat relaterat koncept för icke-plana grafer är skew , det minsta antalet kanter som måste tas bort för att göra en graf plan.