Grafo poliédrico

El diagrama de Schlegel de un poliedro convexo representa sus vértices y aristas como puntos y segmentos de línea recta en un espacio bidimensional, formando una subdivisión de un polígono convexo exterior en polígonos convexos más pequeños (un dibujo convexo del grafo del poliedro).

Es decir, siempre que un grafo sea tanto plano como conectado por 3 vértices, existe un poliedro cuyos vértices y aristas forman un grafo isomórfico.

[1]​[2]​ Dado tal grafo, se puede encontrar una representación del mismo como una subdivisión de un polígono convexo en polígonos convexos más pequeños usando el embebido de Tutte.

[3]​ Según la conjetura de Tait, todo grafo poliédrico cúbico (es decir, un grafo poliédrico en el que cada vértice incide exactamente en tres aristas) posee un camino hamiltoniano, pero esta conjetura fue refutada por un contraejemplo descubierto por W. T. Tutte, el poliédrico pero no hamiltoniano grafo de Tutte.

Los grafos de Halin, grafos formados a partir de un árbol embebido en un plano al agregar un ciclo externo que conecta todas las hojas del árbol, forman otra subclase importante de los grafos poliédricos.