Árboles Trémaux

Un árbol Trémaux de un grafo no dirigido G es un árbol de recubrimiento (spanning tree) T tal que para cada arista [u,v] de G o "u" es un padre de "v" o "v" es un padre de "u" en T. Al ser T un árbol de recubrimiento que debe usar todos los vértices de G y algunas aristas de G y debe haber un único camino entre dos nodos de G donde debe definirse un nodo raíz, como es característico en un árbol.

En la Figura vemos un grafo dirigido y su árbol Trémaux con raíz 0. Cualquier arista del grafo como la [1,2] cumple que el nodo "2" es padre del "1" en el árbol. Incluso la arista [0,1] que no forma parte del árbol también lo cumple, pues el nodo "0" es padre del "1" en el árbol a través del camino descendente "0-2-1".

Todos los árboles de búsqueda en profundidad (DFS) son árboles Trémaux. En la Figura vemos los árboles DFS con las 4 raíces posibles. El primer árbol es el que vimos antes. En el segundo árbol con la arista [0,1] vemos que "1" es padre de "0" a través del camino descendente "1-2-0". En el tercer árbol con la arista [0,2] vemos que "2" es padre de "0" en el árbol a través del camino descendente "2-1-0". En el cuarto árbol esa arista [0,2] también "2" es padre de "0" a través del mismo camino descendente "2-1-0".

Observamos que el último árbol de la Figura es un camino "3-2-1-0" sin ramas, pues el primero tiene dos ramas "2-1" y "3-1" por ejemplo. Hay otro alternativo "3-2-0-1" también sin ramas. Estos árboles sin ramas son óptimos para aplicar el concepto de planaridad usando los árboles de Trémaux, como veremos después.

Esos dos árboles "3-2-1-0" y "3-2-0-1" pueden encontrarse también con el algoritmo findHamiltonianPathAll() usando la opción encontrar todos activada, como vemos en la Figura, obteniéndose esos dos caminos Hamiltonianos y siendo también árboles Trémaux.

{"3,0":[[3,2,1,0]],"3,1":[[3,2,0,1]]}

No todos los grafos tienen un camino Hamiltoniano, como sucede con los bipartitos completos B_n,2 con n>3 tal como el B_4,2 de la Figura.

Todos los árboles que podamos identificar en el grafo no tienen por que ser Trémaux. Por ejemplo, en la Figura vemos un árbol que hemos extraído con una búsqueda en anchura (BFS) con raíz en el nodo "0". Con la arista [1,2], que no forma parte del árbol, vemos que ni "1" es padre de "2" ni "2" es padre de "1" en el árbol, dado que para llegar de uno a otro no hay un camino descendente pues hay que subir al nodo "0" para luego bajar.

Árboles Trémaux y planaridad de grafos

Ya analizamos en el tema anterior que los grafos completo K5 y bipartito completo B3,3 de la Figura eran no planares.

Vimos también que no hay forma de separar las aristas para que no se crucen, como se observa en la Figura en un intento donde siempre habrán dos interiores como las señaladas en color rojo que no hay donde ubicarlas sin que crucen con otras. Eliminando cualquiera de las aristas 4-1 o 3-0 entonces si es planar.

Si al K5 aplicamos una búsqueda en profundidad DFS con raíz en el nodo "0" obtenemos el resultado de la Figura {"visited": [0,4,3,2,1], "path": [[0,4],[4,3],[3,2],[2,1]]} donde los nodos se visitan en el orden 0, 4, 3, 2, 1.

En la aplicación etiquetamos las aristas con el botón , recordando que el grafo es no dirigido y una arista no dirigida puede escribirse como "i-j" o "j-i" indistintamente. Con dirigidas las presentamos con algún tipo de flecha con lo que "i🡒j" es distinta de "j🡒i". En formato de Array, tal como las maneja la aplicación, una dirigida será también [i,j] o [j,i] aunque de forma normalizada la ponemos con el menor índice primero, como [0,1]. Pero si es dirigida con [0,1] representamos "0🡒1" y con [1,0] representamos "1🡒0".

Tomando el grafo anterior con la búsqueda DFS, construimos manualmente el árbol Trémaux del K5 en la Figura, imponiendo una dirección de aristas. Las aristas en color rojo componen el camino de la búsqueda DFS y son ascendentes partiendo del nodo raíz que se ubica en el fondo de la imagen.

El resto de aristas componen el coárbol de Trémaux, que al contrario que el árbol, tienen direcciones descendentes. Esas coaristas se ubican a un lado u otro del árbol de tal forma que no se crucen, a no ser que sea imposible, como pasa para las aristas 1🡒4 y 3🡒0 que no hay forma de ubicarlas sin que en el lado derecho se crucen, o si pasamos una al lado izquierdo se cruzará con otras. Eliminando una de estas dos aristas se dibuja planar.

En la Figura vemos la construcción manual del árbol Trémaux del DFS del grafo B3,3 que vemos a continuación en la Figura. Nuevamente este grafo es no planar, pues no hay forma de ubicar las aristas "3🡒2" y "4🡒0" sin que se crucen. Eliminando alguna de ellas vemos que con esta disposición puede dibujarse planar.

Si podemos hacer algo en un grafo manualmente quizás es posible que un algoritmo también lo haga de forma automática. Vamos a intentarlo con el nuevo algoritmo isGraphPlanarTremaux() que explicaremos en los siguientes apartados.

Ajuste visual a planar

Implementaremos el algoritmo isGraphPlanarTremaux(), para saber si un grafo es planar con el criterio del árbol de Trémaux. Este algoritmo intentará ubicar las coaristas en el lado izquierdo o derecho sin que se crucen, tal como hicimos manualmente más arriba, devolviéndonos el algoritmo un resultado con las coaristas ubicadas en campos "left", "right" y "none" entre otros, siendo las que se incluyan en "none" las que no se pudieron ubicar.

Pero esto lo explicaremos en los siguientes apartados, pues antes veremos que hacemos con esas ubicaciones de coaristas que lleva a cabo isGraphPlanarTremaux(), ofreciendo ahora la aplicación un nuevo ajuste visual a planar, tal como se observa en la Figura que trata de plasmar visualmente esa disposición de nodos y aristas tal como hicimos manualmente en el apartado anterior. Necesitamos este nuevo ajuste visual pues en los siguientes apartados ofreceremos ajustes visuales de los ejemplos que iremos exponiendo para explicar el algoritmo isGraphPlanarTremaux().

Recordemos que los ajustes visuales, a los que se accede con , modifican la presentación del grafo pero no su matriz de adyacencia, a excepción de este caso que si el grafo es dirigido lo convertirá en no dirigido, pues isGraphPlanarTremaux() sólo funciona con no dirigidos. No hay que olvidar que el objetivo principal de isGraphPlanarTremaux() es comprobar la planaridad de un grafo. Y que la de uno no dirigido es la misma que cualquiera de sus versiones dirigidas. En las opciones de la Figura aparece una nota que lo advierte: Nota: si el grafo es dirigido, se convertirá en no dirigido.

Veamos las opciones de la Figura. La opción Hamiltoniano puede ser basado en un "Ciclo" Hamiltoniano, un "Camino" Hamiltoniano o "Ninguno", en cuyo caso se basará en un árbol DFS, opción que usaremos para este ejemplo de la Figura. En otro apartado explicaremos las otras opciones. El campo espaciado es para distanciar los nodos, de tal forma que 1 corresponde con un radio del círculo de los nodos. El tipo de línea puede ser recta, cuadrática o cúbica para las coaristas. Con etiquetas aristas podemos mostrarlas u ocultarlas. El número de iteraciones es por defecto 10000, aunque para grafos grandes será necesario aumentarlas, como veremos en otro apartado.

En la Figura vemos el ajuste visual a planar del grafo K5 sin usar Hamiltoniano, con lo que usaremos DFS, ubicando automáticamente las coaristas con el algoritmo isGraphPlanarTremaux(). Usamos el tipo de línea curva cuadrática (quadratic).

El árbol de Trémaux es el que se obtiene con el DFS, igual que el que construimos manualmente en el de la Figura, aunque ahora el algoritmo isGraphPlanarTremaux() ubica automáticamente las aristas 1-3 y 3-0 a la izquierda, mientras que 2-4, 2-0 y 1-0 se ubican a la derecha para que no se crucen con las anteriores. Sin embargo no puede ubicar 1-4 en ningún lado sin que se crucen, resaltándola en línea de rayas con color rojo. Por lo tanto este grafo K5 es con toda seguridad no planar, pues el algoritmo comprueba todas las posibilidades de ubicación de las coaristas sin encontrar ninguna donde no se crucen. Entre todas las posibilidades se devuelve aquella donde se dan un menor número de aristas que no puedan ser ubicadas.

En el árbol de Trémaux obviamos la dirección de las aristas no incluyendo flechas, pero si anotamos la dirección de cada arista en su etiqueta, como 0⯈4 por ejemplo. Así el árbol de Trémaux se dispone con la raíz abajo en el nodo "0", ascendiendo en los nodos "4,3,2,1" en el árbol, con las coaristas bajando desde esos nodos hacia otros inferiores.

Eliminando la arista 4-1 del K5, vemos el ajuste a planar en la Figura, realizado automáticamente haciendo uso del algoritmo isGraphPlanarTremaux(). Este algoritmo prueba las coaristas en uno u otro lado hasta que encuentra una combinación donde no se crucen aristas.

En la Figura vemos el ajuste visual a planar del grafo B3,3 ubicando automáticamente las coaristas usando el algoritmo isGraphPlanarTremaux(). Ahora usamos el tipo de línea recta (rect).

El algoritmo busca la combinación de ubicaciones de coaristas que producen el menor número de cruces, observando que la coarista 3-2 no puede ubicarse en ningún lado sin que se cruce con otras.

Es el grafo planar con árbol Trémaux isGraphPlanarTremaux()

En la Figura vemos las opciones para ejecutar el algoritmo isGraphPlanarTremaux() que comprueba si un grafo es planar usando el árbol de Trémaux.

Necesitamos encontrar en el grafo un árbol de Trémaux con el tronco más largo y con las menos ramas posibles cuya razón explicaremos después, siendo la mejor opción un ciclo Hamiltoniano o, si no existe entonces usar un camino Hamiltoniano, pues todos los nodos están en el tronco y no tiene ramas. Pero si un grafo no tiene ciclo o camino Hamiltoniano, entonces podemos buscar con DFS todos los árboles que parten de un nodo identificado como raíz y seleccionar el que produce mejor esa condición, tarea que simplificamos usando el algoritmo getSubtrees() para obtener los subárboles, algoritmo que identifica el tronco y las ramas. Entonces iteramos por todas las raíces y seleccionamos el que mejor cumpla esa condición de tronco más largo y menor cantidad de ramas.

Antes de entrar en más detalles veamos el esquema del algoritmo isGraphPlanarTremaux():

Function isGraphPlanarTremaux(matrix)
    Convert matrix to undirected graph
    Convert matrix to mode 0/1
    If graph is disconnected return "error"
    If testGraphNoPlanar(matrix) is not null return true or false
    If isGraphTree(matrix) return true
    Get Trémaux tree with branches and coedges from Hamiltonian cycle, path or DFS
    Sort coedges by increasing length
    If coedges.length===1 then
        Place coedge on the left
    Else If coedges.length===2 then
        Place coedges on the left and right
    Else
        Place coedges on 2-partitions
    End if
    Return branches and coedges placed on the left, right, outer or none
    if none is empty return true else return false
End Function

Siempre convertimos el grafo en no dirigido, pues la planaridad de uno no dirigido es la misma que la de cualquier versión dirigida. Y también al modo valores "0/1" para simplificar los procesos, pues esto no afecta a la planaridad. Si el grafo es desconectado acusamos un error, pues aunque podríamos separar los distintos componentes conectados y comprobar su planaridad, sin embargo esto resultará en un algoritmo más complejo.

A continuación aplicamos el algoritmo testGraphNoPlanar() que nos dirá si no es planar, pues en ese caso no será necesario seguir con el algoritmo. Recuerde que testGraphNoPlanar() solo puede asegurar que es planar si el grafo tiene 4 o menos nodos, asegurando en ciertos casos que no es planar, aunque cuando no se dan esos casos no se puede asegurar nada devolviendo el valor null. Adicionalmente también comprobamos si el grafo es un árbol con isGraphTree() pues todo árbol es planar.

En caso de no obtener un resultado de planaridad, pasamos a verificarlo usando el árbol de Trémaux. Como ejemplo tomamos el grafo muy simple de la Figura que es planar, al que aplicamos el algoritmo isGraphPlanarTremaux(), con la opción "Ninguno" para usar Hamiltoniano que vemos en la Figura, con lo que se usará DFS. La opción usar test planar que aplica testGraphNoPlanar() resultará incierto, pues tiene más de 4 nodos y no cumple las condiciones para asegurar que es no planar.

El algoritmo obtiene las coaristas y luego las ordena por orden creciente de longitud para a continuación aplicar las particiones en dos subconjuntos a esa lista ordenada de coaristas. La idea es ubicar primero las coaristas más pequeñas dejando para el final las más largas, pues en algunos casos podría ser ubicadas como coaristas exteriores ("outer"), algo que explicaremos después.

El resultado del algoritmo isGraphPlanarTremaux() es el siguiente, donde ahora no entramos en más detalles pues lo explicaremos en siguientes apartados. El objetivo de este ejemplo es tener un visión global del resultado y como esto se visualiza con el ajuste visual a planar que explicábamos en el apartado anterior.

Time: 1 ms
Is graph planar Trémaux: {
"planar":true,
"useTestPlanar":true,
"useHamiltonian":"none",
"left":[[0,0,0,0,0],[1,4,5,1,0]],
"right":[[1,0,5,0,0]],
"outer":[],
"none":[],
"partition":[[0,1],[2]],
"relocated":[],
"numCoedges":3,
"totalPartitions":3,
"numPartition":1,
"runnedPartitions":1,
"totalRelocated":0,
"root":0,
"reverse":false,
"visited":[0,4,3,5,2,1],
"path":[[0,4],[4,3],[3,5],[3,2],[2,1]],
"branches":[[0,4,3,2,1],[3,5]],
"coedges":[[0,0,0,0,0],[1,4,5,1,0],[1,0,5,0,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[3,0],
"warnings":[
    "Note: branch '[3,5]' has not coedges and will be ignored"
]}

El grafo es planar, tal como vemos en el campo "planar":true. En "branches" [[0,4,3,2,1],[3,5]] están las ramas del árbol DFS, siendo siempre la primera [0,4,3,2,1] el tronco y el resto son las propias ramas del árbol, en este caso la única [3,5].

El campo "left" contiene las coaristas 0-0 y 1-4 que se ubican a la izquierda, siendo la primera un autobucle que podría ubicarse a la izquierda o derecha indistintamente pues no afecta a la planaridad, optando el algoritmo por ubicarla en "left". A la derecha "right" se ubica la coarista 1-0.

En la Figura vemos el ajuste visual a planar observando que el árbol DFS produce la rama 3-5 que se ubica a la derecha y que, al no tener coaristas, no afecta a la planaridad. La aplicación no siempre posiciona bien estas ramas, pero podemos ajustar manualmente la coarista 1-0 para que no cruce esa rama como vemos en la Figura.

Para evitar árboles DFS con ramas usaremos la opción usar Hamiltoniano con valor "camino" ("path") que vemos en la Figura, con lo que será más fácil ubicar las coaristas pues nunca habrán ramas. Observe que ahora tenemos en "branches" [[5,3,2,1,4,0]] con un sólo tronco, distinto al anterior. Y sin ramas, pues los caminos Hamiltonianos son árboles DFS sin ramas.

Time: 1 ms
Is graph planar Trémaux: {
"planar":true,
"useTestPlanar":true,
"useHamiltonian":"path",
"left":[[0,0,5,5,0],[0,1,5,3,0]],
"right":[[4,3,4,1,0]],
"outer":[],
"none":[],
"partition":[[0,1],[2]],
"relocated":[],
"numCoedges":3,
"totalPartitions":3,
"numPartition":1,
"runnedPartitions":1,
"totalRelocated":0,
"root":5,
"reverse":false,
"visited":[5,3,2,1,4,0],
"path":[[3,5],[2,3],[1,2],[1,4],[0,4]],
"branches":[[5,3,2,1,4,0]],
"coedges":[[0,0,5,5,0],[0,1,5,3,0],
    [4,3,4,1,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[3],
"warnings":[
    "Note: a Hamiltonian path was found"
]}

Ubicación de coaristas en el árbol Trémaux de un grafo no planar

En la Figura vemos el ajuste visual a planar que hacemos sobre el siguiente grafo de Petersen de la Figura, que ya sabemos que no es planar. En las opciones del algoritmo isGraphPlanarTremaux() que vemos en la Figura se marcan usar test planar y usar Hamiltoniano con el valor "ciclo" ("cycle"). El algoritmo testGraphNoPlanar() no es capaz de determinar la planaridad del grafo, con lo que intentará buscar un ciclo Hamiltoniano, que al no encontrarse, buscará un camino Hamiltoniano, encontrándose uno con los nodos que vemos en el resultado más abajo en el campo "visited" [2,1,6,8,3,4,9,7,5,0] y que son los nodos en orden ascendente del tronco del árbol de la Figura.

El grafo de Petersen no tiene un ciclo Hamiltoniano pero si tiene un camino Hamiltoniano. Es cierto que un ciclo Hamiltoniano es a la vez un camino Hamiltoniano, o mejor dicho, contiene un camino Hamiltoniano si ignoramos alguna arista del ciclo, pero no lo es a la inversa, pues puede haber un camino Hamiltoniano que recorra todos los nodos pero que no forme parte de un ciclo.

Recordemos que un ciclo es una lista de nodos v₀, v₁, ..., v_i, v₀ con arista entre cada dos nodos sucesivos, donde empezamos en un nodo y acabamos en el mismo. Un camino en cambio sería la misma lista de nodos pero el último nodo no sería igual que el primero. Cuando el subíndice i es igual que el número de nodos del grafo hablamos entonces de ciclo y camino Hamiltoniano.

Con el valor "cycle" para la opción usar Hamiltoniano el algoritmo isGraphPlanarTremaux() intenta primero buscar un ciclo Hamiltoniano, si no lo encuentra intenta buscar un camino Hamiltoniano, y si no lo encuentra pasa a obtener el árbol DFS. La razón de esto es que si un grafo tiene un ciclo Hamiltoniano es más fácil de obtener que buscar entre todas las combinaciones de 2 nodos del grafo un camino que recorra todos los nodos, pues es eso precisamente la definición de un camino Hamiltoniano. En otro caso se obtiene el árbol DFS, pues todo grafo lo tiene, pero ya hemos dicho que esta es la peor situación pues puede producir un árbol con ramas que puede dificultar la ubicación de coaristas.

Este es el resultado obtenido con isGraphPlanarTremaux() para el grafo de Petersen:

Time: 4 ms
Is graph planar Trémaux: {
"planar":false,
"useTestPlanar":true,
"useHamiltonian":"cycle",
"left":[[0,4,9,5,0],[3,2,4,0,0]],
"right":[[0,1,9,1,0],[9,6,6,2,0]],
"outer":[],
"none":[[5,8,8,3,0],[7,2,7,0,0]],
"partition":[[0,1,2,3,4],[5]],
"relocated":[2,3,4],
"numCoedges":6,
"totalPartitions":31,
"numPartition":1,
"runnedPartitions":31,
"totalRelocated":28,
"root":2,
"reverse":false,
"visited":[2,1,6,8,3,4,9,7,5,0],
"path":[[1,2],[1,6],[6,8],[3,8],[3,4],[4,9],[7,9],[5,7],[0,5]],
"branches":[[2,1,6,8,3,4,9,7,5,0]],
"coedges":[[0,4,9,5,0],[3,2,4,0,0],[9,6,6,2,0],[5,8,8,3,0],[7,2,7,0,0],[0,1,9,1,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[6],
"warnings":[
    "Note: no Hamiltonian cycle was found, testing with Hamiltonian path",
    "Note: a Hamiltonian path was found"
]}

Vemos en la Figura los avisos ("warnings") que la aplicación muestra en pantalla, traducción de los que vemos en ese campo "warnings" del resultado anterior. Al usar la opción "cycle" intentó buscar un ciclo Hamiltoniano y al no encontrarlo pasó a buscar un camino Hamiltoniano.

El ciclo o camino Hamiltoniano no produce ramas estando todos lo nodos en el tronco. Esta es la mejor opción pues después veremos que ubicar las ramas no es fácil. En la Figura vemos una disposición de las coaristas, con dos de ellas en color rojo que son las que no se pudieron ubicar. Las vemos en el campo "none" [[5,8,8,3,0],[7,2,7,0,0]], recordando que por ejemplo la coarista [3,2,4,0,0] se refiere a la arista 3-2 del grafo que arranca en el 4+1=5º nodo del árbol de Trémaux y finaliza en el nodo 0+1=1º, el nodo raíz. El último 0 se refiere a en que rama en "branches" [[2,1,6,8,3,4,9,7,5,0]] encontramos esa arista 3-2, que es el 0 pues sólo hay una rama que es el tronco.

Los campos "visited" [2,1,6,8,3,4,9,7,5,0] y "path" [[1,2],[1,6],[6,8],[3,8],[3,4],[4,9],[7,9],[5,7],[0,5] son los que se obtienen con el algoritmo getDepthFirstSearchIterative() que obtiene el árbol con DFS en caso de que no hubiésemos marcado la opción usar camino Hamiltoniano, pues en este caso usaremos el algoritmo findHamiltonianPathAll() que nos devuelve los "visited" de todos los caminos posibles, devolviendo {"2,0":[[2,1,6,8,3,4,9,7,5,0]], "3,0":[[3,2,1,6,8,5,7,9,4,0]], "3,1": ...} con hasta 30 caminos posibles, tomándose sólo el primero "2,0" que se inicia en el nodo raíz "2" y acaba en el nodo "0". A partir de esa lista de nodos visitados en "visited" componemos la lista de aristas en "path".

Sea sin o con camino Hamiltoniano, tendremos entonces "visited" y "path" que define el árbol, de donde obtendremos las coaristas como el resto de aristas del grafo que no se encuentran en "path" y que vemos en "coedges" reproduciéndolas a continuación indicando el índice de posición en el Array:

            0           1           2           3           4           5
"coedges":[[0,4,9,5,0],[3,2,4,0,0],[9,6,6,2,0],[5,8,8,3,0],[7,2,7,0,0],[0,1,9,1,0]]

Tenemos entonces 6 coaristas referenciadas con índices del conjunto M = {0,1,2,3,4,5} que debemos ubicar en un lado u otro del árbol de Trémaux. Los números de Stirling de segunda clase S2(n, k) o también denotados como {nk}, es el número de formas de particionar un conjunto de n elementos en k subconjuntos no vacíos. Así que hemos de buscar las particiones del conjunto M de las coaristas en subconjuntos de tamaño 2, para lo que usaremos uno de los algoritmos de particiones parciales, en este caso kPartition1(list, 2), que encontramos en la aplicación Combine Tools que vemos en la Figura, obteniéndose las siguientes S2(6, 2) = 31 particiones con los índices de las coaristas en el campo "coedges":

[[0,1,2,3,4],[5]],[[0,1,2,3,5],[4]],[[0,1,2,3],[4,5]],[[0,1,2,4,5],[3]],[[0,1,2,4],[3,5]],
[[0,1,2,5],[3,4]],[[0,1,2],[3,4,5]],[[0,1,3,4,5],[2]],[[0,1,3,4],[2,5]],[[0,1,3,5],[2,4]],
[[0,1,3],[2,4,5]],[[0,1,4,5],[2,3]],[[0,1,4],[2,3,5]],[[0,1,5],[2,3,4]],[[0,1],[2,3,4,5]],
[[0,2,3,4,5],[1]],[[0,2,3,4],[1,5]],[[0,2,3,5],[1,4]],[[0,2,3],[1,4,5]],[[0,2,4,5],[1,3]],
[[0,2,4],[1,3,5]],[[0,2,5],[1,3,4]],[[0,2],[1,3,4,5]],[[0,3,4,5],[1,2]],[[0,3,4],[1,2,5]],
[[0,3,5],[1,2,4]],[[0,3],[1,2,4,5]],[[0,4,5],[1,2,3]],[[0,4],[1,2,3,5]],[[0,5],[1,2,3,4]],
[[0],[1,2,3,4,5]]

Observe que las particiones no tienen subconjuntos vacíos, así que la posibilidad de ubicar todas las aristas en un sólo lado no se contempla aquí pero si todas caben en un lado, también cabría cualquier partición de ellas.

...
"partition":[[0,1,2,3,4],[5]],
"relocated":[2,3,4],
"numCoedges":6,
"totalPartitions":31,
"numPartition":1,
"runnedPartitions":31,
"totalRelocated":28,
...

Entre los resultados obtenidos con isGraphPlanarTremaux() vemos "numCoedges":6 y "totalPartitions":31 que son todas las particiones donde debe ubicar coaristas, observando que cuando el grafo es no planar como en este caso tiene que comprobarlas todas, reflejándose en "runnedPartitions":31 indicando que tuvo que ejecutarlas todas. Se devuelve la ubicación de la partición que menos coaristas puede ubicar, que son las que se incluirán en el campo "none":[[5,8,8,3,0],[7,2,7,0,0]] y que se corresponde con la primera partición que se indica en "numPartition":1 y también en "partition":[[0,1,2,3,4],[5]].

Recordamos que las coaristas eran 0-4, 3-2, 9-6, 5-8, 7-2, 0-1 indexadas con ese orden desde 0 hasta 5. Cuando el algoritmo prueba una partición y resulta que se cruzan aristas podría desecharla y pasar a la siguiente. Así con la primera partición [[0,1,2,3,4],[5]] intentará ubicar las 5 primeras coaristas 0-4, 3-2, 9-6, 5-8, 7-2 a la izquierda y la última 0-1 a la derecha, algo que no es posible, pues las primeras a la izquierda se cruzarían. Así que antes de desechar esa partición y probar otra itentará relocalizar las que se cruzan que son las indicadas en "relocated":[2,3,4] para las coaristas 9-6, 5-8 y 7-2, que reubica a la derecha. Aún así 7-2 y 5-8 se cruzan y finalizan en "none":[[5,8,8,3,0],[7,2,7,0,0]]. Estas coaristas 7-2 y 5-8 de "none" se dibujan en el lado derecho en línea a trozos y color rojo, como vemos en la Figura, pero realmente podrían dibujarse en cualquier lado pues no cabe en ninguno de ellos.

...
"left":[[0,4,9,5,0],[3,2,4,0,0]],
"right":[[0,1,9,1,0],[9,6,6,2,0]],
"outer":[],
"none":[[5,8,8,3,0],[7,2,7,0,0]],
...

Esta es la primera disposición de coaristas, con 3-2 y 0-4 a la izquierda ("left"), 9-6 y 0-1 a la derecha ("right") y 7-2 y 5-8 sin ubicación ("none"). Y aunque sigue buscando en las 31 particiones posibles pues el grafo es no planar, no encontrará otra disposición que produzca un menor número de coaristas no ubicables, es decir, el campo "none" no tendrá menos de 2 aristas no ubicables, así que se devuelve esta primera disposición que se indica en "numPartition":1.

Podríamos pensar que al probar la primera partición [[0,1,2,3,4],[5]] con la relocalización de [2,3,4] realmente estamos probando también [[0,1],[2,3,4,5]], con lo que podríamos ignorar esa partición entre las 31 que habremos de probar pues el grafo es no planar. Sin embargo aparte de la relocalización también se intenta en cada partición ubicar las que se crucen en "outer", algo que explicaremos en el siguiente apartado.

En la sección generación de grafos que podemos acceder con el botón encontramos los grafos Platónicos, donde uno de ellos es el grafo dodecaédrico con 20 nodos que se genera en la aplicación tal como aparece en la Figura, donde prescindimos de etiquetas de nodos y aristas, observando que con esa disposición no aparenta planar pues las aristas interiores se cruzan. Decíamos en ese tema que todos los grafos Platónicos tienen un ciclo Hamiltoniano (y por tanto también un camino Hamiltoniano), por lo que son ideales para aplicar el agoritmo que estamos viendo.

Obteniendo el árbol Trémaux con isGraphPlanarTremaux() con la opción "camino" ("path") para usarHamiltoniano y también para aplicar el ajuste visual a planar, se obtiene la disposición planar que vemos en la Figura, usando solo coaristas sin ramas y ubicándolas a derecha o izquierda sin que se cruce ninguna.

Suele disponerse el grafo dodecaédrico como vemos en la Figura, observando claramente su disposición planar. Usando la opción "ciclo" o incluso "ninguno", con lo que usaría DFS, se obtendría también un árbol sin ramas, aunque con otra disposición de coaristas sin cruzarse.

Se obtiene el siguiente resultado con isGraphPlanarTremaux():

Time: 88 ms
Is graph planar Trémaux: {
"planar":true,
"useTestPlanar":true,
"useHamiltonian":"path",
"left":[[15,5,8,4,0],[10,18,18,14,0],[0,9,19,12,0],[13,3,9,2,0],[11,1,10,0,0]],
"right":[[0,1,19,0,0],[19,17,11,7,0],[8,7,13,6,0],[16,6,15,5,0],[14,4,16,3,0],[12,2,17,1,0]],
"outer":[],
"none":[],
"partition":[[0,1,2,3,4,5,6,7,8,9],[10]],
"relocated":[2,5,7,8,9],
"numCoedges":11,
"totalPartitions":1023,
"numPartition":1,
"runnedPartitions":1,
"totalRelocated":1,
"root":1,
"reverse":false,
"visited":[1,2,3,4,5,6,7,17,15,13,11,19,9,8,18,16,14,12,10,0],
"path":[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,17],[15,17],[13,15],[11,13],[11,19],[9,19],[8,9],[8,18],[16,18],[14,16],[12,14],[10,12],[0,10]]
"branches":[[1,2,3,4,5,6,7,17,15,13,11,19,9,8,18,16,14,12,10,0]],
"coedges":[[15,5,8,4,0],[10,18,18,14,0],[19,17,11,7,0],[0,9,19,12,0],[13,3,9,2,0],[8,7,13,6,0],[11,1,10,0,0],[16,6,15,5,0],[14,4,16,3,0],[12,2,17,1,0],[0,1,19,0,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[11],
"warnings":[
    "Note: a Hamiltonian path was found"
]}

Vemos que con este grafo dodecaédrico hay 1023 particiones con dos subconjuntos, aunque al ser planar solo necesita comprobar la primera, como vemos en "runnedPartitions":1 que indica cuántas particiones fueron ejecutadas. Cuando el grafo es planar el algoritmo isGraphPlanarTremaux() encontrará rápidamente una partición que ubique las coaristas sin que se crucen, tal como observamos con este dodecaédrico de 20 nodos. Pero cuando no es planar el algoritmo puede no resolver el problema con la misma facilidad, como veremos a continuación.

Recordemos que podemos quitarle los valores a los nodos y modificar los radios de los círculos del grafo como vemos en la Figura, actuando sobre las propiedades nodeValueAuto con valor ninguno y nodeRadius con valor 2. Y en el ajuste a planar desmarcar la opción con etiquetas aristas que vemos en la Figura. Así conseguimos el árbol Trémaux de la Figura con menor tamaño aunque sin etiquetas de ninguna clase.

Limitación del número de particiones en el algoritmo basado en el árbol de Trémaux

El ejemplo con el grafo dodecaédrico que vimos en el apartado anterior en la Figura tenía 20 nodos y 30 aristas, obteniendo un árbol de Trémaux usando el camino Hamiltoniano ("path") generando 11 coaristas, dato que podemos comprobar en el campo "numCoedgesToTrunk" con valor [11] y que podemos ver en el resultado del algoritmo isGraphPlanarTremaux(). Ese dato es un Array con los coaristas al tronco que hay en cada rama, siendo en este caso un sólo valor pues aquel árbol no tenía ramas y esas son las 11 coaristas que van desde nodos del tronco a otros nodos del mismo tronco. En el campo "totalPartitions" teníamos el valor 1023, que son las particiones parciales o números de Stirling de segunda clase S2(11, 2) = 1023 para n=11, tal como explicábamos en ese apartado. Ese número aparece en la tabla adjunta con los valores S2(n, 2).

Recordemos que el algoritmo debe probar todas las particiones ubicando las coaristas en los lados derecho e izquierdo según los dos subconjuntos de cada partición. En aquel ejemplo sólo había que ejecutar la primera partición pues el grafo era planar y encontró una posibilidad de ubicación con la primera partición. Aún así la ejecución llevó un tiempo de 88 ms, pero pudo hacerse con un número de iteraciones que no superaba las 10000 que por defecto se impone para los algoritmos.

Cuando un grafo no es planar el algoritmo debe recorrer todas las particiones para asegurar que no hay ninguna posibilidad de ubicar las coaristas. El problema puede llegar a ser intratable con grafos no muy grandes. En la tabla adjunta vemos las particiones parciales hasta n=25 donde ya superan los 16 millones de particiones.

En en la Figura vemos el grafo de Johnson 5,2 que podemos obtener en la sección de generación, con el mismo número de 30 aristas que el dodecaédrico del apartado anterior aunque con la mitad de nodos (10). En este caso es un grafo no planar.

Podemos estar seguros que no es planar pues si activamos la opción usar test planar que podemos ver entre las opciones de isGraphPlanarTremaux() de la Figura, resultará que no necesitará ejecutar el árbol de Trémaux pues será verdadero al cumplirse la segunda condición de no planaridad que vimos en el tema anterior, devolviendo un aviso como el siguiente: Note: Non planar ⇒ Edges > 3 × Vertices - 6 ⇒ 30>3×10-6 ⇒ 30 > 24.

Pero vamos a usar isGraphPlanarTremaux() sin ese test de no planaridad, forzando a encontrar un árbol de Trémaux, para lo cual hemos de imponer un máximo de 2100000 iteraciones. Obtenemos este resultado usando "ciclo" en la opción usar Hamiltoniano:

Time: 2704 ms
Is graph planar Trémaux: {
"planar":false,
"useTestPlanar":false,
"useHamiltonian":"cycle",
"left":[[2,0,2,0,0],[8,4,7,5,0],[8,6,7,4,0],[8,3,7,3,0],[9,3,8,3,0],[9,2,8,2,0],[5,2,9,2,0],[5,0,9,0,0]],
"right":[[3,0,3,0,0],[6,0,4,0,0],[3,1,3,1,0],[9,7,8,6,0],[5,7,9,6,0],[5,4,9,5,0],[4,0,5,0,0]],
"outer":[],
"none":[[4,1,5,1,0],[7,2,6,2,0],[9,6,8,4,0],[7,1,6,1,0],[5,6,9,4,0],[8,1,7,1,0]],
"partition":[[0,1,2,3,5,6,8,9,10,11,12,13,14,15,16,17,18,19,20],[4,7]],
"relocated":[1,3,5,8,9,11,12,13,14,16,17],
"numCoedges":21,
"totalPartitions":1048575,
"numPartition":73728,
"runnedPartitions":1048575,
"totalRelocated":1047911,
"root":0,
"reverse":false,
"visited":[0,1,2,3,6,4,7,8,9,5],
"path":[[0,1],[1,2],[2,3],[3,6],[4,6],[4,7],[7,8],[8,9],[5,9]],
"branches":[[0,1,2,3,6,4,7,8,9,5]],
"coedges":[[2,0,2,0,0],[3,1,3,1,0],[8,4,7,5,0],[9,7,8,6,0],[3,0,3,0,0],[5,7,9,6,0],[8,6,7,4,0],[6,0,4,0,0],[4,1,5,1,0],[7,2,6,2,0],[8,3,7,3,0],[5,4,9,5,0],[9,6,8,4,0],[4,0,5,0,0],[7,1,6,1,0],[9,3,8,3,0],[5,6,9,4,0],[8,1,7,1,0],[9,2,8,2,0],[5,2,9,2,0],[5,0,9,0,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[21],
"warnings":[
    "Note: a Hamiltonian cycle was found"
]}

Vemos que ahora el algoritmo necesitó 2704 ms frente a los 88 ms del ejemplo anterior. Y que necesitamos un máximo de iteraciones que al menos duplique el número de particiones necesarias, pues en este caso tenemos que se generan 21 coaristas al tronco, como puede observarse en "numCoedgesToTrunk":[21] con un total de S2(21, 2) = 1048575 particiones, que observamos también en la tabla más arriba. Con "runnedPartitions":1048575 vemos que se ejecutaron todas, aunque el resultado que se devuelve es la partición "numPartition":852992, que es la que menos coaristas no pudo ubicar.

En la Figura vemos el árbol de Trémaux observando la gran cantidad de coaristas que no pudo ubicar. Recuerde que para que esta imagen no sea muy grande hemos quitado previamente los valores de los nodos del grafo de la Figura, imponiendo un radio de los nodos igual a 2 y en el ajuste planar evitamos las etiquetas de aristas, algo que ya explicamos antes con más detalle.

Resumimos que este algoritmo isGraphPlanarTremaux() que intenta saber si un grafo es plano a partir de ubicar las coaristas en el árbol de Trémaux empieza a tener problemas con grafos cuyos árboles originan muchas coaristas, especialmente cuando el grafo no es planar.

Ubicando coaristas exteriores ("outer") en el árbol Trémaux

En la Figura vemos un grafo planar al que le aplicamos isGraphPlanarTremaux() usando un camino Hamiltoniano ("path"), obteniéndose el siguiente resultado, donde observamos el campo "outer":[[6,3,5,1,0,"R"]], que es una alternativa que en ciertos casos nos permite ubicar una coarista exterior, en este caso marcada con una "R" de "right" que explicaremos después:

Time: 1 ms
Is graph planar Trémaux: {
"planar":true,
"useTestPlanar":true,
"useHamiltonian":"path",
"left":[[5,1,2,0,0],[4,1,4,0,0],[6,1,5,0,0]],
"right":[[6,2,5,3,0],[0,2,6,3,0],[0,5,6,2,0],[0,3,6,1,0]],
"outer":[[6,3,5,1,0,"R"]],
"none":[],
"partition":[[0,4,5,6,7],[1,2,3]],
"relocated":[5,6],
"numCoedges":8,
"totalPartitions":127,
"numPartition":112,
"runnedPartitions":112,
"totalRelocated":104,
"root":1,
"reverse":false,
"visited":[1,3,5,2,4,6,0],
"path":[[1,3],[3,5],[2,5],[2,4],[4,6],[0,6]],
"branches":[[1,3,5,2,4,6,0]],
"coedges":[[5,1,2,0,0],[6,2,5,3,0],[0,2,6,3,0],[0,5,6,2,0],[4,1,4,0,0],[6,3,5,1,0],[0,3,6,1,0],[6,1,5,0,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[8],
"warnings":[
    "Note: a Hamiltonian path was found"
]}

En la Figura vemos el árbol Trémaux con la coarista exterior 6-3 en color verde que se corresponde con el campo "outer":[[6,3,5,1,0,"R"]] que vemos en el resultado. La aplicación diferencia esa coarista exterior aunque con el ajuste a planar la aplicación no es capaz de dibujarla adecuadamente.

La aplicación permite editar el SVG del grafo con el botón ajustando manualmente esa coarista exterior en el editor SVG como vemos en la siguiente imagen de la Figura, observando que la coarista 6-3 sale del nodo 6 de la parte superior izquierda del árbol y entra al nodo 3 por la parte inferior derecha, por eso ponemos una "R" de "right" en el campo "outer":[[6,3,5,1,0,"R"]].

Veáse que esto es posible pues los nodos por encima del 6, en este caso sólo el 0, no tienen coaristas izquierda y que por el otro lado los nodos por debajo del 3, en este caso sólo el 1, no tienen coaristas derecha. Así que hay un hueco para ubicar una coarista exterior. En otros casos podría darse al revés, es decir, una coarista exterior izquierda, pero no ambas al mismo tiempo.

La arista 6-3 de la Figura no puede dibujarse en SVG con una cuadrática o cúbica. Se necesitan al menos tres cuadráticas y/o cúbicas seguidas para conseguirlo (verlo en este SVG usando 1 cúbica y 2 cuadráticas). Y con rectas la aplicación de grafos no permite sino dos puntos de cambio de dirección, pero para la línea 6-3 necesitamos 4 puntos de cambio de dirección.

...
"partition":[[0,4,5,6,7],[1,2,3]],
"relocated":[5,6],
"numCoedges":8,
"totalPartitions":127,
"numPartition":112,
"runnedPartitions":112,
"totalRelocated":104,
...
"numCoedgesToTrunk":[8],
...

En el resultado vemos en el campo "numCoedgesToTrunk":[8] que hay 8 coaristas al tronco lo que ocasiona un total de particiones "totalPartitions":127, pero que tuvo que ejecutar hasta la 112 "partition":[[0,4,5,6,7],[1,2,3]], relocalizando las coaristas "relocated":[5,6] que se corresponden con las coaristas 6-3 y 0-3 que pasó de la izquierda a la derecha donde 6-3 sólo pudo ubicarse exterior "outer":[[6,3,5,1,0,"L"]].

Ubicando ramas con coaristas simples en el árbol Trémaux

El grafo de la Figura es claramente planar. El grafo es Hamiltoniano y el resultado del árbol de Trémaux es que es planar, pudiendo observar en la imagen tremaux-planar-4-a.png que no contiene ramas, pues todos sus nodos están en el tronco del árbol.

Ya vimos más arriba en la Figura un árbol Trémaux con una rama sin coaristas. Vamos ahora a ejecutar el algoritmo isGraphPlanarTremaux() con el grafo de la Figura sin usar Hamiltoniano, obteniéndose el siguiente resultado, observando que no pudo ubicar la arista 3-8:

Time: 1 ms
Is graph planar Trémaux: {
"planar":true,
"useTestPlanar":true,
"useHamiltonian":"none",
"left":[[1,4,4,3,2],[2,5,2,1,1],[4,0,3,0,0]],
"right":[[3,7,5,2,0]],
"outer":[[6,5,4,1,0,"R"]],
"none":[],
"partition":[[0,1,2,4],[3]],
"relocated":[4],
"numCoedges":5,
"totalPartitions":15,
"numPartition":2,
"runnedPartitions":2,
"totalRelocated":2,
"root":0,
"reverse":false,
"visited":[0,5,7,4,6,3,1,2],
"path":[[0,5],[5,7],[7,4],[4,6],[6,3],[6,1],[7,2]],
"branches":[[0,5,7,4,6,3],[7,2],[6,1]],
"coedges":[[1,4,4,3,2],[2,5,2,1,1],[4,0,3,0,0],[3,7,5,2,0],[6,5,4,1,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[3,1,1],
"warnings":[
    "Note: branch '[7,2]' has one simple coedge",
    "Note: branch '[6,1]' has one simple coedge"
]}

Vemos en "branches" [[0,5,7,4,6,3],[7,2],[6,1]] donde el primer array [0,5,7,4,6,3] es el tronco y luego vienen dos ramas [7,2] y [6,1]. En los avisos "Warnings" vemos que ambas ramas tiene una única coarista simple. Entendemos esto con el árbol de Trémaux a continuación.

La aplicación ubica las 2 ramas a la izquierda del tronco con nodos 1 y 2 con fondo rosado y sus coaristas 1-4 y 2-5 son de color magenta que parten de las las ramas [6,1] y [7,2] como se observa en la Figura sin que se crucen con otras coaristas. Se ubican esas ramas a la izquierda pues las coaristas 1-4 y 2-5 están ubicadas a la izquierda en el campo "left".

Una coarista simple es aquella que parte de un nodo de una rama y finaliza en un nodo del tronco distinto del nodo inicial del tronco donde se inicia la rama. Por ejemplo, para la coarista 1-4 vemos que parte del nodo 1 de la rama [6,1] y finaliza en el nodo 4 del tronco, distinto del nodo 6 que es donde se inicia esa rama.

Se observa también la coarista 6-5 en color verde que se ubicó en "outer", algo que ya explicamos en un apartado anterior, aunque esa coarista fue redibujada posteriormente de forma manual usando el editor SVG, pues como ya habíamos expuesto, la aplicación no es capaz de hacerlo (ver la imagen tremaux-planar-4-b.png tal como sale de la aplicación).

Vemos que la rama [6,1] tiene un camino 6-1, 1-4 con lo que podriamos sustituir ese camino por una única arista 6-4 sin que afecte a la planaridad, con lo que sería perfectamante ubicable a la izquierda del tronco. Por eso decimos que esta única coarista de la rama [6,1] es simple.

De la misma forma la rama [7,2] con los caminos 7-2, 2-5 sustituirse por un arista 7-5 y perfectamente ubicable a la derecha del tronco. Por eso decimos que esa rama [7,2] tiene también una única coarista simple.

Vemos que cuando hay una rama con una única coarista simple podemos ubicarla a la izquierda o derecha como si fuera una coarista que parte directamente del tronco. Cuando hay más de una coarista simple y que no sean cortas como veremos a continuación, entonces no podremos asegurar la correcta ubicación, como veremos en otro ejemplo más abajo.

Ubicando ramas con coaristas cortas en el árbol Trémaux

El grafo de la Figura es planar. Si usamos un ciclo Hamiltoniano comprobaremos en la imagen tremaux-planar-5-b.png como las coaristas se ubican correctamente. No vamos a usar un ciclo o camino Hamiltoniano para forzar la generación de ramas con coaristas cortas.

Time: 9 ms
Is graph planar Trémaux: {
"planar":true,
"useTestPlanar":true,
"useHamiltonian":"none",
"left":[[5,7,8,6,0],[5,8,8,5,0]],
"right":[[5,4,8,1,0]],
"outer":[],
"none":[],
"partition":[[0,1],[2]],
"relocated":[],
"numCoedges":3,
"totalPartitions":3,
"numPartition":1,
"runnedPartitions":1,
"totalRelocated":0,
"root":0,
"reverse":false,
"visited":[0,4,9,11,10,8,7,6,5,3,2,1],
"path":[[0,4],[4,9],[9,11],[11,10],[9,8],[8,7],[7,6],[6,5],[0,3],[3,2],[2,1]],
"branches":[[0,4,9,8,7,6,5],[9,11,10],[0,3,2,1]],
"coedges":[[5,7,8,6,0],[5,8,8,5,0],[5,4,8,1,0]],
"coedgesIgnored":[[10,9,2,2,1],[1,0,0,0,2],[2,0,0,0,2]],
"numCoedgesToTrunk":[3,0,0],
"warnings":[
    "Note: branch '[9,11,10]' has short coedges and will be ignored",
    "Note: branch '[0,3,2,1]' has short coedges and will be ignored"
]}

Una coarista corta es aquella que parte de un nodo de una rama y finaliza en el nodo inicial del tronco donde se inicia la rama. En la Figura vemos que la coarista 10-9 parte del nodo 10 de la rama [9,11,10] y finaliza en el nodo 9 del tronco que es donde se inicia esa rama. Con la siguiente rama [0,3,2,1] vemos que tiene 2 coaristas cortas que finalizan en el nodo 0 que es el inicial de esa rama.

Una rama con una o más coaristas cortas puede ubicarse en cualquiera de los dos lados sin que interfiera con el resto de ubicaciones de aristas. Es obvio ver que podemos reubicar y/o reducir el tamaño visual de todo el conjunto de la rama hasta el punto que nos permita pasar otras coaristas a su alrededor.

Ubicando ramas sin coaristas simples en el árbol Trémaux

El grafo bipartito completo B6,3 de la Figura no es planar, tal como nos dice el algoritmo isGraphPlanarTremaux() si activamos la opción usar test planar devolviendo el mensaje Non planar ⇒ There are no size 3 cycles and Edges > 2 × Vertices - 4 ⇒ 18>2×9-4 ⇒ 18 > 14, que es el tercer principio de no planaridad que vimos en el tema tema anterior.

Omitimos esa opción usar test planar y vamos a ver que sucede usando ciclo Hamiltoniano:

Time: 4 ms
Is graph planar Trémaux: {
"planar":false,
"useTestPlanar":false,
"useHamiltonian":"cycle",
"left":[[3,6,4,2,1],[4,6,4,2,2],[5,6,4,2,3],[7,0,4,1,0],[3,8,4,0,1],[4,8,4,0,2],[5,8,4,0,3]],
"right":[[2,8,5,0,0],[1,8,3,0,0]],
"outer":[],
"none":[[2,6,5,2,0]],
"partition":[[0,1,2,3,4,5,6,7,8],[9]],
"relocated":[4,5],
"numCoedges":10,
"totalPartitions":511,
"numPartition":1,
"runnedPartitions":511,
"totalRelocated":375,
"root":8,
"reverse":true,
"visited":[8,0,6,1,7,2,3,4,5],
"path":[[8,0],[0,6],[6,1],[1,7],[7,2],[7,3],[7,4],[7,5]],
"branches":[[8,0,6,1,7,2],[7,3],[7,4],[7,5]],
"coedges":[[3,6,4,2,1],[4,6,4,2,2],[5,6,4,2,3],[7,0,4,1,0],[1,8,3,0,0],[2,6,5,2,0],[3,8,4,0,1],[4,8,4,0,2],[5,8,4,0,3],[2,8,5,0,0]],
"coedgesIgnored":[],
"numCoedgesToTrunk":[4,2,2,2],
"warnings":[
    "Note: no Hamiltonian cycle was found, testing with Hamiltonian path",
    "Note: no Hamiltonian cycle or path was found, testing with DFS",
    "The result maybe inciert, because it was no possible find some root where
        all branches have at most one simple coedge, last test with root '8'"
]}

Vemos que no encontró un ciclo ni un camino Hamiltoniano, con lo que obtuvo un DFS que genera varias ramas con más de una coarista simple, con lo que no podemos asegurar la planaridad del grafo usando el árbol de Trémaux. El resultado lo advierte con este mensaje, exponiendo que intentó buscar en los DFS alternando con diferentes raíces, desde 0 hasta 8.

El resultado podría ser incierto, pues no fue posible encontrar
alguna raíz donde todas las ramas tengan como máximo una
coarista simple, el último test fue con raíz '8'

En la Figura vemos el árbol Tremáux al que hemos posicionado mejor las ramas, pues las originales que vemos en tremaux-planar-6-a.png resultan confusas. Vemos que cada una de las tres ramas no tiene una única coarista simple, o corta, o sin coaristas, con lo que el resultado podría ser incierto. Es obvio que en esa disposición aparte de 2-6 se cruzan coaristas de las ramas, con lo que es evidentemente no planar, pero esto el algoritmo no es capaz de determinarlo al no ser coaristas únicas simples.

Estos grafos que no tienen ciclos o caminos Hamiltonianos y los DFS producen ramas que tienen más de una coarista simple no pueden tratarse con este algoritmo.