Gráfico de arco circular

En teoría de grafos, un gráfico de arcos de un círculo es un gráfico de intersecciones de un conjunto de arcos de un círculo . El gráfico tiene un vértice para cada arco circular y una arista entre dos vértices si los arcos correspondientes se cruzan.

Formalmente, deja

{\displaystyle I_{1},I_{2},\ldots,I_{n}\subconjunto C_{1))

- muchos arcos. Entonces el gráfico de arco circular correspondiente es G = ( V , E ), donde

V=\{I_{1},I_{2},\ldots,I_{n}}\}

\{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnada .

La familia de arcos correspondiente al grafo G se denomina modelo de arco .

Reconocimiento

Tooker [1] encontró el primer algoritmo de reconocimiento de polinomios para gráficos de arco circular que se ejecuta en el tiempo . Posteriormente, McConnell [2] encontró el primer algoritmo de reconocimiento lineal en el tiempo . ${\mathcal {O}}(n^{3})$ $({\mathcal {O}}(n+m))$

Relación con otras clases de grafos

Los gráficos de arco circular son una generalización natural de los gráficos de intervalo . Si el gráfico de arco circular G tiene un modelo de arco que no cubre algunos puntos del círculo, el círculo se puede romper en ese punto y enderezar en un segmento de línea, dando una representación de intervalo. Sin embargo, a diferencia de los gráficos de intervalo, los gráficos de arco circular no siempre son perfectos , ya que los ciclos impares sin cuerdas C 5 , C 7 , etc. son gráficos de arco circular.

Algunas subclases

Sea un gráfico arbitrario a continuación. ${\ estilo de visualización G = (V, E)}$

Gráficas de arcos unitarios de un círculo

$GRAMO$ es un gráfico de arco de círculo unitario si existe un modelo de arco en el que todos los arcos tienen la misma longitud.

Gráficos de arco regulares

$GRAMO$ es un gráfico de arco de círculo regular (o un gráfico de intervalo de ciclo [3] ) si existe un modelo de arco correspondiente en el que ningún arco contiene completamente a otro. El reconocimiento de dichos gráficos y la construcción de un modelo de arco correcto se puede realizar en tiempo lineal . [cuatro] $({\mathcal {O}}(n+m))$

Gráficos de arco circular de Helly

$GRAMO$ es un gráfico de arco de Helly circular si existe un modelo de arco correspondiente tal que los arcos formen una familia de Helly . Gavril [5] da una descripción de esta clase, de la que se sigue el algoritmo de reconocimiento en el tiempo . ${{\mathcal {O}}(n^{3})}$

Joris et al [6] dan otras características (incluida la enumeración de subgrafos generados prohibidos) de esta clase, de la que se sigue un algoritmo de reconocimiento que se ejecuta en tiempo O(n+m) . Si el gráfico de entrada no es un gráfico de arco circular de Helly, el algoritmo devuelve una confirmación de este hecho en forma de un subgráfico generado prohibido. También dieron un algoritmo para determinar si un modelo de arco circular dado forma una familia Helly en tiempo O(n) .

Aplicaciones

Los gráficos de arco circular son útiles para modelar problemas periódicos de asignación de recursos en la investigación de operaciones . Cada intervalo representa una solicitud por un período determinado, repitiéndose en el tiempo.

Enlaces

Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Reconocimiento de tiempo lineal de modelos y gráficos de arco circular de Helly // Algorithmica. - 2009. - T. 59 , núm. 2 . — S. 215–239 . -doi : 10.1007/ s00453-009-9304-5 . .
Alan Tucker. Una prueba eficiente para gráficos de arco circular // SIAM Journal on Computing. - 1980. - T. 9 , núm. 1 . — P. 1–24 . -doi : 10.1137/ 0209001 . .
Ross McConnell. Reconocimiento en tiempo lineal de grafos de arco circular // Algorithmica. - 2003. - T. 37 , núm. 2 . — págs. 93–147 . -doi : 10.1007/ s00453-003-1032-7 .
Martín Charles Golumbic. Teoría de grafos algorítmicos y grafos perfectos. - Prensa académica, 1980. - ISBN 0-444-51530-5 . Segunda edición, Annals of Discrete Mathematics 57, Elsevier, 2004.
Xiaotie Deng, Pavol Hell, Jing Huang. Algoritmos de representación de tiempo lineal para gráficos de arco circular adecuados y gráficos de intervalo adecuados // SIAM Journal on Computing. - 1996. - T. 25 , núm. 2 . — S. 390–403 . -doi : 10.1137/ S0097539792269095 . .
Fánica Gavril. Algoritmos sobre grafos de arco circular // Redes. - 1974. - T. 4 , núm. 4 . — S. 357–369 . -doi : 10.1002/ net.3230040407 .
gráfico de arco circular . Sistema de Información sobre Inclusiones de Clases Gráficas . Fecha de acceso: 14 de diciembre de 2013. Archivado desde el original el 21 de diciembre de 2013. (indefinido)
María Chudnovsky, Paul Seymour. Gráficos sin garras. tercero Gráficos de intervalos circulares // Revista de teoría combinatoria . - 2008. - T. 98 , núm. 4 . — S. 812–834 . -doi : 10.1016/ j.jctb.2008.03.001 . .