I grafteorin är en yttre plan graf en graf som tillåter ett plant diagram där alla hörn hör till den yttre ytan.
Yttre plana grafer kan karakteriseras (på samma sätt som Wagners teorem för plana grafer) av två förbjudna minorer K 4 och K 2,3 , eller deras Colin de Verdière-invarianter . Dessa grafer har Hamilton-cykler om och endast om de är dubbelkopplade, i vilket fall den yttre ytan bildar en enda Hamilton-cykel. Varje ytterplanär graf är 3-färgbar och har degeneration och trädbredd högst 2.
Yttreplanära grafer är en delmängd av plana grafer , subgrafer av parallell-seriegrafer och cirkeldiagram . En maximal ytterplanargraf är en graf till vilken en kant inte kan läggas till utan att förlora ytterplanaritet. De är också ackords- och synlighetsgrafer .
Yttreplanära grafer studerades och namngavs först av Chartrand och Harari [1] när man övervägde problemet med att bestämma planariteten hos grafer som bildas med hjälp av perfekta matchningar som kopplar samman två kopior av basgrafen (till exempel är många av de generaliserade Petersen-graferna utformade på detta sätt från två kopior av cykeldiagrammet ). Som de visade, om basgrafen är dubbelkopplad , är grafen som erhålls från den på det beskrivna sättet plan om och endast om basgrafen är yttre plan och matchningen bildar dihedriska permutationer av den yttre cykeln.
En ytterplanär graf är en oriktad graf som kan ritas på ett plan utan skärningspunkter så att alla hörn hör till ritningens yttre obegränsade yta. Det vill säga, ingen av hörnen är helt omgiven av kanter. Alternativt är en graf G ytterplanar om grafen som bildas av G genom att lägga till en ny vertex som är förbunden med kanter till alla andra hörn är plan [2] .
En maximal ytterplanär graf är en ytterplanär graf till vilken ingen kant kan läggas till utan att bryta mot ytterplanaritetsegenskapen. Varje maximal ytterplanär graf med n hörn har exakt 2n − 3 kanter, och varje avgränsad yta på en maximal ytterplanär graf är en triangel.
Yttreplanära grafer har en karaktärisering av förbjudna grafer som liknar Pontryagin-Kuratovskys sats och Wagners sats för plana grafer - en graf är ytterplanar om och endast om den inte innehåller en underavdelning av en komplett graf K 4 eller en fullständig tvådelad graf K 2, 3 [3] . Alternativt är en graf ytterplanar om och endast om den inte innehåller K 4 eller K 2,3 som en mindre , den graf som erhålls genom att ta bort och dra ihop kanter [4] .
En triangelfri graf är yttre plan om och endast om den inte innehåller underavdelningar K 2,3 [5] .
En graf är yttre plan om och endast om dess Colin de Verdière-invariant inte överstiger två. Grafer som på detta sätt kännetecknas av värdet av Colin de Verdière-invarianten (som inte överstiger värdet 1, 3 eller 4) är linjära skogar, plana grafer och inbäddningsbara grafer utan länk .
En ytterplanär graf är dubbelkopplad om och endast om den yttre ytan bildar en enkel cykel utan upprepade hörn. En ytterplanär graf är Hamiltonsk om och endast om den är dubbelkopplad. I detta fall bildar det yttre ansiktet en unik Hamiltonsk cykel [1] [5] . Mer generellt är storleken på den längsta cykeln i en ytterplanär graf lika med antalet hörn i den längsta bikopplade komponenten . Av denna anledning kan hitta Hamiltons cykler och längsta cykler i ytterplanära grafer göras i linjär tid , i motsats till NP-fullständigheten av dessa problem för godtyckliga grafer.
Varje maximal ytterplanär graf uppfyller ett starkare villkor än att vara hamiltonsk — den är vertex-pancyklisk , vilket betyder att för varje vertex v och vilket nummer k som helst mellan tre och antalet hörn i grafen, finns det en cykel med längden k som innehåller v . En cykel av denna längd kan hittas genom att successivt ta bort en triangel som är ansluten till resten av grafen med en enda kant, så att spetsen som ska tas bort inte sammanfaller med v , förrän den yttre sidan av den återstående grafen har längden k [6] .
En plan graf är yttre plan om och endast om alla dess dubbelkopplade komponenter är ytterplanära [5] .
Alla ytterplanära grafer utan slingor kan färgas med bara tre färger [7] . Detta faktum visar sig framträdande i ett förenklat bevis på konstgallerisatsen av Chvatala Fiscom [ 8] . En färgning med tre färger kan hittas i linjär tid av en girig färgningsalgoritm som tar bort alla hörn med högst två grader och färgar den återstående grafen rekursivt, och sedan returnerar var och en av de borttagna hörnen med en färg som skiljer sig från färgerna i dess två grannar.
Enligt Vizings teorem är det kromatiska indexet för en graf (det minsta antal färger som behövs för att färga grafens kanter så att inga två intilliggande kanter har samma färg) antingen lika med den maximala graden av grafens hörn, eller en mer än maxgraden. För ytterplanära grafer är det kromatiska indexet lika med den maximala effekten, såvida inte grafen är en cykel med udda längd [9] . En kantfärgning med det optimala antalet färger kan hittas i linjär tid baserat på en bredd-först sökning av ett svagt dubbelträd [7] .
Outerplanar graphs har degeneration som högst 2 - vilken subgraf som helst av en ytterplanar graph innehåller en vertex med grad som högst 2 [10] .
Yttreplanära grafer har trädbredd högst 2, vilket innebär att många optimeringsproblem på grafer som är NP-kompletta för generella grafer kan lösas i polynomtid med hjälp av dynamisk programmering om ingången är en ytterplanär graf. Mer allmänt har en k -yttreplanär graf trädbredden O( k ) [11] .
Vilken ytterplansgraf som helst kan representeras som en skärningsgraf av rektanglar med sidor parallella med axlarna, så att ytterplanära grafer har en intervalldimension [12] [13] på högst två [14] [15] .
Varje ytterplanär graf är plan . Varje ytterplanär graf är en subgraf till en parallell-seriell graf [16] . Dock är inte alla parallellsekventiella grafer yttre plan. Den kompletta tvådelade grafen K 2,3 är plan och parallell-seriell, men inte yttre plan. Å andra sidan är den fullständiga grafen K 4 plan, men varken parallell-sekventiell eller yttre plan. Vilken skog och vilken kaktus som helst är outplanar [17] .
Den svagt dubbla plana grafen för en inbäddad ytterplanär graf (en graf som har en vertex för varje avgränsad yta av boet och en kant för intilliggande avgränsade ytor) är en skog, och den svagt dubbla plana grafen i Halin-grafen är en ytterplanar graf . En plan graf är ytterplanar om och endast om dess svaga dual är en skog, och grafen är en Halin-graf om och endast om dess svaga dual är dubbelt sammankopplad och ytterplanar [18] .
Det finns ett koncept för graden av yttre planaritet. En 1-yttreplanär inbäddning av en graf är detsamma som en yttreplanarinbäddning. För k > 1 sägs en plan inbäddning vara k -outerplanar om borttagning av en vertex från den yttre ytan resulterar i en ( k − 1)-ytterplanar inbäddning. En graf är k -outerplanar om och endast om den har en k -outerplanar inbäddning [19] [5] .
Varje maximal ytterplanär graf är en kordalgraf . Varje maximal ytterplanär graf är en enkel polygonsynlighetsgraf [ 20] . Maximala ytterplanära grafer bildas som polygontrianguleringsgrafer . De är också exempel på 2-träd , parallellsekvensgrafer och ackordsgrafer .
Varje ytterplanär graf är en cirkelgraf , skärningsgrafen för uppsättningen av ackord i cirkeln [21] [22] .