Gráfico plano de incrustación de líneas rectas

Question

Quiero demostrar que todo gráfico plano normal tiene una incrustación rectilínea.

En primer lugar, asumo que el gráfico plano $G$ es planar máximo, es decir, el número de aristas es $3n-6$ para $|G|=|V(G)|\ge3$ . Si el grafo no es planar máximo simplemente añado algunas aristas hasta que sea máximo. También sé que todas las caras forman triángulos.

Ahora quiero demostrar el resultado con la inducción con respecto a $n$ .

$n=3:$ Este caso es trivial, es sólo un triángulo.

$n-1\rightarrow n$ . Supongo que sé que la incrustación funciona para un gráfico con $n-1$ vértices. No sé caliente para concluir. Intuitivamente está claro para mí porque no es más que algunos triángulos que cluedo juntos.

Tal vez puedas ayudarme.

Answer 1

Obsérvese que todas las caras del grafo plano máximo (incluida la exterior) son triángulos.

Consideremos un grafo planar máximo $G$ en $n$ vértices. Tiene vértices $v$ tal que $\deg v \le 5$ (de lo contrario tendría al menos $\frac{6n}2 = 3n > 3n - 6$ bordes). Dado que todas las caras de $G$ son triángulos, también hay un ciclo $C$ tal que $V(C) = N(v)$ . Que se elimine $v$ de $G$ , añada $|C| - 3$ acordes en $C$ (si $|C| = 5$ deben ser adyacentes) y obtener el gráfico planar máximo $H$ en $n - 1$ vértices. Por hipótesis de inducción tiene una incrustación rectilínea. Ahora eliminamos todas las aristas de $E(H) \setminus E(G)$ . Si el ciclo $C$ es una cara interior (de tamaño máximo 5) siempre es posible colocar $v$ dentro de esta cara y conectar con sus vecinos en $G$ por líneas rectas. Si $C$ es la cara exterior, entonces todas las aristas (como máximo 2) de $E(H) \setminus E(G)$ son aristas de la cara exterior de la incrustación de $H$ . Entonces es posible colocar $v$ en la cara exterior de $H - (E(H) \setminus E(G))$ y conectarlo con todos los vecinos en $G$ por líneas rectas.

P. S. Ambos casos de colocación de $v$ son evidentes cuando $\deg v = 3$ y $\deg v = 4$ y no es difícil de probar para $\deg v = 5$ Pregunte en los comentarios si es necesario.

Answer 2

Este resultado se conoce como el teorema de Fáry, véase por ejemplo http://en.wikipedia.org/wiki/Fary%27s_theorem

Hay otras pruebas; por ejemplo, se deduce del teorema principal del artículo de Tutte "Cómo dibujar un gráfico".