Squaregraph - Squaregraph

Čtvercový graf.

v teorie grafů, pobočka matematika, a squaregraph je typ neorientovaný graf to může být nakreslen v rovině takovým způsobem, že každý ohraničený tvář je čtyřúhelník a každý vrchol se třemi nebo méně sousedy je incident s neomezenou tváří.

Související třídy grafů

Squaregraphs zahrnují jako zvláštní případy stromy, mřížkové grafy, převodové grafy a grafy polyominos.

Stejně jako bytí rovinné grafy, grafy jsou střední grafy, což znamená, že pro každé tři vrcholy u, proti, a w existuje jedinečný střední vrchol m(u,proti,w), který leží na nejkratších cestách mezi každou dvojicí tří vrcholů.[1] Stejně jako u průměrných grafů obecně platí, že i čtvercové grafy dílčí kostky: jejich vrcholy lze označit binární řetězce takové, že Hammingova vzdálenost mezi řetězci se rovná nejkratší vzdálenosti dráhy mezi vrcholy.

Graf získaný ze čtvercového grafu vytvořením vrcholu pro každou zónu (třída ekvivalence rovnoběžných hran čtyřúhelníků) a okraj pro každé dvě zóny, které se setkávají ve čtyřúhelníku, je kruhový graf určeno a bez trojúhelníků akordové schéma disku jednotky.[2]

Charakterizace

Čtvercové grafy lze charakterizovat několika způsoby, jinými než pomocí jejich plošných vložek:[2]

  • Jsou to střední grafy které neobsahují jako indukovaný podgraf jakýkoli člen nekonečné rodiny zakázané grafy. Tyto zakázané grafy jsou krychle ( simplexní graf z K.3), kartézský součin hrany a dráp K.1,3 (simplexní graf drápu) a grafy vytvořené z a převodový graf přidáním jednoho dalšího vrcholu připojeného k náboji kola (simplexní graf disjunktního spojení cyklu s izolovaným vrcholem).
  • Jsou to grafy, které jsou spojeny a bipartitní, takový, že (pokud je libovolný vrchol r je vybrán jako vykořenit ) každý vrchol má maximálně dva sousedy blíže r, a to tak, že na každém vrcholu proti, odkaz na proti (graf s vrcholem pro každou hranu dopadající na proti a hrana pro každý 4-cyklus obsahující proti) je buď cyklus délky větší než tři, nebo disjunktní sjednocení cest.
  • Jsou to duální grafy z uspořádání vedení v hyperbolická rovina které nemají tři vzájemně se protínající čáry.

Algoritmy

Společně s lze použít charakterizaci grafů, pokud jde o vzdálenost od kořene a odkazy vrcholů šířka první vyhledávání jako součást a lineární čas algoritmus pro testování, zda je daný graf čtvercový graf, aniž by bylo nutné používat složitější algoritmy lineárního času testování rovinnosti libovolných grafů.[2]

Několik algoritmických problémů na grafech lze vypočítat efektivněji než v obecnějších rovinných nebo středních grafech; například, Chepoi, Dragan & Vaxès (2002) a Chepoi, Fanciullini a Vaxès (2004) současné lineární časové algoritmy pro výpočet průměr squaregraphs a pro nalezení vrcholu minimalizujícího maximální vzdálenost ke všem ostatním vrcholům.

Poznámky

  1. ^ Soltan, Zambitskii a Prisǎcaru (1973). Vidět Peterin (2006) pro diskusi o rovinných středních grafech obecněji.
  2. ^ A b C Bandelt, Chepoi a Eppstein (2010).

Reference

  • Bandelt, H.-J .; Chepoi, V .; Eppstein, D. (2010), „Kombinatorika a geometrie konečných a nekonečných čtvercových grafů“, SIAM Journal on Discrete Mathematics, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301, S2CID  10788524.
  • Chepoi, V .; Dragan, F .; Vaxès, Y. (2002), "Problém středu a průměru v rovinných kvadrangulacích a triangulacích", Proc. 13. Annu. ACM – SIAM Symp. o diskrétních algoritmech (SODA 2002), str. 346–355.
  • Chepoi, V .; Fanciullini, C .; Vaxès, Y. (2004), "Mediánový problém v některých rovinných triangulacích a kvadrangulacích", Comput. Geom., 27 (3): 193–210, doi:10.1016 / j.comgeo.2003.11.002.
  • Peterin, Iztok (2006), "Charakterizace rovinných středních grafů", Diskuse Mathematicae Graph Theory, 26 (1): 41–48, doi:10,7151 / dmgt.1299
  • Soltan, P .; Zambitskii, D .; Prisǎcaru, C. (1973), Extrémní problémy grafů a algoritmů jejich řešení (v ruštině), Chişinǎu, Moldavsko: Ştiinţa.