A matematika, azon belül a gráfelmélet területén egy érintőgráf (tangency graph) vagy kontaktgráf (contact graph) olyan gráf, melynek csúcsai mértani objektumoknak (pl. görbék, egyenes szakaszok vagy sokszögek), élei pedig ezen objektumok valamilyen értelemben vett érintkezésének feleltethetők meg.Chaplick, Steven; G. Kobourov, Stephen; Ueckerdt, Torsten (2013-06-19). "Equilateral L-Contact Graphs"
Ismert, hogy a síkgráfoknak többféle mértani reprezentációja létezik, pl. előállíthatók körlapok, háromszögek – vagy a páros gráfok esetében – függőleges és vízszintes egyenes szakaszok érintőgráfjaiként is.
A szakirodalom nagy terjedelemben foglalkozik a síkgráfok kontaktgráfként való előállításával. Az egyik korai eredmény Koebe 1936-ban született tétele, mely szerint minden síkgráf előállítható egymást érintő körlapok segítségével (tehát, hogy minden síkgráfnak létezik érmegráf-reprezentációja).
Példák érintőgráfokra Háromszög-érintőgráfok Körlap-érintőgráfok (érmegráfok) (négyzet alapú) téglatest-érintőgráfok T-érintőgráfok (a csúcsok tengely-igazított T alakok, az élek a T-k közötti érintkezéseket jelzik) (egyenlő szárú) L-érintőgráfok (a csúcsok tengely-igazított L alakok, az élek az L-ek közötti érintkezéseket jelzik); minden L-reprezentációhoz tartozik vele ekvivalens reprezentáció, ahol az L-ek szárai egyenlő hosszúságúak.
Érintőgráfokkal kapcsolatos eredmények Koebe–Andreev–Thurston-féle körpakolási tétel: a körlapok érintőgráfjai pontosan a síkgráfok. Számos alkalmazása van a gráfelméletben, a gráfábrázolás, hálógenerálás területén, a neuroanatómiában stb.M. J. Alam, D. Eppstein, M. Kaufmann, S. G. Kobourov, S. Pupyrev, A. Schulz, and T. Ueckerdt: Contact Graphs of Circular Arcs in 14th Algorithms and Data Structures Symp. (WADS 2015) Victoria, BC, August 2015
A tengely-igazított szakaszok kontaktgráfjai (rács-érintőgráfok)http://www.cs.toronto.edu/~stacho/public/gridcontact.pdf) pontosan megegyeznek a síkba rajzolható páros gráfokkal.J. Czyzowicz, E. Kranakis, and J. Urrutia. A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments. Information Processing Letters, 66(3):125–126, 1998.H. de Fraysseix, P. Ossona de Mendez, and J. Pach. Representation of planar graphs by segments. Intuitive Geometry, 63:109–117, 1991P. Rosenstiehl and R. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete & Computational Geometry, 1:343–353, 1986.
A háromszögmentes síkgráfok reprezentálhatók legfeljebb három lépcsőjű töröttvonal-szegmensek érintőgráfjaiként.N. de Castro, F. Cobos, J. Dana, A. Marquez, and M. Noy. Triangle-free planar graphs and segment intersection graphs. J. of Graph Algorithms and Applications, 6(1):7–26, 2002 Megvalósíthatók továbbá tengely-igazított szaakszok, L-alakok és Γ-alakok érintőgráfjaiként is.S. Chaplick and T. Ueckerdt. Planar graphs as VPG-graphs. In 20th Symp. on Graph Drawing, pages 174–186, 2013
A nem tengely-igazított szakaszok érintőgráfjai pontosan azok a síkgráfok, melyekben k csúcshoz mindig legfeljebb 2k − 3 élű feszített részgráf tartozik.
A Schnyder-realizer segítségével konstruálható síkgráfok T-érintőgráfja vagy háromszög-érintőgráfja.H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability & Computing, 3:233–246, 1994.
A síkba rajzolható Laman-gráfok reprezentálhatók L-érintőgráfokként, ha az L-alakok mind a négy 90°-ban elforgatott alakja jelen lehet.S. Kobourov, T. Ueckerdt, and K. Verbeek. Combinatorial and geometric properties of planar Laman graphs. In 24th Symp. on Discrete Algorithms (SODA), pages 1668–1678. 2013. A síkba rajzolható Laman-gráfok a síkgráfok fontos osztályait tartalmazzák (soros-párhuzamos gráfok, külsíkgráfok, síkba rajzolható 2-fák stb.) és a merevségelmélettel való kapcsolatuk miatt használják őket a strukturális mechanikában, kémiában és fizikában is.R. Haas, D. Orden, G. Rote, F. Santos, B. Servatius, H. Servatius, D. Souvaine, I. Streinu, and W. Whiteley. Planar minimally rigid graphs and pseudo-triangulations. Computational Geometry, 31:31–61, 2005.
Bármely síkgráf rendelkezik „megfelelő” érintőgráf-reprezentációval egymást érintő téglatesteket (tengely-illesztett dobozokat) felhasználva,C. Thomassen. Interval representations of planar graphs. J. Comb. Theory, Ser. B, 40(1):9– 20, 1986. egy erősebb állítás szerint pedig bármely síkgráf reprezentálható négyzet alapú hasábok érintőrendszereként. Bármely síkgráfnak létezik (nem szükségképpen „megfelelő”) reprezentációja kockák érintőrendszereként (egy „megfelelő” reprezentációban a téglatestek területe sohasem nulla).S. Felsner and M. C. Francis. Contact representations of planar graphs with cubes. In Proc. 27th Symposium on Computational Geometry, pages 315–320, 2011
Jegyzetek
Kapcsolódó szócikkek Metszetgráf
Kategória:Gráfcsaládok