Grafo cuadrado
En teoría de grafos, un grafo cuadrado es un grafo no dirigido que puede dibujarse en el plano de modo que cada superficie acotada es un cuadrilátero y cada vértice con tres o menos vecinos es incidente a una cara no acotada.
Los grafos cuadrados son un tipo de grafos medianos planares,[1] e incluyen como casos especiales a los árboles, grafos reticulados, y los grafos de los poliominós. Muchos problemas algorítmicos pueden ser computados más eficientemente en el contexto de grafos cuadrados que en casos más generales de grafos medianos o planares. Por ejemplo, Chepoi, Dragan y Vaxès (2002) y Chepoi, Fanciullini y Vaxès (2004) presentan algoritmos en tiempo lineal para computar el diámetro de grafos cuadrados, y para encontrar 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 de grafos medianos planares.
Referencias
- Chepoi, V.; Dragan, F.; Vaxès, Y. (2002), «Center and diameter problem in planar quadrangulations and triangulations», Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 346-355.
- Chepoi, V.; Fanciullini, C.; Vaxès, Y. (2004), «Median problem in some plane triangulations and quadrangulations», Comput. Geom. 27: 193-210.
- Peterin, I. (2006), , Discussiones Mathematicae Graph Theory 26: 41-48, archivado desde el original el 5 de octubre de 2011, consultado el 17 de diciembre de 2008.
- Soltan, P.; Zambitskii, D.; Prisǎcaru, C. (1973), Extremal Problems on Graphs and Algorithms of their Solution (En ruso), Chişinǎu, Moldova: Ştiinţa.