Gráfica que representa la tangencia entre objetos geométricos
En el área matemática 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 cuyos bordes 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 restringir las formas en que se permite que los objetos subyacentes se intersequen entre sí.
El teorema de empaquetamiento de círculos [2] establece que todo grafo plano puede representarse como un grafo de contacto de círculos. Los grafos de contacto de círculos unitarios se denominan grafos de centavo . [3] También se han estudiado representaciones como grafos de contacto de triángulos , [4] rectángulos , [5] cuadrados , [6] segmentos de línea , [7] o arcos circulares [8] .
Referencias
- ^ Chaplick, Steven; Kobourov, Stephen G.; Ueckerdt, Torsten (2013), "Gráficos equiláteros de contacto L", en Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Alemania, 19-21 de junio de 2013, Documentos revisados , Lecture Notes in Computer Science, vol. 8165, Springer, págs. 139–151, arXiv : 1303.1279 , doi :10.1007/978-3-642-45043-3_13, S2CID 13541242
- ^ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akád. Wiss. Leipzig, Matemáticas-Física. kl. , 88 : 141-164
- ^ 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 desde el original (PDF) el 2022-01-19 , consultado el 2017-02-19; véase especialmente la pág. 176
- ^ de Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1994), "Sobre los grafos de contacto triangulares", Combinatorics, Probability and Computing , 3 (2): 233–246, doi :10.1017/S0963548300001139, MR 1288442, S2CID 46160405
- ^ Buchsbaum, Adam L.; Gansner, Emden R.; Procopiuc, Cecilia M.; Venkatasubramanian, Suresh (2008), "Diseños rectangulares y gráficos de contacto", ACM Transactions on Algorithms , 4 (1): Art. 8, 28, arXiv : cs/0611107 , doi :10.1145/1328911.1328919, MR 2398588, S2CID 1038771
- ^ Klawitter, Jonathan; Nöllenburg, Martin; Ueckerdt, Torsten (2015), "Propiedades combinatorias de los arreglos de rectángulos sin triángulos y el problema de la cuadratura", Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Ángeles, CA, EE. UU., 24-26 de septiembre de 2015, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 9411, Springer, págs. 231–244, arXiv : 1509.00835 , doi :10.1007/978-3-319-27261-0_20, S2CID 18477964
- ^ Hliněný, Petr (2001), "Los gráficos 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
- ^ Alam, Md. Jawaherul; Eppstein, David ; Kaufmann, Michael; Kobourov, Stephen G.; Pupyrev, Sergey; Schulz, André; Ueckerdt, Torsten (2015), "Gráficos de contacto de arcos circulares", Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canadá, 5-7 de agosto de 2015, Actas , Lecture Notes in Computer Science, vol. 9214, Springer, págs. 1–13, arXiv : 1501.00318 , doi :10.1007/978-3-319-21840-3_1, S2CID 6454732
