Grafos Planos

Teoría

Un grafo plano es un grafo que puedes incrustar en el plano, o sea, que lo puedes dibujar en una superficie plana de tal forma que sus vértices sean puntos y sus aristas sean curvas continuas que los conectan, con la condición estricta de que no haya dos aristas que se crucen, excepto en sus extremos. Si dibujas un grafo de esta manera, lo llamamos un grafo planar. Una propiedad fundamental de un grafo plano es que divide al plano en regiones distintas llamadas caras, incluyendo exactamente una región no acotada (infinita).

Los grafos planos son una pieza clave de la geometría combinatoria y la teoría de grafos, y aparecen seguido en problemas de Olimpiada sobre mapas, poliedros y diseño de circuitos. El concepto es vital porque la planaridad impone restricciones estrictas a la "densidad" de un grafo; un grafo plano no puede tener demasiadas aristas en relación con su número de vértices. Esta limitación la usamos mucho para demostrar que ciertas configuraciones son imposibles o para acotar parámetros específicos del grafo.

La herramienta más poderosa para estudiar grafos planos es la Fórmula de Euler, que establece una relación invariante entre el número de vértices, aristas y caras. Esta fórmula conecta la estructura topológica del grafo con aritmética simple, lo que permite sacar condiciones necesarias para la planaridad. Por ejemplo, si combinas la Fórmula de Euler con argumentos de conteo de aristas, puedes demostrar que el grafo completo $