18 Planaridad

Vocabulario:

planar	un grafo es planar cuando se puede pintar sus vértices y sus aristas
	en un plano de tal manera que ninguna pareja de aristas se interseca
región	una región es un área del plano donde se ha pintado un
	grafo planar que esté confinado por aristas
grafo triangular	un grafo es triangular, si en su representación planar
	en el plano toda región está confinada por tres aristas del grafo

Teorema (Euler):

$G$ planar y conexo con $n\leq 1$, $m$ y $l$ $\qquad\Longrightarrow\qquad$ $n-m+l=2$

Teorema:

$G$ planar con $n\geq 3$ $\qquad\Longrightarrow\qquad$ $m\leq 3n-6$

Teorema:

$G$ maximal planar si es un grafo triangular (y contiene $3n-6$ aristas)

Teorema (Kuratowski):

$G$ es planar $\qquad\Longleftrightarrow\qquad$ no contiene un $K^5$ o un $K^{3,3}$ como minor (o minor topológico)