En grafindlejring er en repræsentation af en graf på en given overflade studeret inden for rammerne af topologisk grafteori , hvor punkter er forbundet med grafens hjørnepunkter og simple buer ( homeomorfe billeder [0,1]) på overfladen er forbundet med grafkanter på en sådan måde, at:
Her er overfladen en kompakt , forbundet 2 - manifold .
Uformelt er en indlejring af en graf i en overflade et billede af grafen på overfladen på en sådan måde, at dens kanter kun kan skære hinanden ved endepunkter. Det er velkendt, at enhver finit graf kan indlejres i et tredimensionelt euklidisk rum [1] , og plane grafer kan indlejres i et todimensionelt euklidisk rum .
Ofte ses en indlejring som en ækvivalensklasse (ved homeomorfismer ) af repræsentationer af den beskrevne art.
I forbindelse med grafvisualiseringsproblemer overvejes også en svag version af definitionen af grafindlejring, hvor fraværet af kantskæringer ikke er påkrævet. Derfor beskrives den stærke definition som "en indlejring af en graf uden skæringspunkter" [2] .
Hvis grafen er indlejret i en lukket overflade , så er komplementet af foreningen af punkter og buer, der er forbundet med grafens toppunkter og kanter, en familie af en familie af regioner (eller flader) [3] . En todimensionel celleindlejring eller -kort er en indlejring, hvor hvert ansigt er homøomorfe til en åben disk [4] . En todimensionel lukket celle indlejring er en indlejring, hvor lukningen af ethvert ansigt er homøomorf til en lukket disk.
Grafstabling bruges ofte som et synonym for indlejring, især i tilfælde af plane grafer.
En grafs slægt er det mindste heltal , således at grafen kan indlejres i slægtens overflade . Især en plan graf har slægten 0, fordi den kan tegnes på en kugle uden selvskæringer. Den ikke- orienterbare slægt af en graf er det mindste heltal , således at grafen kan indlejres i en urettet overflade af (ikke-orienterbar) slægt [3] .
Euler-slægten af en graf er det mindste heltal , således at grafen kan indlejres i en orienterbar overflade af (orienterbar) slægt eller en urettet overflade af (ikke-orienterbar) slægt . En graf er simpelthen orienterbar, hvis dens Euler-slægt er mindre end dens ikke-orienterbare slægt.
Den maksimale slægt af en graf er det maksimale heltal , således at grafen kan indlejres med flad celle (indlejring er flad celle, hvis en lukket kurve, der ikke skærer kanterne på grafen, trækker sig sammen til et punkt) i en orienterbar overflade af slægt .
En indlejret graf definerer entydigt de cykliske rækkefølger af kanter, der falder ind på det samme toppunkt. Mængden af alle disse cykliske ordener kaldes det cirkulære system . Indlejringer med det samme cirkulære system betragtes som ækvivalente, og den tilsvarende ækvivalensklasse af indlejringer kaldes en kombinatorisk indlejring (i modsætning til begrebet topologisk indlejring , som refererer til den tidligere definition af punkter og kurver). Nogle gange kaldes et cirkulært system i sig selv for en "kombinatorisk indlejring" [5] [6] [7] .
Den indlejrede graf definerer også naturlige cykliske kantrækkefølger, der definerer grænserne for indlejringsfladerne. At arbejde med disse facetorienterede ordrer er dog mindre indlysende, da nogle kanter i nogle tilfælde kan krydses to gange, når man krydser grænsen af et ansigt. Det gælder for eksempel altid, når der redes træer, der har en enkelt kant. For at overvinde denne kombinatoriske hindring kan man betragte hver kant som værende "delt" i to "halvkanter" eller "sider". I henhold til disse konventioner, i alle flader, krydser grænsen hver halvkant kun én gang, og hver halvkant af den ene kant krydses altid i modsatte retninger.
Problemet med at bestemme slægten af en graf er NP-komplet (problemet med at bestemme om en graf med hjørner har slægt er NP-komplet ) [8] .
Samtidig er problemet med at bestemme en grafs slægt fast-parametrisk løseligt , det vil sige, at der kendes algoritmer med polynomiel tid til at kontrollere, om en graf kan indlejres i en overflade med en given slægt. Det samme gælder for at finde en tilknytning.
Det første gennembrud kom i 1979 , da tidskompleksitetsalgoritmer blev uafhængigt rapporteret på det årlige ACM Symposium on Computational Theory - en foreslået af Ion Filotti og Gary Miller og en anden af John Reif . Deres tilgange var helt anderledes, men efter forslag fra organisationskomiteen indsendte de en sammenlagt artikel [9] .
I 1999 blev det vist, at tilfældet med fast slægt kan løses i lineær tid i grafstørrelse og i dobbelt eksponentiel tid i slægt [10] .
Det er kendt, at enhver finit graf kan indlejres i et tredimensionelt rum [1] .
En metode til en sådan indlejring er at placere punkter (grafens toppunkter) på en linje og tegne kanterne som kurver, der ligger i separate halvplaner , der har denne linje som en grænse fælles for alle halvplaner. Denne form for indlejring kaldes en grafbogsindlejring . Denne metafor bliver tydelig, hvis vi forestiller os hvert halvplan som en side i en bog. Det er tydeligt, at nogle kanter kan tegnes uden skæringspunkter på samme "side". Bogtykkelsen af en graf er det mindste antal halvplaner i en bogindlejring.
På den anden side kan enhver endelig graf tegnes uden skæringspunkter i tredimensionelt rum med lige kanter ved at placere hjørnerne i en generel position , således at ingen fire er koplanære (ikke ligger i samme plan). For eksempel kan dette opnås ved at placere det -th vertex i et punkt på momentkurven .
En indlejring af en graf i et tredimensionelt rum, hvor ikke to cyklusser er topologisk forbundet, kaldes en ikke-forbundet indlejring . En graf har en ikke-linket indlejring, hvis og kun hvis den ikke indeholder nogen af de syv grafer i Peterson-familien som en minor .