Grafo plano exterior

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 cordales y de visibilidad.Chartrand y Harary también demostraron un análogo al Teorema de Kuratowski para grafos planos exteriores, que afirma que un grafo es plano exterior si y solo si no contiene una subdivisión de uno de los dos grafos K4 o K2,3.Un grafo plano exterior es un grafo que puede ser representado en el plano sin cruces de tal manera que todos los vértices pertenecen a la cara no acotada del dibujo.Es decir, ningún vértice está totalmente rodeado de aristas.Todo grafo plano exterior máximo con n vértices tiene exactamente 2n − 3 aristas, y cada cara delimitada de un grafo plano exterior máximo es un triángulo.[2]​ Alternativamente, un grafo es plano exterior si y solo si no contiene K4 o K2,3 como menor (un grafo obtenido a partir de eliminar y contraer bordes).[3]​ Un grafo sin triángulos es plano exterior si y solo si no contiene una subdivisión de K2,3.Por esta razón, encontrar ciclos hamiltonianos y ciclos más largos en grafos planos exteriores puede resolverse en tiempo lineal, en contraste con el carácter NP-completo de estos problemas para grafos arbitrarios.Se puede encontrar un ciclo de esta longitud quitando repetidamente un triángulo que esté conectado al resto del grafo por una sola arista, de modo que el vértice eliminado no sea v, hasta que la cara exterior del grafo restante tenga una longitud k.[6]​ Un grafo plano es plano exterior si y solo si cada uno de sus componentes biconectados es plano exterior.Por otro lado, el grafo completo K4 es plano pero no es serie-paralelo ni exterior.