Planaridad de grafos
Grafo planar
Un grafo es planar (o un grafo es plano) si puede dibujarse en un papel sin que se crucen aristas. Esta es una de las definiciones más fáciles de entender en la teoría de grafos. Pero no es fácil implementar un algoritmo que nos diga si un grafo es planar.
Un grafo con 4 o menos nodos es siempre planar. Es obvio que con 3 o menos lo es, pues con con 1 nodo es un punto, con 2 nodos es un segmento y con 3 es un triángulo, figuras geométricas que se dibujan en el plano sin que se crucen sus aristas.
Veamos uno con 4 nodos, como observamos en el primero de la Figura (grafos que puede importar con los JSON en el archivo de texto graph-complete-k4.txt), un grafo completo con aristas entre todos sus nodos que al generarlo en la aplicación Grafos SVG se dispone visualmente en forma de círculo, con lo que se dará necesariamente cruce de aristas con 4 o más nodos.
En la segunda imagen de la Figura desplazamos la arista [1,3] usando la propiedad lineOffset para evitar el cruce de aristas. O bien hacemos un círculo disponiendo el nodo 2 en el centro, con lo que también no se cruzan aristas. Así que si hemos conseguido dibujarlo en el plano sin cruzar aristas podemos deducir que K4 es planar. Cualquier grafo conectado con 4 nodos tendrá las mismas o menos aristas que el K4, así que siempre podremos dibujarlo en el plano sin cruzar aristas.
Hay un par de teoremas básicos que parece que podrían servir para comprobar la planaridad de un grafo:
- Si un grafo es planar con n ≥ 3 nodos y a aristas entonces a ≤ 3n - 6
- Si un grafo es planar con n > 3 nodos y a aristas y no existen ciclos de longitud 3 nodos entonces a ≤ 2n - 4
Vea que el "si ... entonces ..." (en lugar de "si y solo si") quiere decir que si no se cumple podemos asegurar que es no planar pero si se cumple aún tendremos que hacer más comprobaciones.
Test no planaridad testGraphNoPlanar()
Con lo que vimos antes podríamos intentar implementar un algoritmo que compruebe la no planaridad de un grafo en base a estos principios de no planaridad:
- Con n ≤ 4 nodos siempre es planar.
- Con n ≥ 5 nodos y a aristas es no planar si a > 3n - 6
- Con n ≥ 5 nodos, a aristas y sin ciclos de longitud 3 es no planar si a > 2n - 4
- En otro caso si contiene un subgrafo K5 o B33 es no planar.
- En otro caso no puede deducirse la planaridad con estos principios.
Los tres primeros puntos se explican en el apartado anterior y el cuarto lo veremos después. Estos principios de no planaridad se aplican al algoritmo testGraphNoPlanar().
function testGraphNoPlanar({matrix=[], useGetCycles=false, useGetSubgraph=false}) {
let result = [null, "It was not possible to determine if the graph is planar"], temp;
result.warnings = [];
try {
let n = matrix.length;
if (temp = isGraphDirected({matrix}), typeof temp==="string") throw new Error(temp);
let directed = temp;
if (directed) {
if (temp = getUndirectedMatrix({matrix}), typeof temp==="string") throw new Error(temp);
matrix = temp;
}
if (temp = getMatrixModeValue({matrix}), typeof temp==="string") throw new Error(temp);
let [modeValue, nullValue] = temp;
if (modeValue!=="0/1") {
matrix = matrix.map(v => v.map(w => w===nullValue ? 0 : 1));
}
if (n<=4) { // (1)
result = [true, `Graphs with vertices ≤ 4 are always planar`];
} else {
if (temp = getTotalEdges({matrix}), typeof temp==="string") throw new Error(temp);
let totalEdges = temp;
if (totalEdges > 3*n-6){ // (2)
result = [false, `Edges > 3 × Vertices - 6 ⇒ ${totalEdges}>3×${n}-6 ⇒ ${totalEdges} > ${3*n-6}`];
} else {
let cyclesSize3 = false;
if (useGetCycles) {
if (temp = getCyclesAll({matrix}), typeof temp==="string") throw new Error(temp);
if (temp.hasOwnProperty("warning")) throw new Error(temp.warning);
let cycles = temp;
cyclesSize3 = cycles.some(v => v.length===4);
} else {
let list = Array.from({length:n}, (v,i) => i);
let c3 = combine(list, 3);
if (c3.warning) throw new Error(c3.warning)
for (let c of c3) {
if (matrix[c[0]][c[1]]===1 && matrix[c[0]][c[2]]===1 && matrix[c[1]][c[2]]===1){
cyclesSize3 = true;
break;
}
}
}
if (!cyclesSize3 && totalEdges>2*n-4){ // (3)
result = [false, `There are no size 3 cycles and Edges > 2 × Vertices - 4 ⇒ ${totalEdges}>2×${n}-4 ⇒ ${totalEdges} > ${2*n-4}`];
} else {
// (4) Test if there is a K5 or B33 subgraph for no planarity
}
}
}
} catch(e){result = e.message}
return result;
}La primera parte hasta el punto (1) es para convertir el grafo en no dirigido con isGraphDirected() y getUndirectedMatrix(), pues en el fondo la planaridad de un grafo dirigido es la misma que no dirigido y es más fácil tratar con estos últimos. También consultamos el modo valores con getMatrixModeValue() para convertirlo a "0/1" si no lo fuera, pues también es más fácil este modo y no afecta a la planaridad.
Si no puede deducirse la planaridad devolverá el resultado [null, "It was not possible to determine if the graph is planar"]. La primera posición del resultado puede ser "null", "true" o "false". Solo devolverá "true" si el grafo tiene 4 o menos nodos en el principio (1). En otro caso aplica los principios (2), (3) y (4) (cuyo código de este último principio hemos omitido y explicaremos después) para devolver en su caso "false". Pero si no se cumplen devolverá "null" con lo que no se puede deducir la planaridad con el test. Observe que, a excepción del primer principio, el resto trata de descubrir la no planaridad más que la planaridad.
Obtenemos el total de aristas con getTotalEdges(). Para el tercer principio necesitamos comprobar si el grafo tiene ciclos de longitud 3. Podemos usar el algoritmo getCyclesAll() si pasamos el argumento useGetCycles verdadero. Pero obtener todos los ciclos de un grafo es muy costoso, por lo que ofrecemos la posibilidad de obtener todas las combinaciones de la lista de nodos en conjuntos de 3 nodos y determinar que hay aristas entre ellos, con lo que formarán un ciclo de longitud 3.
En cualquier caso comprobar si hay ciclos de longitud 3 así como usar las combinaciones es muy costoso, por lo que este algoritmo puede servir de base teórica, pero díficilmente podría formar parte de un algoritmo para saber si un grafo es plano.
Aplicando ese algoritmo a los dos grafos K5 (completo de 5 nodos) y B3,3 (bipartito completo de 3+3 nodos) de la Figura obtenemos estos resultados de no planaridad respectivamente, que responden a los principios 2 y 3 de planaridad anteriores:
Para K5: Time: 0 ms Es el grafo planar: [false, "Edges > 3 × Vertices - 6 ⇒ 10>3×5-6 ⇒ 10 > 9"] Para B3,3: Time: 1 ms Es el grafo planar: [false, "There are no size 3 cycles and Edges > 2 × Vertices - 4 ⇒ 9>2×6-4 ⇒ 9 > 8"]
Todos los grafos completos Kn con 5 o más nodos no son planares pues cumplen el segundo principio de los anteriores. Esto es fácil de demostrar pues un grafo completo con n nodos tiene (n2-n)/2 aristas y es obvio que (n2-n)/2 > 3n-6 para n≥5 si consideramos sólo valores enteros, como se observa en la gráfica en azul de la Figura que está por encima de la roja (importar con graphic-principles.txt en la aplicación gráficas matemáticas).
Y un grafo bipartito completo con n = m+m nodos tiene m2 = (n/2)2 aristas con lo que también se observa que (n/2)2 > 2n-4 para valores enteros de n≥5 (gráficas verde y magenta), con lo que se cumple el tercer principio pues además un grafo bipartito no contiene ciclos de longitud impar y, por tanto de longitud 3. Observe que los ciclos en el B3,3 son de longitud 4.
De hecho todos los Bm,m con m=3 o m=4 no cumplen el segundo principio y si cumplen el tercero. Y el resto con m≥5 cumplirán también el segundo. En la Figura vemos la representación del número de aristas de grafos Bm,m donde se observa que (n/2)2 > 3n-6 para n ≥10 tomando valores enteros, con lo que sucederá para m≥5. Importar con graphic-principles-bmm.txt en la aplicación gráficas matemáticas.
Aparte de estos Kn y Bm,m no es fácil encontrar grafos de ejemplo que cumplan estos principios de no planaridad.
Aparte de los grafos completos Kn y bipartitos completos Bm,m, el único grafo de los que aparecen en la sección de generación de la aplicación que cumple el segundo principio de no planaridad es el grafo SUDOKU que vemos en la Figura no encontrando ningún otro que cumpla el tercero. Este grafo tiene 81 nodos y 810 aristas con el resultado del test no planar devolviendo esto:
Time: 0 ms Es el grafo planar: [false, "Edges > 3 × Vertices - 6 ⇒ 810>3×81-6 ⇒ 810 > 237"]
Cada una de las 9 cajas del Sudoku (grupos de 3×3 celdas) es realmente un K9, grafo completo de 9 nodos, como se observa en la Figura, subgrafo que extraemos con el algoritmo getSubgraph() indicando la lista de nodos "0,1,2,9,10,11,18,19,20" de la primera caja, obteniéndose un matriz de adyacencia que importamos y luego aplicamos un ajuste visual a círculo. Se comprueba que es un grafo completo con el algoritmo isGraphComplete().
Time: 0 ms Test graph no planar: [false, "Edges > 3 × Vertices - 6 ⇒ 36>3×9-6 ⇒ 36 > 21"]
Si pasamos el testGraphNoPlanar() a ese grafo K9 de la Figura obtendremos este resultado verificándose que es no planar con el segundo principio que vimos más arriba.
Observe en la Figura que no hay forma de dibujar en el plano un K5 o un B3,3 sin cruzar aristas, pues aunque separemos alguna aristas que se cruzan siempre quedarán un par de ellas que no hay forma de separarlas.
Sin embargo un K4 o un B2,2 (que es el anterior al B3,3) tienen 4 nodos y ya vimos que cualquier grafo con 4 nodos siempre es planar.
Además sucede que en cualquier grafo completo con más de 5 nodos siempre existe un subgrafo K5, como podemos ver en la Figura donde resaltamos un K5 en un K7 obtenido con el algoritmo getInducedSubgraph(). Y lo mismo pasa con el B3,3.
Esto nos podría dar una idea acerca de si un grafo contiene un subgrafo que es el menor de los completos no planares K5 o B3,3 entonces nos serviría para decidir que no es planar. Y es lo que haremos en el punto (4) del algoritmo testGraphNoPlanar cuya parte omitimos arriba y ahora exponemos:
...
} else {
// (4) Test if there is a K5 or B33 subgraph for no planarity
if (useGetSubgraph) { // Use algorithm getInducedSubgraph()
let list = Array.from({length:n}, (v,i) => i);
let k5 = [];
let c5 = combine(list, 5);
if (c5.warning) {
result[1] += ". " + c5.warning;
return result;
}
for (let c of c5) {
if (temp = getInducedSubgraph({matrix, indexesSubgraph:c}), typeof temp==="string") throw new Error(temp);
let subgraph = temp;
if (temp = isGraphComplete({matrix:subgraph}), typeof temp==="string") throw new Error(temp);
let isComplete = temp;
if (isComplete) {
k5 = c;
break;
}
}
let b33 = [];
let c6 = combine(list, 6);
if (c6.warning) {
result[1] += ". " + c6.warning;
return result;
}
for (let c of c6) {
if (temp = getInducedSubgraph({matrix, indexesSubgraph:c}), typeof temp==="string") throw new Error(temp);
let subgraph = temp;
if (temp = isGraphBipartiteComplete({matrix:subgraph}), typeof temp==="string") throw new Error(temp);
let isBipartiteComplete33 = temp[0] && temp[1].length===temp[2].length;
if (isBipartiteComplete33) {
b33 = c;
break;
}
}
if (k5.length>0 || b33.length>0) {
result[0] = false;
result[1] = `K5 = ${JSON.stringify(k5)}, B33 = ${JSON.stringify(b33)}`;
} else {
result[1] += `. K5 = ${JSON.stringify(k5)}, B33 = ${JSON.stringify(b33)}`;
}
} else { // Use algorithm isSubgraphIsomorphic()
let k5 = [[0,1,1,1,1],[1,0,1,1,1],[1,1,0,1,1],[1,1,1,0,1],[1,1,1,1,0]];
if (temp = isSubgraphIsomorphic({matrix, submatrix:k5}), typeof temp==="string") throw new Error(temp);
let {isomorphic, indexes} = temp;
if (isomorphic) {
result[0] = false;
result[1] = `K5 = ${JSON.stringify(indexes)}}`;
} else {
let b33 = [[0,0,0,1,1,1],[0,0,0,1,1,1],[0,0,0,1,1,1],[1,1,1,0,0,0],[1,1,1,0,0,0],[1,1,1,0,0,0]];
if (temp = isSubgraphIsomorphic({matrix, submatrix:b33}), typeof temp==="string") throw new Error(temp);
let {isomorphic, indexes} = temp;
if (isomorphic) {
result[0] = false;
result[1] = `B33 = ${JSON.stringify(indexes)}}`;
}
}
}
}
...Para comprobar que existe un subgrafo K5 o B3,3 tenemos la primera opción de hacerlo usando el algoritmo getInducedSubgraph para lo que obtenemos todas las combinaciones con 5 nodos para el K5 o con 6 nodos para el B3,3 con objeto de obtener los subgrafos y ver si son completos K5 usando el algoritmo isGraphComplete() o isGraphBipartiteComplete() junto a la comprobación de que los subconjuntos son de tamaño 3.
K5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 B3,3 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
La otra opción es usar el algoritmo isSubgraphIsomorphic() pero en el fondo viene a hacer lo mismo, pues también debe hacer combinaciones y extraer subgrafos inducidos para ver si son isomórficos con las matrices de adyacencia de K5 o B3,3 que vemos al lado de este párrafo.
Volvemos a repetir que desde el momento que usamos combinaciones este planteamiento se vuelve intratable para grafos grandes. Por ejemplo, para un grafo con 100 nodos hay C(100, 5) ≃ 7.5×107 combinaciones que probar para ver si es un K5. Y C(100, 6) ≃ 1.2×109 para un B3,3
El otro asunto que ya comentamos es que hay pocos grafos donde probar el algoritmo testGraphNoPlanar(). Construimos un grafo a partir de un K5 rodeándolo de otros vértices, obteniéndose este resultado con testGraphNoPlanar() verificándose que no es planar, basándose en el cuarto principio mediante la comprobación de la existencia de un subgrafo K5 con los nodos [0,1,2,3,4]:
Time: 1 ms Test graph no planar: [false, "K5 = [0,1,2,3,4]}"]
Se podría argumentar acerca del algoritmo testGraphNoPlanar() que si comprobamos todos los subgrafos K5 y B3,3 en un grafo y no se encuentra ninguno entonces podría deducirse que el grafo es planar. Por ejemplo, con el de la Figura obtendremos este resultado:
Time: 1 ms Test graph no planar: [null, "It was not possible to determine if the graph is planar. K5 = [], B33 = []"]
No encontró ningún K5 ni B3,3 en todas las posibles combinaciones C(7, 5) = 21 para K5 ni C(7, 5) = 7 para B3,3 pero obviamente el grafo no es planar pues no hay forma de separar las aristas [0,4] y [2,6]. Así que el hecho de no encontrar K5 o B3,3 no es condición suficiente para deducir que es planar.
En la Figura vemos una subdivisión del grafo K5. Recordemos que es una operación que se realiza seleccionando una arista ([0,2] en este caso) y ejecutar esa operación subdivisión con el botón lo que hará que se inserte un nuevo nodo en medio.
Pasando el testGraphNoPlanar() obtenemos [null, "It was not possible to determine if the graph is planar"] pues no encontró el K5. Pero ese nuevo grafo es claramente no planar, pues una subdivisión de una arista insertando un nodo no modifica la propiedad planar, es decir, si se puede o no dibujar un grafo en el plano también se podrá o no respectivamente si se subdivide una arista. O dicho de otra forma, la planaridad de un grafo no se modifica en su grafo subdivisión. Y esto nos lleva al siguiente teorema.
Teorema de Kuratowski para saber si un grafo es planar
El teorema de Kuratowski nos dice que un grafo es planar si y solo si no contiene un subgrafo que es una subdivisión del grafo completo K5 o el grafo bipartito completo B3,3
Vemos esos grafos K5 y B3,3 en la Figura. Intentemos entender estas definiciones:
- Un subgrafo inducido es un subgrafo con los mismos o menos nodos y sus aristas incidentes.
- Un subgrafo es un subgrafo inducido al que eliminamos cero o más aristas.
- Una subdivisión de un grafo es una operación que consiste en insertar cero o más nodos en una o más aristas del grafo. La operación inversa se denomina suavizado.
- Un grafo completo Kn donde n es el número de nodos del grafo es el que tiene aristas entre todos sus nodos. En este caso nos interesa el K5.
- Un grafo bipartito Bp,q es un grafo donde podemos agrupar los nodos en dos subconjuntos disjuntos de longitudes "p" y "q" donde todas las aristas inciden entre nodos de distintos subconjuntos. Cuando hay aristas entre todos los nodos de un subconjunto al resto de nodos del otro subconjunto decimos además que es bipartito completo. Paro en este caso sólo nos interesa cuando p=q=3 que denominamos B3,3.
Entonces si encontramos una subdivisión de K5 o B3,3 podemos asegurar que el grafo no es planar. Y si no la encontramos será planar. Vea que ahora se establece claramente "...si y solo si..." con lo que se pueden asegurar ambos exteremos. Esto parece fácil de definir pero muy díficil de implementar como veremos en los siguientes apartados.
Pasos para encontrar un subgrafo subdivisión de un B3,3 en un grafo
Ya vimos más arriba que el testGraphNoPlanar() para el grafo de la Figura nos devolvía un resultado incierto pues no encontraba un subgrafo K5 o B3,3. Veamos ahora como podemos encontrar manualmente una subdivisión del B3,3. Puede importar este grafo con el siguiente JSON.
{"nodes":[
{"index":0,"nodeOffset":"23.97 24.36","parent":-1},
{"index":1,"nodeOffset":"-55.28 0.65","parent":-1},
{"index":2,"nodeOffset":"45.24 29.42","parent":0},
{"index":3,"nodeOffset":"6.46 -13.77","parent":[0,1]},
{"index":4,"nodeOffset":"-28.64 29.42","parent":[0,1,2]},
{"index":5,"nodeOffset":"3.42 -24.49","parent":[0,1,2,3]},
{"index":6,"nodeOffset":"-58.77 -0.78","parent":[0,1,2,3,4]}
],
"config":{}}
El primer paso es identificar los nodos "A,B,C,D,E,F" que van a formar parte del B3,3 así como aristas a eliminar y el nodo 5 que formará una subdivisión del B3,3 que finalmente pretendemos conseguir. En la Figura vemos el primer paso de este proceso.
Es obvio que esta identificación es satisfactoria puesto que ya hemos probado varias posibilidades hasta encontrar una que produce el B3,3. Pero suponer que un algoritmo es capaz de buscar en todas esas posibilidades hasta encontrar esta identificación podría ser computacionalmente intratable.
En la Figura vemos el subgrafo obtenido tras eliminar las aristas [[0,5],[0,6],[1,6],[2,4],[3,5]].
Recordamos que un subgrafo es un subgrafo inducido donde indicamos que nodos con sus aristas incidentes vamos a incluir en el subgrafo y a continuación eliminamos cero o más aristas que se indiquen. Para esta acción podemos usar el algoritmo getSubgraph(), tal como hacemos con el ejemplo que vemos en la Figura donde indicamos los nodos a incluir en el subgrafo con "indexesSubgraph": "0,1,2,3,4,5,6" y las aristas a eliminar con "deleteEdgesSubgraph": "[0,5],[0,6],[1,6],[2,4],[3,5]".
Vea que en este momento el subgrafo resultante debe ser una subdivisión del subgrafo B3,3 que pretendemos conseguir. Si tomamos el subgrafo del segundo paso en la Figura y posicionamos los nodos "A,B,C,D,E,F" como un B3,3 observaremos que la arista [B,D] (que se corresponde con índices [1,2]) está subdividida con el nodo 5. Por lo tanto este subgrafo es una subdivisión de B3,3 y ya podríamos deducir que el grafo inicial no es planar.
La operación contraria a la subdivisión es el suavizado que aplicamos al nodo 5 del subgrafo anterior en la Figura obteniéndose el de la Figura. Recordemos que a esta operación se accede en la aplicación con el botón marcando la casilla de suavizado y seleccionando el nodo 5, tras lo cual obtendremos el subgrafo de la Figura.
Este subgrafo ya es un B3,3 tal como podemos comprobar usando el algoritmo isGraphBipartiteComplete() para saber si un grafo es bipartito completo que son de la forma Bn/2,n/2 siendo n un número par, obteniendo el resultado [true,[0,1,5],[2,3,4]] donde se indican las dos particiones [0,1,5] y [2,3,4] de nodos del bipartito.
Tras aplicar un ajuste visual a rejilla con 3 columnas y orden de nodos [0,1,5,2,3,4] que se corresponden con las particiones [0,1,5] y [2,3,4] que vimos más arriba al aplicar isGraphBipartiteComplete(), obtenemos el B3,3 que vemos en la Figura. Así que el grafo inicial no es planar pues encontramos una subdivisión B3,3.
Pasos para encontrar un subgrafo subdivisión K5 en un grafo
Con el mismo grafo de ejemplo del apartado anterior vamos a encontrar manualmente una subdivisión de un K5, identificando 3 aristas a eliminar que vemos en la Figura.
En las siguientes imágenes vemos el estado del grafo tras eliminar esas aristas y suavizar los nodos 5 y 4. El último ya es un K5.
Ya el grafo de la Figura es un K5, que podríamos comprobar con isGraphComplete(). Podemos visualizarlo haciendo un ajuste a círculo con el resultado de la Figura.
Manualmente hemos verificado en el apartado anterior que hay una subdivisión de un B3,3 o bien otra K5 en este apartado, con lo que el grafo no es planar. Lo hemos conseguido manualmente, pero supongamos que encontramos un algoritmo que lo haga. Sin embargo el problema contrario es más grave, es decir, buscar en todas las combinaciones hasta demostrar que no hay ninguna subdivisión de K5 o B3,3 me parece que es computacionalmente impracticable.
Pasos para encontrar un subgrafo B3,3 en un grafo de Petersen
Con el grafo del apartado anterior encontramos un K5 y un B3,3. En cambio el grafo de Petersen de la Figura no tiene una subdivisión de un K5 pero si una de un B3,3. El primer paso es identificar el subgrafo, con lo que tenemos que quitar el nodo 6 (podría ser cualquier otro de los interiores). Esto equivale a obtener un subgrafo inducido con todos los nodos menos ese.
En los siguientes pasos vemos como queda al eliminar ese nodo y hacer 3 suavizados, donde tendremos un B3,3.
Hacemos un ajuste a rejilla para comprobar visualmente en la Figura que es un B3,3 con lo que el grafo de Petersen no es planar.
Teorema de Wagner para saber si un grafo es planar
El teorema de Wagner dice que un grafo es planar si y solo si no contiene un subgrafo menor que es isomórfico a K5 o B3,3. Un menor es el resultado de una o más operaciones de contracción de dos nodos (entre los que puede o no haber una arista).
En la Figura vemos el grafo de Petersen donde selecionamos la arista [0,5] o bien esos dos nodos 0 y 5 y los vamos a contraer. Siempre se contraen dos nodos, pudiendo o no haber una arista entre ellos, aunque en este caso si hay una arista.
En la Figura vemos la operación contracción en la aplicación a la que accedemos con el botón . Con mantener valores nodos vemos que la contraccion de 0 y 5 hace que se incluya el valor "05" al nodo contraido.
En las siguientes imágenes vemos la contracción de los nodos (que en este caso coinciden también coinciden con aristas) [1,6], [4,9], [3,8] y [2,7].
Y finalmente tras 5 contracciones llegamos a un K5 como vemos en la Figura. Por lo tanto en el grafo de Petersen hay un menor K5 y por ello no es planar acorde al teorema de Wagner.
De nuevo, como dijimos con el teorema de Kuratowski, no parece fácil implementar un algoritmo que detecte donde aplicar las contracciones para llegar a un menor K5 o B3,3. Y mucho menos lo contrario, demostrar que ningún menor conduce a un K5 o B3,3 para demostrar que el grafo es plano. Así que todo lo que hemos visto en este tema sirve de poco para llegar a un algoritmo práctico que verifique la planaridad de un grafo.
En siguientes temas intentaremos buscar otras soluciones.
Fórmula de Euler: Caras de un grafo plano
Antes de finalizar este tema se expone la fórmula de Euler sobre las caras de un grafo plano. En la Figura vemos un grafo que ya vimos en la Figura al que le hemos eliminado la arista [0,4], con lo que ahora se puede dibujar en el plano sin que se crucen aristas. Tiene 7 vértices, 14 aristas y 9 caras. Cada cara es una región del plano donde no cruzan aristas.
La fórmula de Euler dice que si un grafo simple plano conexo tiene v vértices, a aristas y c caras entonces v - a + c = 2. Y eso se cumple para este grafo pues 7 - 14 + 9 = 2.
Este teorema es "...si...entonces" con lo que poco nos sirve usarlo al revés, pues no habrá forma de contar las caras de un grafo sin antes saber que es plano. Pues si vemos el grafo inicial en la Figura sin eliminar la arista [0,4] ¿cómo contamos las caras de esa región donde se cruzan dos aristas que no pueden ubicarse sin cruzarse con otras? No creo que la fórmula de Euler nos pueda servir de algo práctico para determinar la planaridad de un grafo.