Grafo cuadrado
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Squaregraph.svg/220px-Squaregraph.svg.png)
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, 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
|formato=
requiere|url=
(ayuda)), Chişinǎu, Moldova: Ştiinţa .
Datos: Q7582090