Négyszöggráf

Egy négyszöggráf.

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. 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 K₃ szimplexgráfja), a K_1,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 (Chepoi, Dragan & Vaxès 2002) és (Chepoi, Fanciullini & Vaxès 2004) 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

• Bandelt, H.-J.; Chepoi, V. & Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics 24 (4): 1399–1440, DOI 10.1137/090760301.
• Chepoi, V.; Dragan, F. & Vaxès, Y. (2002), "Center and diameter problem in planar quadrangulations and triangulations", Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 346–355.
• Chepoi, V.; Fanciullini, C. & Vaxès, Y. (2004), "Median problem in some plane triangulations and quadrangulations", Comput. Geom. 27 (3): 193–210, DOI 10.1016/j.comgeo.2003.11.002.
• Peterin, I. (2006), "A characterization of planar median graphs", Discussiones Mathematicae Graph Theory 26: 41–48, <http://www.mp.feri.uni-mb.si/osebne/peterin/clanki/planarmedian6.pdf>. Hozzáférés ideje: 2017-03-28 Archiválva 2011. október 5-i dátummal a Wayback Machine-ben.
• Soltan, P.; Zambitskii, D. & Prisǎcaru, C. (1973), Extremal Problems on Graphs and Algorithms of their Solution, Chişinǎu, Moldova: Ştiinţa.

Fordítás

• Ez a szócikk részben vagy egészben a Squaregraph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.