- Grafo cuadrado
-
Un 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), «A characterization of planar median graphs», Discussiones Mathematicae Graph Theory 26: 41–48, http://www.mp.feri.uni-mb.si/osebne/peterin/clanki/planarmedian6.pdf
- Soltan, P.; Zambitskii, D.; Prisǎcaru, C. (1973) (En ruso), Extremal Problems on Graphs and Algorithms of their Solution, Chişinǎu, Moldova: Ştiinţa
Categoría:- Familias de grafos
Wikimedia foundation. 2010.
