En teoría de grafos , un gráfico de cuerdas es un gráfico de intersección de curvas en el plano; cada curva se llama "cadena". Dado un gráfico G , G es un gráfico de cadena si y solo si existe un conjunto de curvas, o cadenas, dibujadas en el plano de manera que no hay tres cadenas que se crucen en un solo punto y que la gráfica tenga un vértice para cada curva y un borde para cada par de intersección de las curvas es isomorfo a G .
Fondo
Seymour Benzer ( 1959 ) describió un concepto similar a los gráficos de cadena en su aplicación a las estructuras genéticas. En ese contexto, también planteó el caso específico de intersección de intervalos en una línea, a saber, la familia ahora clásica de gráficos de intervalo . Posteriormente, Sinden (1966) concretó la misma idea para las redes eléctricas y los circuitos impresos. El estudio matemático de los gráficos de cuerdas comenzó con el artículo Ehrlich, Even & Tarjan (1976) y a través de una colaboración entre Sinden y Ronald Graham , donde la caracterización de los gráficos de cuerdas finalmente llegó a plantearse como una cuestión abierta en el V Coloquio Húngaro sobre Combinatoria. en 1976. [1] Sin embargo, finalmente se demostró que el reconocimiento de los gráficos de cadenas era NP-completo , lo que implica que no es probable que exista una caracterización simple. [2]
Clases de grafos relacionados
Cada gráfico plano es un gráfico de cadena: [3] se puede formar una representación de gráfico de cadena de un gráfico incrustado en un plano arbitrario dibujando una cadena para cada vértice que gira alrededor del vértice y alrededor del punto medio de cada borde adyacente, como se muestra en la figura. Para cualquier borde uv de la gráfica, las cuerdas para u y v se cruzan entre sí dos veces cerca del punto medio de UV , y no hay otros pasos, por lo que los pares de cuerdas que se cruzan representan exactamente los pares adyacentes de vértices del grafo planar original de . Alternativamente, por el teorema del empaquetamiento de círculos , cualquier grafo plano puede representarse como una colección de círculos, dos cualesquiera de los cuales se cruzan si y solo si los vértices correspondientes son adyacentes; estos círculos (con un punto inicial y final elegido para convertirlos en curvas abiertas) proporcionan una representación gráfica de cadena del gráfico plano dado. Chalopin, Gonçalves & Ochem (2007) demostraron que cada grafo plano tiene una representación de cadena en la que cada par de cadenas tiene como máximo un punto de cruce, a diferencia de las representaciones descritas anteriormente. La conjetura de Scheinerman , ahora probada, es la afirmación aún más fuerte de que cada gráfico plano puede representarse mediante el gráfico de intersección de segmentos de línea recta, un caso muy especial de cadenas.
Si cada borde de un gráfico G determinado se subdivide , el gráfico resultante es un gráfico de cadena si y solo si G es plano. En particular, la subdivisión del gráfico completo K 5 que se muestra en la ilustración no es un gráfico de cadena, porque K 5 no es plano. [3]
Cada gráfico circular , como un gráfico de intersección de segmentos de línea (las cuerdas de un círculo), también es un gráfico de cuerdas. Cada grafo cordal se puede representar como un grafo de cuerdas: los grafos cordales son grafos de intersección de subárboles de árboles, y se puede formar una representación de cuerda de un grafo cordal formando una incrustación plana del árbol correspondiente y reemplazando cada subárbol por una cuerda que traza alrededor de los bordes del subárbol.
El gráfico de complemento de cada gráfico de comparabilidad también es un gráfico de cadena. [4]
Otros resultados
Ehrlich, Even y Tarjan (1976) demostraron que calcular el número cromático de gráficos de cuerdas es NP-duro. Kratochvil (1991a) encontró que los gráficos de cadena forman una clase cerrada menor inducida, pero no una clase cerrada menor de gráficos.
Cada gráfico de cadena de borde m se puede dividir en dos subconjuntos, cada uno una fracción constante del tamaño de todo el gráfico, mediante la eliminación de vértices O ( m 3/4 log 1/2 m ). De ello se deduce que los gráficos de cuerdas libres de biclices , los gráficos de cuerdas que no contienen ningún subgrafo de K t , t para alguna t constante , tienen aristas O ( n ) y, más fuertemente, tienen expansión polinomial . [5]
Notas
- ^ Graham (1976) .
- ↑ Kratochvil (1991b) mostró que el reconocimiento de gráficos de cadenas era NP-hard, pero no pudo demostrar que pudiera resolverse en NP. Tras los resultados intermedios de Schaefer & Štefankovič (2001) y Pach & Tóth (2002) , Schaefer, Sedgwick & Štefankovič (2003) completaron la prueba de que el problema es NP-completo.
- ↑ a b Schaefer y Štefankovič (2001) atribuyen esta observación a Sinden (1966) .
- ^ Golumbic, Rotem & Urrutia (1983) y Lovász (1983) . Véase también Fox y Pach (2010) .
- ^ Fox y Pach (2010) ; Dvořák y Norin (2015) .
Referencias
- Benzer, S. (1959), "Sobre la topología de la estructura genética fina", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 45 (11): 1607–1620, Código Bibliográfico : 1959PNAS ... 45.1607B , doi : 10.1073 / pnas.45.11.1607 , PMC 222769 , PMID 16590553.
- Chalopin, J .; Gonçalves, D .; Ochem, P. (2007), "Las gráficas planas 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 (2015), Separadores fuertemente sublineales y expansión polinomial , arXiv : 1504.04821 , Bibcode : 2015arXiv150404821D.
- Ehrlich, G .; Incluso, 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 del separador para gráficos de cuerdas y sus aplicaciones", Combinatoria, Probabilidad y Computación , 19 (3): 371, doi : 10.1017 / s0963548309990459.
- Golumbic, M .; Rotem, D .; Urrutia, J. (1983), "Gráficos de comparabilidad y gráficos de intersección", Matemáticas discretas , 43 (1): 37–46, doi : 10.1016 / 0012-365X (83) 90019-5.
- Graham, RL (1976), "Problema 1", problemas abiertos en el quinto coloquio húngaro sobre combinatoria.
- Kratochvil, Jan (1991a), "Gráficos de cadena. I. El número de gráficos críticos que no son de cadena es infinito", Journal of Combinatorial Theory, Serie B , 52 (1): 53–66, doi : 10.1016 / 0095-8956 (91) 90090-7.
- Kratochvil, Jan (1991b), "String Graphs. II. Reconocer los gráficos de cadena es NP-Hard", 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 seleccionados en teoría de gráficos , 2 , Londres: Academic Press, págs. 55–87.
- Pach, János ; Tóth, Geza (2002), "El reconocimiento de los gráficos de cadena es decidible", Geometría discreta y computacional , 28 (4): 593–606, doi : 10.1007 / s00454-002-2891-4.
- Schaefer, Marcus; Štefankovič, Daniel (2001), "Decidability of string graphs", Actas del 33º Simposio Anual de ACM sobre Teoría de la Computación (STOC 2001) : 241–246.
- Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (2003), "Recognizing string graphs in 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.