I topologisk grafteori er en 1-plan graf en graf , der kan tegnes i det euklidiske plan på en sådan måde, at hver kant højst har ét skæringspunkt med kun én anden kant.
1-plane grafer blev først overvejet af Ringel, som viste, at de kan farves med højst syv farver [1] . Senere blev det nøjagtige antal farver, der var nødvendige for at farve disse grafer, (i værste fald) reduceret til seks [2] . Et eksempel på en komplet K 6 -graf , der er 1-plan, viser, at 1-plane grafer nogle gange kan kræve seks farver for at farvelægge. Det er dog ikke let at bevise, at seks farver er tilstrækkelige.
Grunden til at overveje 1-plane grafer af Ringel var et forsøg på at løse en variant af det totale farveproblem for plane grafer , hvor hjørnerne og fladerne på en plan graf er farvet på en sådan måde, at ikke to tilstødende hjørner har det samme farve og to tilstødende flader skal også farves i forskellige farver. farverne, såvel som farverne på hjørnerne og flader, der støder op til dem, skal være forskellige. Dette kan naturligvis gøres med otte farver, hvis vi anvender firefarvesætningen for en graf og dens dobbeltgraf separat ved at bruge to usammenhængende sæt af fire farver. Du kan dog få færre farver, hvis du danner en hjælpegraf, der har et toppunkt for hvert toppunkt og hver side af den oprindelige plane graf, og hvor to hjørner af hjælpegrafen støder op til hinanden, hvis de svarer til tilstødende objekter på den givne plane graf . Hjelpegrafens toppunktsfarvning svarer til farven på den oprindelige plane graf. Hjælpegrafen er 1-plan, hvilket betyder, at Ringels toppunkt og ansigtsfarveproblem kan løses ved hjælp af seks farver [2] . Graf K 6 kan ikke opnås som en hjælpegraf på denne måde, men ikke desto mindre kræver problemet med at farve toppunkter og flader nogle gange seks farver. For eksempel, hvis du farvelægger den plane graf af et trekantet prisme , kræver dets 6 spidser + 5 flader seks farver [3] .
Enhver 1-plan graf med n toppunkter har højst 4n − 8 kanter [4] . Mere strengt har hver tegning af en 1-plan graf højst n − 2 skæringspunkter . Fjernelse af en kant fra hvert krydsende par af kanter efterlader en plan graf, der højst har 3n − 6 kanter, hvilket umiddelbart indebærer grænsen på 4n − 8 kant for den oprindelige 1-plane graf [5] . Men i modsætning til plane grafer (hvor alle maksimale plane grafer på et givet sæt hjørner har det samme antal kanter), er der maksimale 1-plane grafer (grafer, hvortil en kant ikke kan tilføjes, mens 1-planariteten bevares), som har væsentligt mindre end 4 n − 8 kanter [6] . De 4 n − 8 bundet på det maksimalt mulige antal kanter i en 1-plan graf kan bruges til at vise, at hele grafen K 7 med syv hjørner ikke er 1-plan, da denne graf har 21 kanter, og derefter 4 n − 8 = 20 < 21 [7] .
En 1-plan graf siges at være en optimal 1-plan graf, hvis den har præcis 4n − 8 kanter, det maksimalt mulige antal. I en 1-plan indlejring af en optimal 1-plan graf danner ikke-skærende kanter nødvendigvis en flisebelægning i firkanter (dvs. danner en polyedrisk graf , hvor hver flade er en firkant ). Enhver quadring genererer en 1-plan graf ved at tilføje to diagonaler til hver firkantet flade. Det følger heraf, at enhver optimal 1-plan graf er Eulersk (alle dens toppunkter har lige grad ), at den mindste grad i sådanne grafer er 6, og at enhver optimal 1-plan graf har mindst otte toppunkter med nøjagtig seks grader. Desuden er enhver optimal 1-plan graf 4-vertex-forbundet , og enhver 4-vertex-sektion i en sådan graf er en skærende cyklus i den underliggende firkant [8] .
Grafer, der har retlinede 1-plane tegninger (dvs. tegninger, hvor hver kant er repræsenteret af et lige linjestykke, og hvert segment er gennemskåret af højst en anden kant) har en lidt stærkere grænse på 4 n − 9 på det maksimale antal af kanter, hvilket opnås på et uendeligt antal grafer [9] .
En komplet klassifikation af 1-planare komplette grafer , komplette todelte grafer og mere generelle komplette multipartite grafer er kendt. Enhver komplet todelt graf af formen K 2, n er 1-plan, ligesom enhver komplet tredelt graf af formen K 1,1, n er . Udover disse uendelige mængder er de komplette multipartite 1-plane grafer K 6 , K 1,1,1,6 , K 1,1,2,3 , K 2,2,2,2 , K 1,1,1, 2 ,2 og deres underafsnit. De minimale komplette multipartite grafer, der ikke er 1-plane, er K 3,7 , K 4,5 , K 1,3,4 , K 2,3,3 og K 1,1,1,1,3 . For eksempel er den komplette todelte graf K 3,6 1-plan, fordi den er en undergraf af K 1,1,1,6 , men K 3,7 er ikke 1-plan [7] .
At kontrollere om en graf er 1-plan er NP-komplet [10] [11] , og problemet forbliver NP-komplet selv for grafer opnået fra plane grafer ved at tilføje en enkelt kant [12] og for grafer med begrænset bredde [ 13] .
Problemet er fast-parametrisk løseligt hvis det parametriseres af cyklomatisk tal eller trædybde , så det kan løses i polynomiel tid, hvis disse parametre er begrænset [13] .
I modsætning til Faree-sætningen for plane grafer, kan ikke alle 1-plane grafer tegnes 1-plane med linjestykker som kanter [14] [15] . Men at kontrollere, om en 1-plan graf med lige kanter kan tegnes, kan ske i polynomiel tid [16] . Derudover har enhver top-3-forbundet 1-plan graf en 1-plan tegning, hvor højst en kant på den ydre flade har et knæk . En sådan tegning kan bygges i lineær tid , baseret på en 1-plan grafindlejring [17] . 1-plane grafer har en begrænset bogtykkelse [18] , men nogle 1-planære grafer, herunder K 2,2,2,2 , har en bogtykkelse på mindst fire [19] .
1-plane grafer har en afgrænset lokal træbredde , hvilket betyder, at der eksisterer en (lineær) funktion f , således at 1-plane grafer med diameter d højst har en træbredde f ( d ). Den samme egenskab gælder for mere generelle grafer, der kan indlejres i en overflade af afgrænset slægt med et begrænset antal krydsninger pr. kant. De har også separatorer , et lille sæt hjørner, hvis fjernelse deler grafen op i forbundne komponenter, hvis størrelse er en konstant brøkdel af hele grafen. Baseret på disse egenskaber kan adskillige plane grafalgoritmer, såsom Brenda Sue Bakers teknik til at konstruere tilnærmelsesalgoritmer , udvides til 1-plane grafer. For eksempel fører denne metode til et tilnærmet polynomisk tidsskema til at finde det største uafhængige sæt af en 1-plan graf [20] .
Klassen af grafer, der er analoge med ydre- planære grafer for 1-planaritet, kaldes ydre-1-planære grafer . Det er grafer, der kan tegnes på en skive med spidser på skivegrænsen og med kanter, der højst har et skæring pr. kant. Disse grafer kan altid tegnes (som en ekstern 1-plan graf) med lige kanter og retvinklede skæringspunkter [21] . Ved hjælp af dynamisk programmering på SPQR-træet for en given graf er det muligt at kontrollere, om grafen er eksternt 1-plan i lineær tid [22] [23] . Tri-forbundne grafkomponenter (SPQR-træknuder) kan kun bestå af cyklusser , bondgraphs og komplette grafer med fire spidser, hvilket indebærer, at eksterne 1-plane grafer er plane og har højst tre træbredder . I modsætning til 1-plane grafer har ekstrinsiske 1-plane grafer en karakterisering i form af grafiske minorer - en graf er ydre 1-planar, hvis og kun hvis den ikke indeholder nogen af de fem forbudte molorer [23] .
Klassen af 1-plane grafer inkluderer 4-kort grafer , grafer dannet fra tilstødende områder af planet med den betingelse, at intet punkt ligger på grænsen af mere end fire områder (hjørnepunkter (områder) er forbundet med en kant, hvis regionsgrænsen). Omvendt er enhver optimal 1-plan graf en 4-kort graf. 1-plane grafer, der ikke er optimale 1-plane, er muligvis ikke kortgrafer [24] .
1-plane grafer generaliseres til k -plane grafer, hvor hver kant er krydset af andre kanter højst k gange. Ringel definerede det lokale skæringsnummer for en graf G som den mindste ikke-negative k , således at G har en k -plan tegning. Da det lokale antal skæringspunkter er lig med den største grad af skæringsgrafen for kanterne af det optimale mønster, og tykkelsen (det mindste antal plane grafer, som kanterne kan dekomponeres i) kan betragtes som det kromatiske antal af skæringsgrafen for det passende mønster, følger det af Brooks' sætning , at tykkelsen højst er én større end det lokale antal skæringspunkter [25] . k -plane grafer med n toppunkter har maksimalt O ( k 1/2 n ) kanter [26] og en træbredde på O (( kn ) 1/2 ) [27] . Den lavvandede mol af en k -plan graf med dybde d er sig selv ( 2d + 1) k -plan, så de lavvandede mol af 1-plane grafer og k -plane grafer er sparsomme grafer , hvilket her betyder, at 1-plan og k- plane grafer har en afgrænset forlængelse [28] .
For ikke-plane grafer kan du også indstille parameteren antal skæringspunkter , det mindste antal kanter, der skærer hinanden i en graftegning. En graf med k skæringspunkter er nødvendigvis k -plan, men det modsatte er ikke nødvendigvis sandt. For eksempel har Heawood Graph 3 skæringspunkter, men disse skæringspunkter behøver ikke at være med én kant, den er 1-plan og kan tegnes med samtidig optimering af det samlede antal skæringer og skæringer pr.
Et andet relateret koncept for ikke-plane grafer er skew , det mindste antal kanter, der skal fjernes for at gøre en graf plan.