Gráfico de cadenas

En teoría de grafos , un grafo de cuerdas es un grafo de intersección de curvas en el plano ; cada curva se denomina "cuerda". Dado un grafo G , G es un grafo de cuerdas si y solo si existe un conjunto de curvas, o cuerdas, tales que el grafo que tiene un vértice para cada curva y una arista para cada par de curvas que se intersecan es isomorfo a G.

Seymour Benzer  (1959) describió un concepto similar al de los grafos de cuerdas aplicados a las estructuras genéticas. En ese contexto, también planteó el caso específico de los intervalos que se intersecan en una línea, es decir, la ahora clásica familia de grafos de intervalos . Más tarde, Sinden (1966) especificó la misma idea para las redes eléctricas y los circuitos impresos. El estudio matemático de los grafos de cuerdas comenzó con el artículo Ehrlich, Even & Tarjan (1976) y mediante una colaboración entre Sinden y Ronald Graham , donde la caracterización de los grafos de cuerdas finalmente llegó a plantearse como una pregunta abierta en el 5º Coloquio Húngaro sobre Combinatoria en 1976. ^[1] Sin embargo, finalmente se demostró que el reconocimiento de los grafos de cuerdas era NP-completo , lo que implica que es probable que no exista una caracterización simple. ^[2]

Todo grafo plano es un grafo de cuerdas: ^[3] se puede formar una representación de grafo de cuerdas de un grafo arbitrario embebido en un plano dibujando una cuerda para cada vértice que se enrolle alrededor del vértice y alrededor del punto medio de cada arista adyacente, como se muestra en la figura. Para cualquier arista uv del grafo, las cuerdas para u y v se cruzan entre sí dos veces cerca del punto medio de uv , y no hay otros cruces, por lo que los pares de cuerdas que se cruzan representan exactamente los pares adyacentes de vértices del grafo plano original. Alternativamente, por el teorema de empaquetamiento de círculos , cualquier grafo plano puede representarse como una colección de círculos, dos de los cuales se cruzan si y solo si los vértices correspondientes son adyacentes; estos círculos (con un punto inicial y final elegidos para convertirlos en curvas abiertas) proporcionan una representación de grafo de cuerdas del grafo plano dado. Chalopin, Gonçalves y Ochem (2007) demostraron que todo grafo plano tiene una representación de cuerdas en la que cada par de cuerdas tiene como máximo un punto de cruce, a diferencia de las representaciones descritas anteriormente. La conjetura de Scheinerman , ahora demostrada, es la afirmación aún más contundente de que todo grafo plano puede representarse mediante el grafo de intersección de segmentos de línea recta, un caso muy especial de cuerdas.

Si cada arista de un grafo dado G se subdivide , el grafo resultante es un grafo de cuerdas si y solo si G es plano. En particular, la subdivisión del grafo completo K ₅ que se muestra en la ilustración no es un grafo de cuerdas, porque K ₅ no es plano. ^[3]

Todo grafo circular , como grafo de intersección de segmentos de línea (las cuerdas de un círculo), es también un grafo de cuerdas. Todo grafo de cuerdas puede representarse como un grafo de cuerdas: los grafos de cuerdas son grafos de intersección de subárboles de árboles, y se puede formar una representación de cuerdas de un grafo de cuerdas formando una incrustación plana del árbol correspondiente y reemplazando cada subárbol por una cadena que recorra los bordes del subárbol.

El gráfico complementario de cada gráfico de comparabilidad es también un gráfico de cadenas. ^[4]

Ehrlich, Even y Tarjan (1976) demostraron que calcular el número cromático de grafos de cuerdas es NP-hard. Kratochvil (1991a) descubrió que los grafos de cuerdas forman una clase cerrada menor inducida, pero no una clase cerrada menor de grafos.

Cada grafo de cadena de m aristas se puede dividir en dos subconjuntos, cada uno de ellos una fracción constante del tamaño del grafo completo, mediante la eliminación de O ( m ^3/4 log ^1/2 m ) vértices. De ello se deduce que los grafos de cadena libres de biciclos , grafos de cadena que no contienen ningún subgrafo K _{t , t} para alguna constante t , tienen O ( n ) aristas y, más fuertemente, tienen expansión polinómica . ^[5]

• Benzer, S. (1959), "Sobre la topología de la estructura fina genética", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 45 (11): 1607–1620, Bibcode :1959PNAS...45.1607B, doi : 10.1073/pnas.45.11.1607 , PMC  222769 , PMID  16590553.
• Chalopin, J.; Gonçalves, D.; Ochem, P. (2007), "Los gráficos planares están en 1-STRING", Actas del decimoctavo simposio anual ACM-SIAM sobre algoritmos discretos , ACM y SIAM, págs. 609–617.
• Dvořák, Zdeněk ; Norin, Sergey (2016), "Separadores fuertemente sublineales y expansión polinomial", SIAM Journal on Discrete Mathematics , 30 (2): 1095–1101, arXiv : 1504.04821 , Bibcode :2015arXiv150404821D, doi :10.1137/15M1017569.
• Ehrlich, G.; Even, S.; Tarjan, RE (1976), "Gráficos de intersección de curvas en el plano", Journal of Combinatorial Theory , 21 (1): 8–20, doi : 10.1016/0095-8956(76)90022-8.
• Fox, Jacob ; Pach, János (2010), "Un teorema separador para gráficos de cadenas y sus aplicaciones", Combinatorics, Probability and Computing , 19 (3): 371, doi :10.1017/s0963548309990459, S2CID  5705145.
• Golumbic, M.; Rotem, D.; Urrutia, J. (1983), "Gráficos de comparabilidad y gráficos de intersección", Discrete Mathematics , 43 (1): 37–46, doi : 10.1016/0012-365X(83)90019-5.
• Graham, RL (1976), "Problema 1", Problemas abiertos en el 5º Coloquio Húngaro sobre Combinatoria.
• Kratochvil, Jan (1991a), "Gráficos de cuerdas. I. El número de gráficos críticos no de cuerdas es infinito", Journal of Combinatorial Theory, Serie B , 52 (1): 53–66, doi : 10.1016/0095-8956(91)90090-7.
• Kratochvil, Jan (1991b), "Gráficos de cuerdas. II. Reconocer gráficos de cuerdas es NP-difícil", Journal of Combinatorial Theory, Serie B , 52 (1): 67–78, doi : 10.1016/0095-8956(91)90091-W.
• Lovász, L. (1983), "Gráficos perfectos", Temas selectos de teoría de grafos , vol. 2, Londres: Academic Press, págs. 55–87.
• Pach, János ; Tóth, Geza (2002), "El reconocimiento de gráficos de cuerdas es decidible", Geometría discreta y computacional , 28 (4): 593–606, doi : 10.1007/s00454-002-2891-4.
• Schaefer, Marcus; Štefankovič, Daniel (2001), "Decidibilidad de gráficos de cadenas", Actas del 33.º Simposio anual de la ACM sobre teoría de la computación (STOC 2001) : 241–246.
• Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (2003), "Reconocimiento de gráficos de cadenas en NP", Journal of Computer and System Sciences , 67 (2): 365–380, doi : 10.1016/S0022-0000(03)00045-X.
• Sinden, FW (1966), "Topología de circuitos RC de película delgada", Bell System Technical Journal , 45 (9): 1639–1662, doi :10.1002/j.1538-7305.1966.tb01713.x.