En el área matemática de la teoría de grafos , un grafo de contacto o grafo de tangencia es un gráfico 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) de acuerdo con alguna noción especificada. [1] Es similar a la noción de gráfico de intersección, pero se diferencia de ella en restringir las formas en que los objetos subyacentes pueden cruzarse entre sí.
El teorema del empaquetamiento de círculos [2] establece que cada gráfico plano se puede representar como un gráfico de contacto de círculos. Las gráficas de contacto de los círculos unitarios se denominan gráficas de centavo . [3] También se han estudiado las representaciones como gráficos de contacto de triángulos , [4] rectángulos , [5] cuadrados , [6] segmentos de línea , [7] o arcos circulares [8] .
Referencias
- ^ Chaplick, Steven; G. Kobourov, Stephen; Ueckerdt, Torsten (19 de junio de 2013). "Gráficos de contacto L equilátero". arXiv : 1303.1279 . PDF en línea
- ^ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. , 88 : 141–164
- ^ Pisanski, Tomaž ; Randić, Milán (2000), "Puentes entre geometría y teoría de grafos" (PDF) , en Gorini, Catherine A. (ed.), Geometry at Work , MAA Notes, 53 , Cambridge University Press, págs. 174-194, MR 1782654. Ver especialmente la p. 176 .
- ^ de Fraysseix, Hubert; Ossona de Méndez, Patrice ; Rosenstiehl, Pierre (1994), "Sobre gráficos de contacto triangulares", Combinatoria, probabilidad y computación , 3 (2): 233–246, doi : 10.1017 / S0963548300001139 , MR 1288442
- ^ Buchsbaum, Adam L .; Gansner, Emden R .; Procopiuc, Cecilia M .; Venkatasubramanian, Suresh (2008), "Diseños rectangulares y gráficos de contacto", Transacciones ACM sobre algoritmos , 4 (1): Art. 8, 28, arXiv : cs / 0611107 , doi : 10.1145 / 1,328,911.1328919 , MR 2398588
- ^ Klawitter, Jonathan; Nöllenburg, Martin; Ueckerdt, Torsten (2015), "Propiedades combinatorias de arreglos de rectángulos sin triángulos y el problema de cuadratura", Dibujo de gráficos y visualización de redes: 23 ° Simposio Internacional, GD 2015, Los Ángeles, CA, EE. UU., 24-26 de septiembre de 2015, revisado Artículos seleccionados , Lecture Notes in Computer Science, 9411 , Springer, págs. 231–244, arXiv : 1509.00835 , doi : 10.1007 / 978-3-319-27261-0_20
- ^ Hliněný, Petr (2001), "Las gráficas de contacto de los segmentos de línea son NP-completas" (PDF) , Matemáticas discretas , 235 (1–3): 95–106, doi : 10.1016 / S0012-365X (00) 00263-6 , Señor 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", Algoritmos y estructuras de datos: 14th International Symposium, WADS 2015, Victoria, BC, Canadá, 5-7 de agosto de 2015, Actas , Lecture Notes in Computer Science, 9214 , Springer, págs. 1-13, arXiv : 1501.00318 , doi : 10.1007 / 978-3-319-21840-3_1.