Gráfica de arco circular

En teoría de grafos , un grafo de arco circular es el grafo de intersección de un conjunto de arcos en el círculo. Tiene un vértice por cada arco del conjunto y una arista entre cada par de vértices correspondiente a los arcos que se intersecan.

Formalmente, dejar

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

sea ​​un conjunto de arcos. Entonces el grafo de arco circular correspondiente es G = ( V ,  E ) donde

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

y

${\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .}$

Una familia de arcos que corresponde a G se llama modelo de arco .

Tucker (1980) demostró el primer algoritmo de reconocimiento polinomial para grafos de arco circular, que se ejecuta en el tiempo. McConnell (2003) presentó el primer algoritmo de reconocimiento lineal en el tiempo, donde es el número de aristas. Más recientemente, Kaplan y Nussbaum ^[1] desarrollaron un algoritmo de reconocimiento lineal en el tiempo más simple. ${\displaystyle {\mathcal {O}}(n^{3})}$${\displaystyle ({\mathcal {O}}(n+m))}$${\estilo de visualización m}$

Los grafos de arco circular son una generalización natural de los grafos de intervalo . Si un grafo de arco circular G tiene un modelo de arco que deja algún punto del círculo descubierto, el círculo se puede cortar en ese punto y estirar hasta una línea, lo que da como resultado una representación de intervalo. Sin embargo, a diferencia de los grafos de intervalo, los grafos de arco circular no siempre son perfectos , ya que los ciclos impares sin cuerdas C ₅ , C ₇ , etc., son grafos de arco circular.

En lo que sigue, sea un gráfico arbitrario. ${\displaystyle G=(V,E)}$

${\estilo de visualización G}$es un gráfico de arco circular unitario si existe un modelo de arco correspondiente tal que cada arco tiene la misma longitud.

El número de grafos de arco circular unitarios etiquetados en n vértices está dado por . ^[2]${\displaystyle (n+2){\binom {2n-1}{n-1}}-2^{2n-1}}$

${\estilo de visualización G}$es un grafo de arco circular propio (también conocido como grafo de intervalo circular ) ^[3] si existe un modelo de arco correspondiente tal que ningún arco contenga apropiadamente a otro. El reconocimiento de estos grafos y la construcción de un modelo de arco propio pueden realizarse en tiempo lineal. ^[4] Forman una de las subclases fundamentales de los grafos sin garras . ^[3]${\displaystyle ({\mathcal {O}}(n+m))}$

${\estilo de visualización G}$es un grafo de arco circular de Helly si existe un modelo de arco correspondiente tal que los arcos constituyen una familia de Helly . Gavril (1974) da una caracterización de esta clase que implica un algoritmo de reconocimiento. ${\displaystyle {{\mathcal {O}}(n^{3})}}$

Joeris et al. (2009) ofrecen otras caracterizaciones de esta clase, que implican un algoritmo de reconocimiento que se ejecuta en tiempo O(n+m) cuando la entrada es un grafo. Si el grafo de entrada no es un grafo de arco circular de Helly, entonces el algoritmo devuelve un certificado de este hecho en forma de un subgrafo inducido prohibido. También proporcionaron un algoritmo de tiempo O(n) para determinar si un modelo de arco circular dado tiene la propiedad de Helly.

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 de un recurso para un período específico que se repite en el tiempo.

• Chudnovsky, Maria ; Seymour, Paul (2008), "Gráficos sin garras. III. Gráficos de intervalos circulares" (PDF) , Journal of Combinatorial Theory , Serie B, 98 (4): 812–834, doi : 10.1016/j.jctb.2008.03.001 , MR  2418774.
• Deng, Xiaotie; Hell, Pavol ; Huang, Jing (1996), "Algoritmos de representación en tiempo lineal para gráficos de arco circular y gráficos de intervalo adecuados", SIAM Journal on Computing , 25 (2): 390–403, doi :10.1137/S0097539792269095.
• Gavril, Fanica (1974), "Algoritmos en grafos de arco circular", Networks , 4 (4): 357–369, doi :10.1002/net.3230040407.
• Golumbic, Martin Charles (1980), Teoría de grafos algorítmicos y grafos perfectos, Academic Press, ISBN 978-0-444-51530-8, archivado desde el original el 22 de mayo de 2010 , consultado el 21 de mayo de 2008. Segunda edición, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), "Reconocimiento en tiempo lineal de modelos y gráficos de arcos circulares de Helly", Algorithmica , 59 (2): 215–239, CiteSeerX  10.1.1.298.3038 , doi :10.1007/s00453-009-9304-5.
• McConnell, Ross (2003), "Reconocimiento de gráficos de arco circular en tiempo lineal", Algorithmica , 37 (2): 93–147, CiteSeerX  10.1.1.22.4725 , doi :10.1007/s00453-003-1032-7.
• Tucker, Alan (1980), "Una prueba eficiente para gráficos de arco circular", SIAM Journal on Computing , 9 (1): 1–24, doi :10.1137/0209001.

• Gráfico de arco circular, Sistema de información sobre inclusiones de clases de gráficos