grafo plano exterior

En teoría de grafos, un grafo plano exterior es un grafo que tiene una representación plana para la que todos los vértices pertenecen a la cara exterior del dibujo. Los grafos planos externos se pueden caracterizar (análogamente al teorema de Wagner para grafos planos) por los dos menores prohibidos K4 y K2,3, o por sus . Poseen ciclos hamiltonianos si y solo si están biconectados, en cuyo caso la cara exterior forma el único ciclo hamiltoniano. Cada grafo plano externo tiene 3 colores; y y como máximo 2. Los grafos planos exteriores son un subconjunto de los grafos planos, de los subgrafos de grafos serie-paralelo y de los . Los grafos planos exteriores máximos, aquellos a los que no se les pueden añadir más aristas conservando la planaridad exterior, también son y de visibilidad.