Caracterización de grafos prohibidos

Así, todo grafo o bien tiene un dibujo plano (en cuyo caso pertenece a la familia de los grafos planos) o tiene una subdivisión de al menos uno de estos dos grafos como subgrafo (en cuyo caso no pertenece a los grafos planos).Las diferentes familias varían en la naturaleza de lo que está prohibido.si y solo si una subestructura prohibida no está contenida en G. Las subestructuras prohibidas podrían ser: El conjunto de estructuras que tienen prohibido pertenecer a una familia de grafos dada también puede denominarse conjunto de obstrucciones para esa familia.En muchos casos, es posible probar en tiempo polinómico si un grafo dado contiene alguno de los miembros del conjunto de obstrucciones y, por lo tanto, si pertenece a la familia definida por este conjunto.Cuando esto es cierto, siempre existe un conjunto de obstrucción (el conjunto de grafos que no están en la familia pero cuyas subestructuras más pequeñas pertenecen todas a la familia).