Comprobando si un grafo es plano

Question

Tengo que verificar si un grafo es planar. El tipo dado es

$$ e 3v 6 .$$

De Wikipedia:

Se debe tener en cuenta que estos teoremas proporcionan condiciones necesarias para la planaridad que no son condiciones suficientes, por lo tanto, solo se pueden usar para demostrar que un grafo no es planar, no que lo sea. Si fallan tanto el teorema 1 como el 2, se pueden utilizar otros métodos.

Me pregunto qué debo hacer para demostrar que un grafo es planar.

Answer 1

¿Estás buscando el siguiente resultado?

Teorema: En un grafo plano simple y conectado con $v$ vértices y $e$ bordes, si $v \geq 3$, entonces $e \leq 3v-6$.

Esto se suele demostrar a través de la Fórmula Característica de Euler (por ejemplo, aquí [advertencia pdf]); una vez lo propuse como pregunta de tarea.

Este teorema puede usarse para mostrar por ejemplo que $K_5$ no es plano (ya que no cumple $e \leq 3v-6$). Sin embargo, como comentó Alon Amit, el límite $e ≤ 3v-6$ también puede ser cumplido por grafos no planos, como $K_{3,3}$ (donde se necesitan argumentos más sofisticados en su lugar).

La forma más directa (humana) de mostrar que un grafo es plano es dibujándolo en el plano (sin que las aristas se crucen). Los teoremas de Kuratowski y Wagner son resultados importantes que dan condiciones necesarias y suficientes para la planaridad.

Si estás buscando un software en particular, no creo poder explicarlo mejor que en la publicación de StackExchange que mencionó Shahab (aquí).

Answer 2

En realidad, un grafo plano debe ser un grafo disperso lo que en el caso de $K_{3,3}$ significa que contiene $9$ aristas y $6$ vértices, lo que muestra que $K_{3,3}$ no es disperso. Por verificación de Euler, $K_{3,3}$ no contiene ciclos o triángulos de longitud $3$, lo que significa que $e \leq 2v-6$ no se cumple.

Answer 3

Una adición a la publicación de Douglas S. Stones sobre este tema, donde menciona $K_{3,3}$. Este grafo es bipartito y la longitud más corta de un ciclo en este grafo es $4$.

Para $K_5$ y $K_{3,3}$ se pueden utilizar los criterios siguientes, mencionados en el artículo de Wikipedia sobre grafos planares. (Estos son precisamente los resultados a los que te refieres como Teorema 1 y Teorema 2 en tu publicación.)

Para un grafo planar con $v$ vértices y $e$ aristas, se cumple lo siguiente:

• Si $v \ge 3$ entonces $e \le 3v - 6$;
• Si $v \ge 3$ y no hay ciclos de longitud $3$, entonces $e \le 2v - 4.

(El primero se puede usar para demostrar que $K_5$ no es planar, y el segundo se puede usar para $K_{3,3}$.)

La idea de ambas pruebas es similar y se basa en la fórmula de Euler $$v-e+f=2,$$ que es equivalente a $f=2-v+e$.

El borde de cada cara consiste en al menos $3$ aristas. Dado que cada arista pertenece a los bordes de dos caras, si sumas las longitudes de los bordes de todas las caras, obtienes precisamente $2e$. Así que vemos que
$2e\ge 3f$
$2e\ge 6-3v+3e$
$3v-6\ge e$.

Si, además, sabemos que el ciclo más corto tiene al menos longitud $4$, vemos que cada borde debe tener al menos $4$ aristas. Por lo tanto
$2e\ge 4f$
$2e\ge 8-4v+4e$
$e\ge 4-2v+2e$
$2v-4\ge e$.

Answer 4

Para demostrar que un grafo dado es planar, simplemente debemos dibujarlo en un plano y si se puede dibujar con la condición de que ninguna dos aristas se crucen entre sí, entonces podemos decir que el grafo dado es planar. Tan simple como eso.