En la disciplina matemática de la teoría de grafos , un gráfico de círculo poligonal es un gráfico de intersección de un conjunto de polígonos convexos cuyos vértices se encuentran en un círculo común. Estos gráficos también se han llamado gráficos de araña . Esta clase de gráficos fue sugerida por primera vez por Michael Fellows en 1988, motivado por el hecho de que está cerrado bajo contracción de borde y operaciones de subgrafo inducidas . [1]
Un gráfico de círculo poligonal se puede representar como una "secuencia alterna". Esta secuencia se puede obtener perturbando los polígonos que representan el gráfico (si es necesario) para que no haya dos que compartan un vértice, y luego enumerando para cada vértice (en orden circular, comenzando en un punto arbitrario) el polígono adjunto a ese vértice.
Cierre de menores inducidos
Contraer un borde de un gráfico poligonal-circular da como resultado otro gráfico poligonal-circular. Se puede formar una representación geométrica del nuevo gráfico reemplazando los polígonos correspondientes a los dos puntos finales del borde contraído por su casco convexo . Alternativamente, en la secuencia alterna que representa el gráfico original, la combinación de las subsecuencias que representan los puntos finales del borde contraído en una sola subsecuencia produce una representación de secuencia alterna del gráfico contraído. Los gráficos de círculos poligonales también se cierran bajo subgrafos inducidos o, de manera equivalente, operaciones de eliminación de vértices: para eliminar un vértice, eliminar su polígono de la representación geométrica o eliminar su subsecuencia de puntos de la secuencia alterna.
Reconocimiento
M. Koebe anunció un algoritmo de reconocimiento de tiempo polinomial, [2] sin embargo, su versión preliminar tenía "errores graves" [3] y una versión final nunca fue publicada. [1] Martin Pergel demostró más tarde que el problema de reconocer estos gráficos es NP-completo . [4] También es NP-completo determinar si un gráfico dado se puede representar como un gráfico de círculo polígono con un máximo de k vértices por polígono, para cualquier k ≥ 3 . [1]
Familias de gráficos relacionados
Los gráficos poligonales-circulares son una generalización de los gráficos circulares , que son gráficos de intersección de las cuerdas de un círculo, y los gráficos de trapezoides , gráficos de intersección de trapezoides que tienen todos sus vértices en las mismas dos líneas paralelas. También incluyen los gráficos de arco circular . [1] [5]
Los gráficos poligonales-circulares no son, en general, gráficos perfectos , pero son casi perfectos, en el sentido de que sus números cromáticos pueden estar acotados por una función (exponencial) de sus números de camarilla . [6]
Referencias
- ↑ a b c d Kratochvíl, Jan ; Pergel, Martin (2004), "Two results on intersection graphs of polygons", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, 21-24 de septiembre de 2003, Revised Papers , Lecture Notes in Computer Science, 2912 , Berlín: Springer, págs. 59–70, doi : 10.1007 / 978-3-540-24595-7_6 , MR 2177583.
- ^ Koebe, Manfred (1992), "Sobre una nueva clase de gráficos de intersección", Cuarto Simposio checoslovaco sobre combinatoria, gráficos y complejidad (Prachatice, 1990) , Ann. Discrete Math., 51 , Holanda Septentrional, Ámsterdam, págs. 141–143, doi : 10.1016 / S0167-5060 (08) 70618-6 , MR 1206256.
- ^ Spinrad, Jeremy P. (2003), Representaciones gráficas eficientes , Fields Institute Monographs, 19 , American Mathematical Society, Providence, RI, p. 41, ISBN 0-8218-2815-0, Señor 1971502.
- ^ Pergel, Martin (2007), "El reconocimiento de gráficos de polígonos-círculos y gráficos de filamentos de intervalo es NP-completo", Conceptos de teoría de gráficos en ciencias de la computación: 33º Taller Internacional, GT 2007, Dornburg, Alemania, 21-23 de junio de 2007 , Revised Papers , Lecture Notes in Computer Science, 4769 , Berlín: Springer, págs. 238–247, doi : 10.1007 / 978-3-540-74839-7_23 , MR 2428581.
- ^ Gráficos de araña , sistema de información sobre clases de gráficos y sus inclusiones, consultado el 11 de julio de 2016.
- ^ Kostochka, Alexandr; Kratochvíl, Jan (1997), "Cubrir y colorear gráficos poligonales-circulares", Matemáticas discretas , 163 (1-3): 299-305, doi : 10.1016 / S0012-365X (96) 00344-5 , MR 1428585.