Hispanopedia Wiki
Articulo de referencia

Gráfico de contacto

En el ámbito matemático de la teoría de grafos , un grafo de contacto o grafo de tangencia es un grafo cuyos vértices están representados por objetos geométricos (por ejemplo, c...

Hispanopedia WikiContenido en espanolLectura gratuita

En el ámbito matemático de la teoría de grafos , un grafo de contacto o grafo de tangencia es un grafo cuyos vértices están representados por objetos geométricos (por ejemplo, curvas , segmentos de línea o polígonos ) y cuyas aristas corresponden a dos objetos que se tocan (pero no se cruzan) según alguna noción específica. [ 1 ] Es similar a la noción de grafo de intersección , pero se diferencia de ella en que restringe las formas en que los objetos subyacentes pueden intersecarse entre sí.

El teorema del empaquetamiento de círculos [ 2 ] establece que todo grafo planar puede representarse como un grafo de contacto de círculos, conocido como grafo de monedas . El teorema del empaquetamiento de monstruos de Oded Schramm generaliza esto: todo grafo planar es un grafo de contacto de copias homotéticas de cualquier conjunto convexo suave dado . [ 3 ] Los grafos de contacto de círculos unitarios se llaman grafos de monedas . [ 4 ] También se han estudiado representaciones como grafos de contacto de triángulos , [ 5 ] rectángulos , [ 6 ] cuadrados , [ 7 ] segmentos de línea , [ 8 ] o arcos circulares [ 9 ] .

Referencias

  1. ↑ Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten (2013), "Grafos de contacto L equiláteros", en Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Conceptos de teoría de grafos en informática - 39.º Taller Internacional, WG 2013, Lübeck, Alemania, 19-21 de junio de 2013, Artículos revisados , Lecture Notes in Computer Science, vol.  8165, Springer, pp. 139–151 , arXiv : 1303.1279 , doi : 10.1007/978-3-642-45043-3_13 , ISBN  978-3-642-45042-6, S2CID 13541242 
  2. ^ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akád. Wiss. Leipzig, Matemáticas-Física. kl. , 88 : 141-164​
  3. ↑ Schramm, Oded (1990), Empaquetamiento de cuerpos bidimensionales con combinatoria prescrita y aplicaciones a la construcción de mapeos conformes y cuasiconformes (tesis doctoral), Universidad de Princeton, ProQuest 303827410 ; modificado y reimpreso como "Empaquetamientos prescritos combinatoriamente y aplicaciones a mapas conformes y cuasiconformes", arXiv : 0709.0710 , 2007
  4. ↑ Pisanski, Tomaž ; Randić, Milan (2000), "Puentes entre la geometría y la teoría de grafos" (PDF) , en Gorini, Catherine A. (ed.), Geometry at Work , MAA Notes, vol. 53, Cambridge University Press, pp. 174–194 , MR 1782654 , archivado del original (PDF) el 19-01-2022 , recuperado el 19-02-2017   ; véase especialmente la página  176
  5. ↑ de Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1994), "Sobre grafos de contacto triangulares", Combinatoria, Probabilidad y Computación , 3 (2): 233– 246, doi : 10.1017/S0963548300001139 , MR 1288442 , S2CID 46160405  
  6. ↑ Buchsbaum, Adam L.; Gansner, Emden R.; Procopiuc, Cecilia M.; Venkatasubramanian, Suresh (2008), "Diseños rectangulares y grafos de contacto", ACM Transactions on Algorithms , 4 (1): Art. 8, 28, arXiv : cs/0611107 , doi : 10.1145/1328911.1328919 , MR 2398588 , S2CID 1038771  
  7. ↑ Klawitter, Jonathan; Nöllenburg, Martin; Ueckerdt, Torsten (2015), "Propiedades combinatorias de arreglos de rectángulos sin triángulos y el problema de la cuadrabilidad", Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers , Lecture Notes in Computer Science, vol. 9411, Springer, pp. 231–244 , arXiv : 1509.00835 , doi : 10.1007/978-3-319-27261-0_20 , ISBN   978-3-319-27260-3, S2CID 18477964 
  8. ↑ Hliněný, Petr (2001), "Los grafos de contacto de segmentos de línea son NP-completos" (PDF) , Matemáticas Discretas , 235 ( 1–3 ): 95–106 , doi : 10.1016/S0012-365X(00)00263-6 , MR 1829839 
  9. ↑ Alam, Md. Jawaherul; Eppstein, David ; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey; Schulz, André; Ueckerdt, Torsten (2015), "Grafos de contacto de arcos circulares", Algoritmos y estructuras de datos: 14.º Simposio Internacional, WADS 2015, Victoria, BC, Canadá, 5-7 de agosto de 2015, Actas , Lecture Notes in Computer Science, vol. 9214, Springer, pp. 1–13 , arXiv : 1501.00318 , doi : 10.1007/978-3-319-21840-3_1 , ISBN   978-3-319-21839-7, S2CID 6454732