Además de ser grafos planares , los grafos cuadrados son grafos medianos , lo que significa que por cada tres vértices u , v y w hay un vértice mediano único 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 con los grafos medianos en general, los grafos cuadrados también son cubos parciales : sus vértices se pueden etiquetar con cadenas binarias de modo que la distancia de Hamming entre cadenas sea igual a la distancia del camino más corto entre vértices.
El grafo obtenido a partir de un cuadrángulo haciendo 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 cuerda libre de triángulos del disco unitario. [2]
Caracterización
Los cuadrágrafos se pueden caracterizar de varias maneras además de a través de sus incrustaciones planas: [2]
Son los grafos medianos que no contienen como subgrafo inducido a ningún miembro de una familia infinita de grafos prohibidos . Estos grafos prohibidos son el cubo (el grafo simplex de K 3 ), el producto cartesiano de una arista por 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 buje de la rueda (el grafo simplex de la unión disjunta de un ciclo con un vértice aislado).
Son los grafos que son conexos 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 vínculo de v (un grafo con un vértice para cada arista incidente a v y una arista para cada 4-ciclo que contiene a v ) es un ciclo de longitud mayor que tres o una unión disjunta de caminos.
La caracterización de los grafos cuadrados en términos de distancia desde una raíz y vínculos de vértices se puede utilizar junto con la búsqueda en amplitud como parte de un algoritmo de tiempo lineal para probar si un gráfico dado es un grafo cuadrado, sin necesidad de utilizar algoritmos de tiempo lineal más complejos para pruebas de planaridad de gráficos arbitrarios. [2]
Varios problemas algorítmicos en grafos cuadrados se pueden calcular de manera más eficiente que en grafos planos 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 grafos cuadrados y para encontrar un vértice que minimice la distancia máxima a todos los demás vértices.
Notas
^ Soltan, Zambitskii y Prisǎcaru (1973). Véase Peterin (2006) para una discusión más general sobre los gráficos planos de mediana.
^ abc Bandelt, Chepoi y Eppstein (2010).
Referencias
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 de centro y diámetro en cuadrangulaciones y triangulaciones planas", Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (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", Computational Geometry , 27 (3): 193–210, doi : 10.1016/j.comgeo.2003.11.002.
Peterin, Iztok (2006), "Una caracterización de 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.
