Grafinbäddning

En grafinbäddning är en representation av en graf på en given yta studerad inom ramen för topologisk grafteori , där punkter är associerade med grafens hörn och enkla bågar ( homeomorfa bilder [0,1]) på ytan är associerade med grafkanter på ett sådant sätt att: $G$ $\Sigma$ $\Sigma$

ändpunkterna för en båge som är associerade med en kant på grafen är de punkter som är associerade med ändpunkterna på den kanten av grafen $e$ $e$
ingen båge innehåller punkter associerade med andra hörn
inga två bågar skär varandra vid de inre punkterna av dessa bågar.

Här är ytan ett kompakt , sammankopplat 2 - grenrör .

Informellt är en inbäddning av en graf i en yta en bild av grafen på ytan på ett sådant sätt att dess kanter endast kan skära varandra vid ändpunkter. Det är välkänt att vilken finit graf som helst kan bäddas in i ett tredimensionellt euklidiskt utrymme [1] , och plana grafer kan bäddas in i ett tvådimensionellt euklidiskt utrymme . $\mathbb {R} ^{3}$ $\mathbb {R} ^{2}$

Ofta ses en inbäddning som en ekvivalensklass (av homeomorfismer ) av representationer av det beskrivna slaget. $\Sigma$

I samband med grafvisualiseringsproblem övervägs också en svag version av definitionen av grafinbäddning, där frånvaron av kantskärningar inte krävs. Följaktligen beskrivs den starka definitionen som "en inbäddning av en graf utan skärningspunkter" [2] .

Terminologi

Om grafen är inbäddad i en sluten yta , då är komplementet av föreningen av punkter och bågar associerade med grafens hörn och kanter en familj av en familj av regioner (eller ytor) [3] . En tvådimensionell cellinbäddning eller karta är en inbäddning där varje ansikte är homeomorft till en öppen skiva [4] . En tvådimensionell inbäddning av slutna celler är en inbäddning där stängningen av vilket ansikte som helst är homeomorf till en sluten skiva. $G$ $\Sigma$ $G$

Grafstapling används ofta som en synonym för kapsling, särskilt när det gäller plana grafer.

Släktet för en graf är det minsta heltal så att grafen kan bäddas in i släktets yta . I synnerhet har en plan graf genus 0 eftersom den kan ritas på en sfär utan självskärningar. Det icke- orienterbara släktet av en graf är det minsta heltal så att grafen kan bäddas in i en oriktad yta av (icke-orienterbart) släkte [3] . $n$ $n$ $n$ $n$

Euler-släktet för en graf är det minsta heltal så att grafen kan bäddas in i en orienterbar yta av (orienterbart) släkte eller en oriktad yta av (icke-orienterbart) genus . En graf är helt enkelt orienterbar om dess Euler-släkte är mindre än dess icke-orienterbara genus. $n$ ${\tfrac {n}{2))$ $n$

Det maximala släktet för en graf är det maximala heltal så att grafen kan bäddas in med platt cell (inbäddning är platt cell om någon sluten kurva som inte skär grafens kanter drar ihop sig till en punkt) i en orienterbar yta av släkte . $n$ $n$

Kombinatorisk inbäddning

En kapslad graf definierar unikt de cykliska ordningsföljderna av kanter som faller in på samma vertex. Mängden av alla dessa cykliska ordningar kallas det cirkulära systemet . Inbäddningar med samma cirkulära system anses vara likvärdiga, och motsvarande ekvivalensklass av inbäddningar kallas en kombinatorisk inbäddning (till skillnad från termen topologisk inbäddning , som syftar på den tidigare definitionen av punkter och kurvor). Ibland kallas ett cirkulärt system i sig för en "kombinatorisk inbäddning" [5] [6] [7] .

Den kapslade grafen definierar också naturliga cykliska kantordningar som definierar gränserna för kapslingsytorna. Att arbeta med dessa facettorienterade ordningar är dock mindre uppenbart, eftersom vissa kanter i vissa fall kan korsas två gånger när man korsar gränsen för ett ansikte. Detta gäller till exempel alltid när man häckar träd som har en enda kant. För att övervinna detta kombinatoriska hinder kan man betrakta varje kant som "delad" i två "halvkanter" eller "sidor". Enligt dessa konventioner, i alla ytor, korsar gränsen varje halvkant endast en gång, och varje halvkant av en kant korsas alltid i motsatta riktningar.

Beräkningskomplexitet

Problemet med att bestämma släktet för en graf är NP-komplett (problemet med att avgöra om en graf med hörn har släktet är NP-komplett ) [8] . $n$ $g$

Samtidigt är problemet med att bestämma släktet för en graf fast-parametriskt lösbart , det vill säga algoritmer med polynomtid för att kontrollera om en graf kan bäddas in i en yta med ett givet släkte är kända. Detsamma gäller för att hitta en anknytning.

Det första genombrottet kom 1979 när tidskomplexitetsalgoritmer rapporterades oberoende av det årliga ACM Symposium on Computational Theory - en föreslagen av Ion Filotti och Gary Miller och en annan av John Reif . Deras tillvägagångssätt var helt olika, men på förslag från organisationskommittén lade de in en sammanslagen artikel [9] . $O(n^{O(g)})$

1999 visades det att fallet med fast släkte kan lösas i linjär tid i grafstorlek och i dubbel exponentiell tid i släkte [10] .

Inbäddning av en graf i utrymmen med högre dimensioner

Det är känt att vilken finit graf som helst kan bäddas in i ett tredimensionellt utrymme [1] .

En metod för en sådan inbäddning är att placera punkter (grafhörn) på en linje och rita kanterna som kurvor som ligger i separata halvplan som har denna linje som en gräns gemensam för alla halvplan. Denna typ av inbäddning kallas en grafbokinbäddning . Denna metafor blir tydlig om vi föreställer oss varje halvplan som en sida i en bok. Det är tydligt att vissa kanter kan ritas utan skärningspunkter på samma "sida". Boktjockleken för en graf är det minsta antalet halvplan i en bokinbäddning.

Å andra sidan kan vilken finit graf som helst ritas utan skärningspunkter i tredimensionellt utrymme med raka kanter genom att placera hörnen i en allmän position så att inga fyra är i samma plan (inte ligger i samma plan). Detta kan till exempel uppnås genom att placera den -:e vertexen vid en punkt på momentkurvan . $i$ $(i,i^{2},i^{3})$

En inbäddning av en graf i ett tredimensionellt utrymme där inga två cykler är topologiskt sammanlänkade kallas en olänkad inbäddning . En graf har en olänkad inbäddning om och endast om den inte innehåller någon av de sju graferna i Peterson-familjen som en mindre .

Se även

Dubbelt länkad lista över kanter - en datastruktur för att representera en graf inbäddad i ett plan
Rätt kort
Faris teorem , som säger att det alltid finns en inbäddning i planet för en plan graf där alla bågar representeras av linjesegment.

Anteckningar

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

Litteratur

Robert F. Cohen, Peter Eades, Tao Lin, Frank Ruskey. Grafritning: 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. — ( Lecture Notes in Computer Science ). - 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. — (Föreläsningsanteckningar i datavetenskap). - 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. — (Föreläsningsanteckningar i datavetenskap). - 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, 22-25 september 2009, Revised Papers . - Springer-Verlag, 2010. - T. 5849. - S. 45-56. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_7 .
Carsten Thomassen. Grafens släktproblem är NP-komplett // Journal of Algorithms. - 1989. - T. 10 , nr. 4 . — S. 568–576 . - doi : 10.1016/0196-6774(89)90006-0 .
IS Filotti, Gary L. Miller, John Reif. Vid bestämning av släktet för en graf i O(v O(g)) steg (Preliminär rapport) // Proc. 11:e år. ACM Symposium on Theory of Computing . - 1979. - S. 27-37. - doi : 10.1145/800135.804395 .
Bojan Mohar. En linjär tidsalgoritm för att bädda in grafer i en godtycklig yta // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , nr. 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å ytor och deras tillämpningar. - 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, Kanada, 16-19 juli 2007, Proceedings. - Springer-Verlag, 2007. - T. 4598. - S. 243-253. — ( Lecture Notes in Computer Science ). — ISBN 978-3-540-73544-1 . - doi : 10.1007/978-3-540-73545-8_25 .