En la disciplina matemática de la teoría de grafos , un grafo polígono-círculo es un grafo de intersección de un conjunto de polígonos convexos cuyos vértices se encuentran todos en un círculo común. Estos grafos también se han llamado grafos de araña . Esta clase de grafos fue sugerida por primera vez por Michael Fellows en 1988, motivado por el hecho de que es cerrada bajo contracción de aristas y operaciones de subgrafos inducidas . [1]
Un grafo de polígono-círculo se puede representar como una "secuencia alternada". Esta secuencia se puede obtener alterando los polígonos que representan el grafo (si es necesario) de modo que ningún par comparta un vértice y luego enumerando para cada vértice (en orden circular, comenzando en un punto arbitrario) el polígono asociado a ese vértice.
La contracción de un borde de un grafo de polígono-círculo da como resultado otro grafo de polígono-círculo. Se puede formar una representación geométrica del nuevo grafo reemplazando los polígonos correspondientes a los dos puntos finales del borde contraído por su envoltura convexa . Alternativamente, en la secuencia alternada que representa el grafo 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 alternada del grafo contraído. Los grafos de polígono-círculo también se cierran bajo operaciones de eliminación de subgrafos inducidos o, equivalentemente, de vértices: para eliminar un vértice, se elimina su polígono de la representación geométrica o se elimina su subsecuencia de puntos de la secuencia alternada.
M. Koebe anunció un algoritmo de reconocimiento de tiempo polinomial; [2] sin embargo, su versión preliminar tenía "errores graves" [3] y nunca se publicó una versión final. [1] Martin Pergel demostró más tarde que el problema de reconocer estos grafos es NP-completo . [4] También es NP-completo determinar si un grafo dado puede representarse como un grafo de polígono-círculo con como máximo k vértices por polígono, para cualquier k ≥ 3. [ 1]
Los grafos polígono-círculo son una generalización de los grafos circulares , que son grafos de intersección de las cuerdas de un círculo, y los grafos trapezoidales , grafos de intersección de trapecios que tienen todos sus vértices en las mismas dos líneas paralelas. También incluyen los grafos de arco circular . [1] [5]
Los grafos polígono-círculo no son, en general, grafos 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]