Térképgráf
Sablon:Több kép A matematika, azon velül a gráfelmélet területén egy térképgráf (map graph) az euklideszi sík véges sok darab, egyszerűen összefüggő, belső részüket tekintve diszjunkt régiójának metszetgráfja. A térképgráfok közé tartoznak a síkbarajzolható gráfok, de annál általánosabb fogalom. Akárhány régió találkozhat egyetlen közös pontban (mint az USA Négysarok régiója, ahol négy állam találkozik), és ilyenkor a térképgráf a megfelelő csúcsok alkotta klikket fog tartalmazni, a síkgráfoktól eltérően, ahol a legnagyobb klikkek csak négy csúcsból állhatnak.[1] A térképgráfok egy másik példája a királygráf, a sakktábla mezőinek térképgráfja, ami azokat a mezőknek megfelelő csúcsokat köti össze, melyek között a király mozoghat.
Kombinatorikai reprezentáció
A térképgráfok kombinatorikailag kifejezhetők „páros síkbarajzolható gráfok félnégyzeteiként”. Legyen Sablon:Math egy síkbarajzolható páros gráf, a bipartíció legyen Sablon:Math. A Sablon:Mvar négyzete a Sablon:Mvar csúcshalmazával rendelkező olyan gráf, melyben két csúcs akkor szomszédos, ha legfeljebb két lépés távolságra vannak Sablon:Mvar-ben. A gráf félnégyzete a gráf négyzetében a bipartíció egyik felének (mondjuk Sablon:Mvar-nek) a feszített részgráfja: csúcshalmaza a Sablon:Mvar, és Sablon:Mvar azon csúcsai között szerepelnek élek, melyek két lépés távolságra vannak Sablon:Mvar-ben. Ez a félnégyzet egy térképgráf. Mértanilag úgy is ábrázolható, hogy Sablon:Mvar-nek megkeressük egy síkba rajzolását, majd Sablon:Mvar minden csúcsát és a velük szomszédos éleket csillag alakú régióvá növesztjük úgy, hogy ezek a régiók Sablon:Mvar csúcsaiban érintkezzenek. Megfordítva, minden térképgráfnak létezik ilyen félnégyzet-reprezentációja.[1]
Számítási bonyolultság
A térképgráfok felismerésére létezik polinom idejű algoritmus, az eddig ismert legjobb ilyen algoritmus azonban olyan magas kitevővel rendelkezik (), hogy a gyakorlatban nem praktikus a használata.[2] A maximális elemszámú független csúcshalmaz problémának térképgráfok esetében van polinomiális approximációs sémája, és a kromatikus számuk is 2 faktorral polinom időben becsülhető.[3] A bidimenzionalitás-elmélet segítségével a térképgráfok optimalizálási problémáinak számos más közelítő algoritmusához és rögzített paraméter mellett kezelhető algoritmusához jutottak el.[4][5][6]
Változatok és kapcsolódó fogalmak
Egy Sablon:Mvar-térképgráf olyan régiók halmazából állítható elő, melyek közül legfeljebb Sablon:Mvar találkozik egyetlen pontban. Ezzel ekvivalens megfogalmazás szerint egy páros síkbarajzolható gráf félnégyzete, melyben az Sablon:Mvar csúcshalmaz (a bipartíció azon fele, mely nem vett részt a félnégyzet-műveletben) maximális fokszáma Sablon:Mvar. A 3-térképgráfok mind síkbarajzolhatók, és minden síkbarajzolható gráfnak van 3-térképgráf reprezentációja. Minden 4-térképgráf 1-síkgráf, azaz élenként legfeljebb egy metszéssel lerajzolható gráf, és minden optimális 1-síkgráf (a sík egy négyszögeléséből minden négyszögű tartományhoz két metsző átló hozzáadásával kapott gráf) pedig 4-térképgráf. A nem optimális 1-síkgráfok azonban nem térképgráfok, mert (a térképgráfoktól eltérően) tartalmaznak olyan metsző éleket, melyek nem egy 4 csúcsú klikk részei.[1]