Gráfico circular - Circle graph
En teoría de grafos , un gráfico circular es el gráfico de intersección de un conjunto de cuerdas de un círculo . Es decir, es un grafo no dirigido cuyos vértices se pueden asociar a las cuerdas de un círculo de manera que dos vértices son adyacentes si y solo si las cuerdas correspondientes se cruzan entre sí.
Complejidad algorítmica
Spinrad (1994) proporciona un algoritmo de tiempo O ( n 2 ) que prueba si un gráfico no dirigido de n- vértices dado es un gráfico circular y, si lo es, construye un conjunto de cuerdas que lo representa.
Varios otros problemas que son NP-completos en gráficos generales tienen algoritmos de tiempo polinomial cuando se restringen a gráficos circulares. Por ejemplo, Kloks (1996) mostró que se puede determinar el ancho de árbol de un gráfico circular y construir una descomposición óptima del árbol en un tiempo O ( n 3 ). Además, un relleno mínimo (es decir, un gráfico cordal con el menor número posible de aristas que contiene el gráfico circular dado como un subgráfico) se puede encontrar en el tiempo O ( n 3 ). Tiskin (2010) ha demostrado que se puede encontrar una camarilla máxima de un gráfico circular en el tiempo O ( n log 2 n ), mientras que Nash y Gregg (2010) han demostrado que un conjunto máximo independiente de un gráfico circular no ponderado se puede encontrar en O ( n min { d , α }) tiempo, donde d es un parámetro del gráfico conocido como su densidad y α es el número de independencia del gráfico circular.
Sin embargo, también hay problemas que permanecen NP-completos cuando se restringen a gráficos circulares. Estos incluyen el conjunto dominante mínimo, el conjunto dominante mínimo conectado y los problemas de conjunto dominante mínimo total.
Número cromático
El número cromático de un gráfico circular es el número mínimo de colores que se pueden usar para colorear sus acordes de modo que no haya dos acordes cruzados del mismo color. Dado que es posible formar gráficos circulares en los que conjuntos de cuerdas arbitrariamente grandes se cruzan entre sí, el número cromático de un gráfico circular puede ser arbitrariamente grande, y determinar el número cromático de un gráfico circular es NP-completo. Queda NP-completo para probar si un gráfico circular se puede colorear con cuatro colores. Unger (1992) afirmó que la búsqueda de una coloración con tres colores se puede hacer en tiempo polinomial, pero su redacción de este resultado omite muchos detalles.
Varios autores han investigado los problemas de colorear subclases restringidas de gráficos circulares con pocos colores. En particular, para gráficos circulares en los que ningún conjunto de k o más acordes se cruzan entre sí, es posible colorear el gráfico con tan solo colores. Una forma de decir esto es que las gráficas circulares están limitadas . En el caso particular cuando k = 3 (es decir, para gráficos circulares sin triángulos ) el número cromático es como máximo cinco, y esto es ajustado: todos los gráficos circulares sin triángulos pueden colorearse con cinco colores, y existen triángulos- gráficos circulares libres que requieren cinco colores. Si un gráfico circular tiene una circunferencia de al menos cinco (es decir, no tiene triángulos y no tiene ciclos de cuatro vértices), se puede colorear con un máximo de tres colores. El problema de colorear gráficos cuadrados sin triángulos es equivalente al problema de representar gráficos cuadrados como subgrafos isométricos de productos cartesianos de árboles ; en esta correspondencia, el número de colores en la coloración corresponde al número de árboles en la representación del producto.
Aplicaciones
Surgen gráficas circulares en VLSI diseño físico como una representación abstracta de un caso especial para el enrutamiento de alambre , conocida como "de dos terminales de conmutación de encaminamiento ". En este caso, el área de enrutamiento es un rectángulo, todas las redes son de dos terminales y los terminales se colocan en el perímetro del rectángulo. Se ve fácilmente que el gráfico de intersección de estas redes es un gráfico circular. Entre los objetivos de la etapa de encaminamiento de alambre es asegurar que las diferentes redes permanecen desconectados eléctricamente, y sus partes de intersección potenciales deben ser dispuestas en diferentes capas conductoras. Por lo tanto, los gráficos circulares capturan varios aspectos de este problema de enrutamiento.
Los colorantes de gráficos circulares también se pueden usar para encontrar incrustaciones de libros de gráficos arbitrarios: si los vértices de un gráfico dado G están dispuestos en un círculo, con los bordes de G formando cuerdas del círculo, entonces la gráfica de intersección de estas cuerdas es un El gráfico circular y los colores de este gráfico circular son equivalentes a las incrustaciones de libros que respetan el diseño circular dado. En esta equivalencia, el número de colores en la coloración corresponde al número de páginas del libro incrustado.
Clases de grafos relacionados
Un gráfico es un gráfico circular si y solo si es el gráfico superpuesto de un conjunto de intervalos en una línea. Este es un gráfico en el que los vértices corresponden a los intervalos, y dos vértices están conectados por un borde si los dos intervalos se superponen, sin que ninguno contenga al otro.
El gráfico de intersección de un conjunto de intervalos en una línea se llama gráfico de intervalo .
Los gráficos de cadena , los gráficos de intersección de curvas en el plano, incluyen los gráficos circulares como un caso especial.
Cada gráfico hereditario de distancia es un gráfico circular, al igual que todo gráfico de permutación y todo gráfico de indiferencia . Cada gráfico del plano exterior es también un gráfico circular.
Cada gráfico circular es un gráfico poligonal-circular .
Notas
Referencias
- Ageev, AA (1996), "Un gráfico circular sin triángulos con número cromático 5", Matemáticas discretas , 152 (1-3): 295-298, doi : 10.1016 / 0012-365X (95) 00349-2.
- Ageev, AA (1999), "Cada gráfico circular de circunferencia de al menos 5 es tricolor", Matemáticas discretas , 195 (1-3): 229-233, doi : 10.1016 / S0012-365X (98) 00192-7.
- Bandelt, H.-J .; Chepoi, V .; Eppstein, D. (2010), "Combinatoria y geometría de gráficos cuadrados finitos e infinitos", SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137 / 090760301.
- Černý, Jakub (2007), "Colorear gráficos circulares", Electronic Notes in Discrete Mathematics , 29 : 357–361, doi : 10.1016 / j.endm.2007.07.072.
- Garey, MR ; Johnson, DS ; Miller, GL ; Papadimitriou, C. (1980), "La complejidad de colorear arcos circulares y acordes", SIAM Journal on Algebraic and Discrete Methods , 1 (2): 216-227, doi : 10.1137 / 0601025.
- Gyárfás, A. (1985), "Sobre el número cromático de gráficos de intervalo múltiple y gráficos superpuestos", Matemáticas discretas , 55 (2): 161-166, doi : 10.1016 / 0012-365X (85) 90044-5. Como lo cita Ageev (1996) .
- Gyárfás, A .; Lehel, J. (1985), "Problemas de cobertura y coloración para parientes de intervalos", Matemáticas discretas , 55 (2): 167–180, doi : 10.1016 / 0012-365X (85) 90045-7. Como lo cita Ageev (1996) .
- Karapetyan, A. (1984), On perfect arc and chord intersection graphs , Ph.D. tesis (en ruso), Inst. de Matemáticas, Novosibirsk. Como lo cita Ageev (1996) .
- Keil, J. Mark (1993), "La complejidad de los problemas de dominación en gráficos circulares", Matemáticas aplicadas discretas , 42 (1): 51–63, doi : 10.1016 / 0166-218X (93) 90178-Q.
- Kloks, Ton (1996), "Treewidth of Circle Graphs", Int. J. Encontrado. Computación. Sci. , 7 (2): 111–120, doi : 10.1142 / S0129054196000099.
- Kloks, T .; Kratsch, D .; Wong, CK (1998), "Relleno mínimo en gráficos circulares y de arco circular", Journal of Algorithms , 28 (2): 272-289, doi : 10.1006 / jagm.1998.0936.
- Kostochka, AV (1988), "Límites superiores del número cromático de gráficos", Trudy Instituta Mathematiki (en ruso), 10 : 204–226, MR 0945704. Como lo cita Ageev (1996) .
- Kostochka, AV; Kratochvíl, J. (1997), "Cubrir y colorear gráficos poligonales-circulares", Matemáticas discretas , 163 (1-3): 299-305, doi : 10.1016 / S0012-365X (96) 00344-5.
- Nash, Nicholas; Gregg, David (2010), "Un algoritmo sensible a la salida para calcular un conjunto máximo independiente de un gráfico circular", Information Processing Letters , 116 (16): 630–634, doi : 10.1016 / j.ipl.2010.05.016 , hdl : 10344/2228.
- Spinrad, Jeremy (1994), "Reconocimiento de gráficos circulares", Journal of Algorithms , 16 (2): 264-282, doi : 10.1006 / jagm.1994.1012.
- Tiskin, Alexander (2010), "Multiplicación a distancia rápida de matrices unitarias de Monge", Actas de ACM-SIAM SODA 2010 , págs. 1287–1296.
- Unger, Walter (1988), "On the k -colouring of circle-graphs", STACS 88: 5to Simposio anual sobre aspectos teóricos de la informática, Burdeos, Francia, 11 al 13 de febrero de 1988, Actas , Notas de conferencias en informática , 294 , Berlín: Springer, págs. 61–72, doi : 10.1007 / BFb0035832.
- Unger, Walter (1992), "La complejidad de colorear gráficos circulares", STACS 92: Noveno Simposio anual sobre aspectos teóricos de la informática, Cachan, Francia, 13-15 de febrero de 1992, Actas , Lecture Notes in Computer Science, 577 , Berlín: Springer, págs. 389–400, doi : 10.1007 / 3-540-55210-3_199.
- Wessel, W .; Pöschel, R. (1985), "On circle graphs", en Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory celebrada en Eyba, 1 al 5 de octubre de 1984 , Teubner-Texte zur Mathematik, 73 , BG Teubner, págs. 207–210. Como lo cita Unger (1988) .
