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.

• 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 .