¿Es este gráfico un gráfico plano o no?

Question

Llevo un tiempo intentando averiguar si este gráfico es plano o no y me he quedado corto a la hora de crear un dibujo plano del gráfico. Mi intuición me dice que no es plano, pero no puedo encontrar ningún subgrafo del grafo homeomorfo a K3, 3 (por el Teorema de Kuratowski). Cualquier ayuda sería muy apreciada. El gráfico se puede ver a continuación:

Answer 1

Aunque la pregunta ya ha sido contestada a fondo, aquí hay un enfoque inusual para comprobar si un gráfico es plano al que soy muy aficionado y que funciona bien aquí.

En primer lugar, observamos que hay un ciclo que pasa por todos $12$ vértices:

(Este método sólo garantiza resolver la cuestión en un sentido u otro si encontramos un ciclo de este tipo, aunque para un ciclo que sólo pasa por la mayoría de los vértices puede seguir siendo muy útil).

Ahora vuelve a dibujar la gráfica de manera que este ciclo se disponga en un círculo:

Si hay una incrustación plana del grafo, este círculo tiene que aparecer en alguna parte, por lo que las únicas opciones que quedan para dibujar el grafo son decidir, para cada arista no en el ciclo, si se dibujará como una cuerda dentro del círculo o fuera del círculo.

Pero las tres aristas resaltadas se cruzan entre sí. Independientemente de las opciones que elijas para ellas, o bien dos de ellas estarán en el interior (y se cruzan) o bien dos de ellas estarán en el exterior (y se cruzan). Por tanto, no hay incrustación plana.

(En general, una vez que se ha encontrado el ciclo hamiltoniano -si es que existe-, decidir si las aristas restantes pueden dibujarse sin cruzarse es sencillo. Empieza con una elección arbitraria y luego sólo tienes que asegurarte de que si una arista está en el interior, todas las aristas que cruza están en el exterior, y viceversa).

Answer 2

No es planar. Si eliminas el vértice $j$ y el borde $bf,$ lo que queda es homeomorfo a $K_{3,3}.$

Answer 3

Puede utilizar Algoritmo O(N) de Hopcroft y Tarjan de 1974 "efficient planarity Testing" para comprobar la planaridad. Se puede encontrar una explicación detallada en el Tesis "Prueba de planaridad por adición de trayectorias" .

Comience por realizar una búsqueda de profundidad en (cada componente biconectado del) gráfico:

A --> E --> D --> I --> G --> L --> A
                        |      \
                        |       --> C --> B --> D
                        |           |      \
                        |           |       --> F --> I
                        |           |            \
                        |           |             --> A
                        |            \
                        |             --> J --> D
                        |                  \
                        |                   --> E
                         \
                          --> K --> H --> E

A continuación, se divide (cada componente biconectado del) grafo en un ciclo y una jerarquía de cuerdas (cada una de ellas compuesta por cero o más aristas de árbol/adelante de la DFS y exactamente una arista de co-árbol/atrás de la DFS):

A --> E --> D --> I --> G --> L --> A

                              L --> C --> B --> F --> A

                                                F --> I

                                          B --> D

                                    C --> J --> E

                                          J --> D

                        G --> K --> H --> E

El método para elegir qué arista continúa un ciclo/acorde que se detalla en el documento/tesis vinculado, pero se puede resumir (brevemente) así:

• Cada acorde terminará en el ancestro más bajo alcanzable en el árbol DFS
• Si varias cuerdas pueden llegar a este ancestro, entonces se preferirá una en la que el subárbol DFS rooteado en ese vértice pueda llegar sólo a ese ancestro más bajo, en lugar de una cuerda que sólo pueda llegar a varios ancestros inferiores. Por lo tanto, hay dos caminos de ramificación del subárbol DFS rooteado en L que puede llegar al ancestro más bajo A pero el camino L --> C puede llegar a más de un ancestro de L (los antepasados A , E , D y I ) mientras que el subárbol que empieza por L --> A sólo puede alcanzar A es el camino preferido.
• Si todavía hay varias rutas con la misma preferencia, elija una de ellas.

A continuación, comenzando por el ciclo, se añaden sucesivamente cada uno de los acordes a la incrustación del grafo en el post-orden DFS:

Así que el ciclo A --> E --> D --> I --> G --> L --> A se incrusta primero y luego es bisecada por la cuerda L -> C --> B --> F --> A y luego F --> I en el interior de ese ciclo:

A --> E --> D --> I --> G --> L
^\                ^           |\
| \            __/            | |
|  \          /               | |
|   \----<-- F <-- B <-- C <-/  |
 \_____________________________/

A continuación, tratamos de incrustar B --> D y descubrimos que no se puede incrustar porque no hay ninguna cara que contenga los dos vértices B y D y se ha encontrado un menor no plano (en este caso, homeomorfo a k _(3,3) ).

A --> E --> D --> I --> G --> L
^\          ^     ^           |\
| \         |   _/            | |
|  \        |  /              | | 
|   \       \_/__             | |
|    \       /   \            | |
|     \-<-- F <-- B <-- C <--/  |
 \_____________________________/