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.[1] 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.[2]
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 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.[2]
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.
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.
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.