I grafteori er en ydreplanær graf en graf, der tillader et plant diagram , hvor alle hjørner tilhører den ydre flade.
Ydre plane grafer kan karakteriseres (på samme måde som Wagners sætning for plane grafer) ved to forbudte mol K 4 og K 2,3 eller deres Colin de Verdière invarianter . Disse grafer har Hamiltonske cyklusser, hvis og kun hvis de er dobbeltforbundne, i hvilket tilfælde den ydre flade danner en enkelt Hamiltonsk cyklus. Enhver ydreplanær graf er 3-farverbar og har degeneration og træbredde på højst 2.
Ydreplanære grafer er en delmængde af plane grafer , undergrafer af parallel-serielle grafer og cirkelgrafer . En maksimal ydreplanargraf er en graf, hvortil en kant ikke kan tilføjes uden at miste ydreplanaritet. De er også akkord- og synlighedsgrafer .
Ydreplanære grafer blev først undersøgt og navngivet af Chartrand og Harari [1] , da de overvejede problemet med at bestemme planheden af grafer dannet ved hjælp af perfekte matchninger , der forbinder to kopier af basisgrafen (for eksempel er mange af de generaliserede Petersen-grafer dannet på denne måde fra to kopier af cyklusgrafen ). Som de viste, hvis basisgrafen er biforbundet , er grafen opnået fra den på den beskrevne måde plan, hvis og kun hvis basisgrafen er ydreplanar, og matchningen danner dihedrale permutationer af den ydre cyklus.
En ydreplanær graf er en urettet graf , der kan tegnes på et plan uden skæringspunkter , således at alle toppunkter tilhører tegningens ydre ubegrænsede flade. Det vil sige, at ingen af hjørnerne er helt omgivet af kanter. Alternativt er en graf G ydre plan, hvis grafen dannet af G ved at tilføje et nyt toppunkt forbundet med kanter til alle andre hjørner er plan [2] .
En maksimal outerplanar graf er en outerplanar graf, hvortil ingen kant kan tilføjes uden at krænke outerplanarity egenskaben. Enhver maksimal ydreplanær graf med n toppunkter har nøjagtigt 2n − 3 kanter, og enhver afgrænset flade på en maksimal ydreplanær graf er en trekant.
Ydreplane grafer har en karakterisering af forbudte grafer svarende til Pontryagin-Kuratovsky-sætningen og Wagners sætning for plane grafer - en graf er ydreplanar, hvis og kun hvis den ikke indeholder en underopdeling af en komplet graf K 4 eller en komplet todelt graf K 2, 3 [3] . Alternativt er en graf outerplanar, hvis og kun hvis den ikke indeholder K 4 eller K 2,3 som en mindre , grafen opnået ved at fjerne og trække kanter sammen [4] .
En trekantfri graf er udvendig plan, hvis og kun hvis den ikke indeholder underinddelinger K 2,3 [5] .
En graf er udvendig, hvis og kun hvis dens Colin de Verdière-invariant ikke overstiger to. Grafer karakteriseret på denne måde af værdien af Colin de Verdière invarianten (ikke over værdien af 1, 3 eller 4) er lineære skove, plane grafer og indlejrbare grafer uden et link .
En ydre planar graf er dobbelt forbundet , hvis og kun hvis den ydre flade danner en simpel cyklus uden gentagne hjørner. En ydreplanær graf er Hamiltonsk , hvis og kun hvis den er biforbundet. I dette tilfælde danner den ydre flade en unik Hamilton-cyklus [1] [5] . Mere generelt er størrelsen af den længste cyklus i en ydreplanar graf lig med antallet af hjørner i den længste biforbundne komponent . Af denne grund kan finde Hamilton-cyklusser og længste cyklusser i ydreplanære grafer ske i lineær tid , i modsætning til NP-fuldstændigheden af disse problemer for vilkårlige grafer.
Enhver maksimal ydreplanær graf opfylder en stærkere betingelse end at være Hamiltonsk - den er toppunkt-pancyklisk , hvilket betyder, at for ethvert toppunkt v og ethvert tal k mellem tre og antallet af hjørner i grafen, er der en cyklus med længden k indeholdende v . En cyklus af denne længde kan findes ved successivt at fjerne en trekant, der er forbundet med resten af grafen med en enkelt kant, således at toppunktet, der skal fjernes, ikke falder sammen med v , før den ydre flade af den resterende graf har længden k [6] .
En plan graf er udvendig, hvis og kun hvis alle dens dobbeltforbundne komponenter er udvendige [5] .
Alle ydre planære grafer uden sløjfer kan farves med kun tre farver [7] . Dette faktum viser sig fremtrædende i et forenklet bevis på kunstgallerisætningen af Chvatala Fiscom [ 8] . En farvning med tre farver kan findes i lineær tid ved hjælp af en grådig farvealgoritme , der fjerner ethvert toppunkt med højst grad to og farver den resterende graf rekursivt og derefter returnerer hver af de fjernede hjørner med en farve, der er forskellig fra farverne i dens to naboer.
Ifølge Vizings sætning er det kromatiske indeks for enhver graf (det mindste antal farver, der er nødvendige for at farve grafens kanter, så ingen to tilstødende kanter har samme farve) enten lig med den maksimale grad af grafens hjørner, eller en mere end den maksimale grad. For ydreplanære grafer er det kromatiske indeks lig med den maksimale effekt, medmindre grafen er en cyklus med ulige længde [9] . En kantfarvning med det optimale antal farver kan findes i lineær tid baseret på en bredde-først søgning af et svagt dobbelttræ [7] .
Yderplane grafer har degeneration højst 2 - enhver undergraf i en ydreplanar graf indeholder et toppunkt med grad på højst 2 [10] .
Ydreplanære grafer har højst træbredde 2, hvilket indebærer, at mange optimeringsproblemer på grafer, der er NP-komplette for generelle grafer, kan løses i polynomisk tid ved hjælp af dynamisk programmering, hvis inputtet er en ydreplanær graf. Mere generelt har en k -ydreplanar graf træbredde O( k ) [11] .
Enhver ydreplanær graf kan repræsenteres som en skæringsgraf af rektangler med sider parallelle med akserne, således at ydreplanære grafer har en intervaldimension [12] [13] på højst to [14] [15] .
Enhver ydreplanær graf er plan . Enhver ydreplanær graf er en undergraf af en parallel-seriel graf [16] . Det er dog ikke alle parallel-sekventielle grafer, der er udvendige. Den komplette todelte graf K 2,3 er plan og parallel-seriel, men ikke udvendig. På den anden side er den komplette graf K 4 plan, men hverken parallel-sekventiel eller ydreplanar. Enhver skov og enhver kaktus er udplanære [17] .
Den svagt dobbelte plane graf af en indlejret ydreplanær graf (en graf, der har et toppunkt for hver afgrænset flade af redet og en kant for tilstødende afgrænsede flader) er en skov, og den svagt dobbelte plane graf af Halin-grafen er en ydreplanar graf . En plan graf er ydreplanar, hvis og kun hvis dens svage dual er en skov, og grafen er en Halin-graf, hvis og kun hvis dens svage dual er dobbelt forbundet og ydreplanar [18] .
Der er et koncept for graden af ekstern planaritet. En 1-ydreplanar indlejring af en graf er det samme som en ydreplanar indlejring. For k > 1 siges en plan indlejring at være k -ydreplanar, hvis fjernelse af et vertex fra den ydre flade resulterer i en ( k − 1)-ydreplan indlejring. En graf er k -ydreplanar, hvis og kun hvis den har en k -ydreplanar indlejring [19] [5] .
Enhver maksimal ydreplanær graf er en akkordgraf . Enhver maksimal ydreplanær graf er en simpel polygonsynlighedsgraf [20] . Maksimale ydreplanære grafer er dannet som polygontrianguleringsgrafer . De er også eksempler på 2-træer , parallelle sekvensgrafer og akkordgrafer .
Enhver ydreplanær graf er en cirkelgraf , skæringsgrafen for sættet af akkorder i cirklen [21] [22] .