Gráfico cuadrado

En la teoría de grafos , una rama de las matemáticas , un grafo cuadrado es un tipo de grafo no dirigido que se puede dibujar en el plano de tal manera que cada cara delimitada sea un cuadrilátero y cada vértice con tres o menos vecinos sea incidente a una cara no delimitada.

Los grafos cuadrados incluyen como casos especiales árboles , grafos de cuadrícula , grafos de engranajes y los grafos de poliominos .

Además de ser grafos planares , los grafos cuadrados son grafos medianos , lo que significa que para cada tres vértices u , v y w hay un único vértice mediano m ( u , v , w ) que se encuentra en los caminos más cortos entre cada par de los tres vértices. ^{[ 1 ]} Al igual que los grafos medianos en general, los grafos cuadrados también son cubos parciales : sus vértices pueden etiquetarse con cadenas binarias de tal manera que la distancia de Hamming entre cadenas es igual a la distancia del camino más corto entre vértices.

El grafo obtenido a partir de un grafo cuadrado, creando un vértice para cada zona (una clase de equivalencia de aristas paralelas de cuadriláteros) y una arista para cada dos zonas que se encuentran en un cuadrilátero, es un grafo circular determinado por un diagrama de cuerdas sin triángulos del disco unitario. ^{[ 2 ]}

Los grafos cuadrados pueden caracterizarse de varias maneras distintas a través de sus incrustaciones planares: ^{[ 2 ]}

• Son los grafos medianos que no contienen como subgrafo inducido ningún miembro de una familia infinita de grafos prohibidos . Estos grafos prohibidos son el cubo (el grafo simplex de K ₃ ), el producto cartesiano de una arista y una garra K _1,3 (el grafo simplex de una garra) y los grafos formados a partir de un grafo de engranaje añadiendo un vértice más conectado al cubo de la rueda (el grafo simplex de la unión disjunta de un ciclo con un vértice aislado).
• Son los grafos que son conectados y bipartitos , tales que (si se elige un vértice arbitrario r como raíz ) cada vértice tiene como máximo dos vecinos más cercanos a r , y tales que en cada vértice v , el enlace de v (un grafo con un vértice para cada arista incidente a v y una arista para cada ciclo de 4 miembros que contiene a v ) es un ciclo de longitud mayor que tres o una unión disjunta de caminos.
• Son las gráficas duales de conjuntos de líneas en el plano hiperbólico que no tienen tres líneas que se crucen entre sí.

La caracterización de los grafos cuadrados en términos de distancia a una raíz y enlaces de vértices puede utilizarse junto con la búsqueda en anchura como parte de un algoritmo de tiempo lineal para comprobar si un grafo dado es un grafo cuadrado, sin necesidad de utilizar los algoritmos de tiempo lineal más complejos para la comprobación de planaridad de grafos arbitrarios. ^{[ 2 ]}

Varios problemas algorítmicos en grafos cuadrados pueden calcularse de manera más eficiente que en grafos planares o medianos más generales; por ejemplo, Chepoi, Dragan y Vaxès (2002) y Chepoi, Fanciullini y Vaxès (2004) presentan algoritmos de tiempo lineal para calcular el diámetro de los grafos cuadrados y para encontrar un vértice que minimice la distancia máxima a todos los demás vértices.

• Bandelt, Hans-Jürgen; Chepoi, Victor; Eppstein, David (2010), "Combinatoria y geometría de grafos cuadrados finitos e infinitos", SIAM Journal on Discrete Mathematics , 24 (4): 1399– 1440, arXiv : 0905.4537 , doi : 10.1137/090760301 , S2CID 10788524 .
• Chepoi, Victor; Dragan, Feodor; Vaxès, Yann ( 2002), "Problema del centro y el diámetro en cuadrangulaciones y triangulaciones planas", Actas del 13.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA 2002) , págs. 346-355 .
• Chepoi, Victor; Fanciullini, Clémentine; Vaxès, Yann (2004), "Problema de la mediana en algunas triangulaciones y cuadrangulaciones planas", Geometría Computacional , 27 (3): 193– 210, doi : 10.1016/j.comgeo.2003.11.002.
• Peterin, Iztok (2006), "Una caracterización de los grafos medianos planares" , Discussiones Mathematicae Graph Theory , 26 (1): 41– 48, doi : 10.7151/dmgt.1299
• Soltán, P.; Zambitskii, D.; Prisǎcaru, C. (1973), Problemas extremos sobre gráficos y algoritmos de su solución (en ruso), Chişinǎu, Moldavia: Ştiinţa.