Topologisk grafteori er en gren af grafteori, der studerer indlejring af grafer i overflader , rumlig indlejring og grafer som topologiske rum [1] . Graffordybelser studeres også i denne gren .
Indlejring af en graf i en overflade betyder, at vi ønsker at tegne grafen på en overflade, såsom en kugle , uden at krydse kanter . Det vigtigste redeproblem, præsenteret som et matematisk puslespil , er " Huse og brønde "-problemet. Flere vigtige anvendelser kan findes i udarbejdelsen af trykte elektroniske kredsløb , hvor målet er at sprede (indlejre) elektroniske kredsløb (graf) på et printkort (overflade) uden at krydse kredsløbene for at undgå kortslutninger .
En urettet graf kan ses som et abstrakt forenklet kompleks C , hvor delmængderne er et-elementmængder (svarende til toppunkter) og to-elementmængder (svarende til kanter) [2] . Geometrisk realisering af komplekset | c | består af kopier af enhedsintervallet [0,1] for hver kant, med enderne af disse intervaller limet sammen i hjørnerne. Fra dette synspunkt er indlejring af en graf i en overflade eller en underopdeling af en anden graf et specialtilfælde af en topologisk indlejring. En grafhomeomorfisme er blot en specialisering af en topologisk homøomorfisme , begrebet en forbundet graf er det samme som en topologisk forbindelse , og en forbundet graf er et træ, hvis og kun hvis dens grundlæggende gruppe er triviel.
Andre simple komplekser forbundet med grafer omfatter Whitney- eller klikkomplekserne , hvor delmængderne er grafens kliker , og de matchende komplekser , hvor delmængderne er grafens matchninger (tilsvarende klikkomplekserne af linjegrafens komplement ). Det matchende kompleks af en komplet todelt graf kaldes et skakbrætkompleks , da det kan beskrives som et kompleks af sæt af indbyrdes ikke-angribende tårne på et skakbræt. [3]
John Hopcroft og Robert Tarjan [4] opnåede en gennemsnitlig tid til at kontrollere planheden af en graf, der er lineær i antallet af kanter. Det gør deres algoritme ved at bygge en grafindlejring, som de kalder et "palmetræ". Effektiviteten af planaritetskontrol er grundlæggende for grafvisualisering .
Fan Chang et al. [5] undersøgte problemet med bogindlejring af en graf med hjørner på en linje på rygraden af en bog. Kanterne af grafen er tegnet på forskellige sider af bogen, så de kanter, der ligger på samme side, ikke skærer hinanden. Dette problem er en abstraktion af flerlags PCB-layoutproblemet.
Grafindlejring bruges også til at bevise strukturelle resultater på grafer gennem underordnet grafteori og grafstruktursætningen .