Érintőgráf
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.[1]
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,[2] 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[szerkesztés]
- 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.[1]
Érintőgráfokkal kapcsolatos eredmények[szerkesztés]
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.[3]
A tengely-igazított szakaszok kontaktgráfjai (rács-érintőgráfok)[4]) pontosan megegyeznek a síkba rajzolható páros gráfokkal.[5][6][7][8]
A háromszögmentes síkgráfok reprezentálhatók legfeljebb három lépcsőjű töröttvonal-szegmensek érintőgráfjaiként.[9] Megvalósíthatók továbbá tengely-igazított szaakszok, L-alakok és Γ-alakok érintőgráfjaiként is.[10]
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.[11]
A Schnyder-realizer segítségével konstruálható síkgráfok T-érintőgráfja vagy háromszög-érintőgráfja.[12]
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.[13] 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.[14]
Bármely síkgráf rendelkezik „megfelelő” érintőgráf-reprezentációval egymást érintő téglatesteket (tengely-illesztett dobozokat) felhasználva,[15] egy erősebb állítás szerint pedig bármely síkgráf reprezentálható négyzet alapú hasábok érintőrendszereként.[1] 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).[16]
Jegyzetek[szerkesztés]
- ↑ a b c Chaplick, Steven; G. Kobourov, Stephen; Ueckerdt, Torsten (2013-06-19). "Equilateral L-Contact Graphs"
- ↑ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88: 141–164
- ↑ 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
- ↑ http://www.cs.toronto.edu/~stacho/public/gridcontact.pdf
- ↑ (1991. január 19.) „On grid intersection graphs”. Discrete Mathematics 87 (1), 41-52. o. DOI:10.1016/0012-365X(91)90069-E. (Hozzáférés: 2016. szeptember 3.)
- ↑ 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, 1991
- ↑ P. Rosenstiehl and R. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete & Computational Geometry, 1:343–353, 1986.
- ↑ 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
- ↑ S. Chaplick and T. Ueckerdt. Planar graphs as VPG-graphs. In 20th Symp. on Graph Drawing, pages 174–186, 2013
- ↑ (2012. szeptember 1.) „Proportional Contact Representations of Planar Graphs”. Journal of Graph Algorithms and Applications 16 (3), 701-728. o. DOI:10.7155/jgaa.00276. (Hozzáférés: 2016. szeptember 3.)
- ↑ H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability & Computing, 3:233–246, 1994.
- ↑ 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.
- ↑ 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.
- ↑ C. Thomassen. Interval representations of planar graphs. J. Comb. Theory, Ser. B, 40(1):9– 20, 1986.
- ↑ S. Felsner and M. C. Francis. Contact representations of planar graphs with cubes. In Proc. 27th Symposium on Computational Geometry, pages 315–320, 2011