Topologisk grafteori är en gren av grafteorin som studerar inbäddningen av grafer i ytor , rumslig inbäddning och grafer som topologiska utrymmen [1] . Grafnedsänkningar studeras också i denna gren .
Att bädda in en graf i en yta innebär att vi vill rita grafen på en yta, till exempel en sfär , utan att korsa kanter . Det huvudsakliga häckningsproblemet, presenterat som ett matematiskt pussel , är problemet " Hus och brunnar ". Viktigare tillämpningar kan hittas vid framställning av tryckta elektroniska kretsar , där målet är att sprida (bädda in) elektroniska kretsar (graf) på ett kretskort (yta) utan att korsa kretsarna för att undvika kortslutning .
En oriktad graf kan ses som ett abstrakt förenklat komplex C , där delmängderna är enelementsmängder (motsvarande hörn) och tvåelementsmängder (motsvarande kanter) [2] . Geometrisk realisering av komplexet | c | består av kopior av enhetsintervallet [0,1] för varje kant, med ändarna av dessa intervaller limmade samman vid hörnen. Ur denna synvinkel är inbäddningen av en graf i en yta eller en underavdelning av en annan graf ett specialfall av en topologisk inbäddning. En grafhomeomorfism är bara en specialisering av en topologisk homeomorfism , begreppet en sammankopplad graf är detsamma som en topologisk anslutning , och en sammankopplad graf är ett träd om och bara om dess grundläggande grupp är trivial.
Andra enkla komplex som är associerade med grafer inkluderar Whitney- eller klickkomplexen , där delmängderna är klickarna i grafen, och matchande komplex , där undermängderna är matchningarna av grafen (motsvarande klickkomplexen av linjediagrammets komplement ). Matchningskomplexet för en komplett tvådelad graf kallas ett schackbrädekomplex , eftersom det kan beskrivas som ett komplex av uppsättningar av ömsesidigt icke-attackerande torn på ett schackbräde. [3]
John Hopcroft och Robert Tarjan [4] uppnådde en genomsnittlig tid för att kontrollera planariteten hos en graf som är linjär i antalet kanter. Deras algoritm gör detta genom att bygga en grafinbäddning, som de kallar en "palmträd". Effektiviteten av planaritetskontroll är grundläggande för grafvisualisering .
Fan Chang et al [5] studerade problemet med bokinbäddning av en graf med hörn på en linje på ryggraden av en bok. Kanterna på grafen är ritade på olika sidor i boken så att kanterna som ligger på samma sida inte skär varandra. Detta problem är en abstraktion av flerskikts-PCB-layoutproblemet.
Grafinbäddning används också för att bevisa strukturella resultat på grafer genom underordnad grafteori och grafstruktursatsen .