A matematika, azon belül a gráfelmélet területén egy négyszöggráf (squaregraph) egy irányítatlan gráf, ami síkba rajzolható oly módon, hogy a lerajzolás minden belső tartománya négyszög, és minden három vagy kevesebb szomszéddal rendelkező csúcs rajta van egy nem korlátos tartományon.
Kapcsolódó gráfcsaládok A négyszöggráfok közé tartoznak a fák, a rácsgráfok, a fogaskerékgráfok és a poliominók gráfjai.
A négyszöggráfok amellett, hogy síkgráfok, mediángráfok is, tehát bármely három u, v és w csúcsra igaz, hogy létezik olyan egyedi medián tulajdonságú m(u,v,w) csúcs, ami a három csúcs között páronként legrövidebb utakon fekszik.. Lásd -ot a síkba rajzolható medián gráfok leírásához. Ahogy az összes medián gráfok is, a négyszöggráfok is mind hiperkockák részgráfjai (partial cube): csúcsaik címkézhetők bitfüzérekkel oly módon, hogy két füzér Hamming-távolsága megegyezzen a csúcsok közötti legrövidebb út hosszával.
Ha egy négyszöggráfból képezünk egy gráfot oly módon, hogy az új gráf minden csúcsa a négyszöggráf egy zónájának feleljen meg (a négyszögek párhuzamos éleinek ekvivalenciaosztálya) és a közös négyszögben találkozó zónák közé pedig élt húzunk, akkor húrmetszetgráfot kapunk.
Karakterizáció A négyszöggráfok a síkba ágyazásukon kívül másképpen is karakterizálhatók:. Azok a mediángráfok, melyek nem tartalmazzák feszített részgráfként a tiltott gráfok végtelen osztályának egyik tagját sem. Ebben az esetben a tiltott gráfok közé tartoznak: a K3 szimplexgráfja), a K1,3 karomgráf és egy él Descartes-szorzata (a karom szimplexgráfja) és a fogaskerékgráfokból a kerékagyhoz egy csúcs csatlakoztatásával kapott gráfok (egy körgráf és egy izolált csúcs diszjunkt uniójából álló gráf szimplexgráfjai). Azok az összefüggő és páros gráfok, melyekre igaz, hogy (bármely r csúcsot választva a gráf gyökerének) minden csúcsnak legfeljebb két, r-hez nála közelebbi csúcsa van és bármely v csúcsára, a v csúcs linkje (az a gráf, melyben egy csúcs szerepel minden v-ből kiinduló élhez, él pedig a v-t tartalmazó 4-körökhöz tartozik) pedig vagy háromnál hosszabb kör, vagy utak diszjunkt uniója. A hiperbolikus sík azon egyeneselrendezéseinek duális gráfjai, melyek nem tartalmaznak három, egymást kölcsönösen metsző egyenest.
Algoritmusok A négyszöggráfoknak a gyökércsúcstól való távolságon és a csúcsok linkjein alapuló karakterizálása egy szélességi kereséssel együtt egy a négyszöggráfokat tesztelő lineáris idejű algoritmus alapját képezi, és így nincs szükség az általános gráfok síkgráf voltának tesztelésére használt bonyolultabb, lineáris idejű algoritmusokra.
Számos algoritmikus probléma egyszerűbben kiszámítható a négyszöggráfokon, mint az általánosabb síkgráfokon vagy mediángráfokon; például és lineáris idejű algoritmusokat mutat a négyszöggráfok átmérőjének meghatározására, továbbá a csúcsoktól való maximális távolság tekintetében minimális csúcs megkeresésére.
Jegyzetek
. . . . .
Fordítás
Kategória:Gráfcsaládok Kategória:Síkgráfok Kategória:Páros gráfok