A gráfelmélet kezdeti fejlődését jellemzően topológiai és mértani témák motiválták, gondoljunk a königsbergi hidak problémájára, az Euler-féle poliédertételre vagy a síkba rajzolhatóság Kuratowski-tételére. Csak a 20. század második felében terjedt el a gráfok mértani objektumok helyett absztrakt, binér relációként való kezelése. Bár ez az absztrakció sok területen (Ramsey-elmélet, extremális gráfelmélet, algebrai gráfelmélet stb.) gyümölcsözőnek bizonyult, a geometriai alkalmazásokra nem minden esetben tudott megfelelő válaszokkal szolgálni.
A tágabb értelemben vett geometriai gráfelmélet (geometric graph theory) a gráfelmélet nagy kiterjedésű és amorf részterülete, ami mértani eszközökkel definiált gráfokkal foglalkozik. A szűkebb értelemben vett geometriai gráfelmélet geometriai gráfok és topológiai gráfok kombinatorikai és geometriai tulajdonságaival foglalkozik; a geometriai gráfok az euklideszi síkra (vagy más felületre) egyenes, de esetleg egymást metsző szakaszokkal (vagy általánosabban egyszerű görbeívvel) lerajzolt gráfok, míg a topologikus gráfok esetében az élek lerajzolása tetszőleges folytonos görbékkel történik. Így a geometriai gráfelmélet szűkebb értelemben „a geometriai és topologikus gráfok elmélete”.
Geometriai gráfok különböző típusai Egy egyenes élű síkgráf olyan gráf, amelynek csúcsai az euklideszi síkba vannak ágyazva, élei pedig a sík egymást nem metsző egyenes szakaszai. A Fáry-tétel (1948) állítása szerint minden síkgráfhoz tartozik ilyen síkba ágyazás. Az egyenes élű síkgráfok speciális esetei a háromszögelések (sokszög háromszögekre bontása, ponthalmaz háromszögelése). Ezek maximálisak abban az értelemben, hogy nem lehetséges egyenes élekkel kiegészíteni őket. Még speciálisabb eset a Delaunay-háromszögelés: adott ponthalmaz Delaunay-háromszögelése olyan gráf, melyben két csúcs akkor van összekötve, ha létezik csak a két csúcsot tartalmazó kör.
Egy poliéder vagy politóp 1-váza a politóp csúcsainak és éleinek halmaza. Bármely konvex poliéder váza síkba rajzolható, és bármely k-dimenziós konvex politóp váza k-szorosan összefüggő. Megfordítva, a Steinitz-tétel kimondja, hogy minden 3-szorosan összefüggő síkbarajzolható gráf egy konvex poliéder váza; emiatt ezt a gráfosztályt poliédergráfoknak is nevezik.
Egy euklideszi gráf csúcsai a sík pontjai, az éleihez pedig éppen az él két csúcsa között mért távolságot rendeljük. Az euklideszi minimális feszítőfa egy euklideszi teljes gráf minimális feszítőfája. A távolságokat feltételként használva is lehet gráfokat definiálni; például egy egységtávolsággráfban a síkban egységnyi távolságra lévő csúcsok vannak összekötve. A Hadwiger–Nelson-probléma ilyen gráfok kromatikus számával foglalkozik.
Egy metszetgráf olyan gráf, melynek minden csúcsa egy halmaznak felel meg, és két csúcs akkor van összekötve, ha a hozzájuk tartozó halmazok metszete nem üres. Ha ezek a halmazok geometriai objektumok, az eredmény egy geometriai gráf. Például egy dimenzióban egyenes szakaszok metszetgráfja egy intervallumgráf; a síkban egységnyi körlapok metszetgráfja egységkörgráf. A körpakolási tétel szerint a nem metsző körök metszetgráfjai éppen a síkbarajzolható gráfok. A 2009-ben bizonyított Scheinerman-sejtés kimondja, hogy minden síkbarajzolható gráf előállítható a sík egyenes szakaszainak metszetgráfjaként.
Pontok és egyenesek egy geometriai konfigurációjának illeszkedési gráfjában minden csúcs a pontok és egyenesek valamelyikének felel meg, él pedig az illeszkedő pont-egyenes pároknak megfelelő csúcsok között húzódik. A projektív konfigurációk Levi-gráfjai számos fontos szimmetrikus gráfot és cage-et előállítanak.
Egy zárt sokszög láthatósági gráfjában két csúcs akkor van összekötve, ha a csúcsokat összekötő egyenes szakasz teljes egészében a sokszögön belül található. Nem ismert, hogy lehet hatékonyan ellenőrizni, hogy egy irányítatlan gráf előállítható-e láthatósági gráfként.
Egy parciális kocka (hiperkocka izometrikus részgráfja) olyan gráf, melynek csúcsai egy hiperkocka csúcsainak felelnek meg oly módon, hogy a gráfbeli távolságok megegyezzenek a hiperkocka csúcsai közötti Hamming-távolságokkal. Több fontos kombinatorikai struktúra, például egy gráf körmenter orientációi vagy hipersík-konfigurációk régiói közötti szomszédsági viszonyok kifejezhetők parciális kockagráf formájában. A parciális kockák fontos speciális esetei a permutaéderek (három dimenzióban ilyen a csonkított oktaéder), melyek rendezett objektumok permutációnak felelnek meg, éleik pedig a sorba rendezésnek megfelelő cseréket jelölik. Számos más fontos gráfosztály, köztük a mediángráfok definíciója is metrikus beágyazásokon alapul .
A flip gráfok egyik fajtája az euklideszi sík egy ponthalmazának háromszögeléseiből formált gráf, melynek minden csúcsa egy háromszögelésnek felel meg, és két csúcs akkor van összekötve, ha a nekik megfelelő háromszögelés közti különbség éppen egy él cseréje egy másikra. A flip gráfok egyéb változataiban háromszögelés helyett négyszögekre vagy pszeudoháromszögekre osztás szerepel, esetleg magasabb dimenziószámú háromszögelések. Egy konvex sokszög háromszögeléseinek flip gráfja egy asszociéder (Stasheff-politóp) vázát alkotja. Egy ponthalmaz reguláris háromszögelésének (a magasabb dimenziójú konvex burkok projekcióinak) flip gráfja szintén előállhat váz formájában, ez az úgynevezett „másodlagos politóp”.
Kapcsolódó szócikkek Topologikus gráfelmélet Molekulagráf
Fordítás
Jegyzetek
Források
*