Indlejring af grafer

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: $G$ $\Sigma$ $\Sigma$

endepunkterne af en bue, der er knyttet til en kant af grafen , er de punkter, der er knyttet til endepunkterne på den pågældende kant af grafen $e$ $e$
ingen bue indeholder punkter forbundet med andre hjørner
ingen to buer skærer hinanden ved de indre punkter af disse buer.

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 . $\mathbb {R} ^{3}$ $\mathbb {R} ^{2}$

Ofte ses en indlejring som en ækvivalensklasse (ved homeomorfismer ) af repræsentationer af den beskrevne art. $\Sigma$

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] .

Terminologi

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. $G$ $\Sigma$ $G$

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] . $n$ $n$ $n$ $n$

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. $n$ ${\tfrac {n}{2))$ $n$

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 . $n$ $n$

Kombinatorisk indlejring

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.

Beregningsmæssig kompleksitet

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] . $n$ $g$

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] . $O(n^{O(g)})$

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] .

Indlejring af en graf i rum med højere dimensioner

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 . $jeg$ $(i,i^{2},i^{3})$

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 .

Se også

Dobbeltforbundet liste over kanter - en datastruktur til at repræsentere en graf, der er indlejret i et plan
Korrekt kort
Faris sætning , der siger, at der altid er en indlejring i planet af en plan graf, hvor alle buer er repræsenteret af linjestykker.

Noter

↑ 1 2 Cohen, Eades, Lin, Ruskey, 1995 , s. 1-11.
↑ Katoh, Tanigawa, 2007 , s. 243-253.
↑ 12 Gross , Tucker, 2001 .
↑ Zvonkin, Lando, 2010 .
↑ Mutzel, Weiskircher, 2000 , s. 95-104.
↑ Didjev, 1995 , s. 76-83.
↑ Duncan, Goodrich, Kobourov, 2010 , s. 45-56.
↑ Thomassen, 1989 , s. 568-576.
↑ Filotti, Miller, Reif, 1979 , s. 27-37.
↑ Mohar, 1999 , s. 6-26.

Litteratur

Robert F. Cohen, Peter Eades, Tao Lin, Frank Ruskey. Graftegning: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, 10.–12. oktober 1994, Proceedings / Roberto Tamassia, Ioannis G. Tollis. - Springer, 1995. - T. 894. - S. 1-11. — ( Forelæsningsnotater i Datalogi ). - doi : 10.1007/3-540-58950-3_351 .
Petra Mutzel, René Weiskircher. Computing Optimal Embeddings for Planar Graphs // Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australien, 26.–28. juli 2000, Proceedings. - Springer-Verlag, 2000. - T. 1858. - S. 95–104. — (Forelæsningsnotater i datalogi). - ISBN 978-3-540-67787-1 . - doi : 10.1007/3-540-44968-X_10 .
Christo N. Didjev. Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, 10.-12. oktober 1994, Proceedings . - Springer-Verlag, 1995. - T. 894. - S. 76–83. — (Forelæsningsnotater i datalogi). - doi : 10.1007/3-540-58950-3_358 .
Christian Duncan, Michael T. Goodrich, Stephen Kobourov. Planar Drawings of Higher-Genus Graphs // Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers . - Springer-Verlag, 2010. - T. 5849. - S. 45–56. — (Forelæsningsnotater i datalogi). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_7 .
Carsten Thomassen. Grafens slægtsproblem er NP-komplet // Journal of Algorithms. - 1989. - T. 10 , no. 4 . — S. 568–576 . - doi : 10.1016/0196-6774(89)90006-0 .
IS Filotti, Gary L. Miller, John Reif. Ved bestemmelse af slægten af en graf i O(v O(g)) trin(Foreløbig rapport) // Proc. 11. år. ACM Symposium on Theory of Computing . - 1979. - S. 27-37. - doi : 10.1145/800135.804395 .
Bojan Mohar. En lineær tidsalgoritme til indlejring af grafer i en vilkårlig overflade // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , no. 1 . — S. 6–26 . - doi : 10.1137/S089548019529248X .
Jonathan Gross, Thomas W. Tucker. Topologisk grafteori . - Dover Publications, 2001. - ISBN 0-486-41741-7 .
A.K. Zvonkin, S.K. Lando. Grafer på overflader og deres anvendelser. - M. : MTSNMO, 2010. - ISBN 978-5-94057-588-7 .
Naoki Katoh, Shin-ichi Tanigawa. Enumerating Constrained Non-crossing Geometric Spanning Trees // Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, 16.-19. juli 2007, Proceedings. - Springer-Verlag, 2007. - T. 4598. - S. 243-253. — ( Forelæsningsnotater i Datalogi ). — ISBN 978-3-540-73544-1 . - doi : 10.1007/978-3-540-73545-8_25 .