Ir al contenido

Grafo cuadrado

De Wikipedia, la enciclopedia libre
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

[editar]
  1. Soltan, Zambitskii y Prisǎcaru (1973). Véase Peterin (2006) para una discusión más general de grafos medianos planares.

Referencias

[editar]
  • 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), Chişinǎu, Moldova: Ştiinţa .