Su tarea es determinar si un gráfico es plano.

Un gráfico es plano si puede incrustarse en el plano, o en otras palabras, si puede dibujarse sin bordes cruzados.

Entrada: Se le dará un gráfico no dirigido en su elección de los siguientes formatos:

• Lista de bordes, p. Ej. [(0, 1), (0, 2), (0, 3)]

• Mapa de adyacencia, p. Ej. {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

• Matriz adyacente, p. Ej. [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Los nombres de nodo pueden ser números, cadenas o similares, pero el formato elegido debe ser compatible con un gráfico arbitrario. No poner código en los nombres de nodo. No habrá self loops.

Elección estándar de entrada, incluidos STDIN, argumentos de línea de comando y argumentos de función.

Salida: debe devolver una salida específica para todos los gráficos planos y una salida específica diferente para todos los gráficos no planos.

Elección estándar de salida, incluido STDOUT, valor de retorno de función.

Ejemplos:

Plano:

[]
[(0,1), (0,2), (0,3), (0,4), (0,5), (0,6)]
[(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]
[(0,2), (0,3), (0,4), (0,5), (1,2), (1,3), (1,4), (1,5), (2,3),
 (2,5), (3,4), (4,5)]

No planas:

[(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]
[(0,3), (0,4), (0,5), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]
[(0,3), (0,4), (0,6), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (5,6), 
 (7,8), (8,9), (7,9)]

No se permite ninguna función que realice explícitamente pruebas de planaridad o que haga referencia específica a incrustaciones planas.

Este es el código de golf. Que gane el código más corto.

Mathematica, 201 bytes

f@g_:=EdgeCount@g<9||!(h=g~IsomorphicGraphQ~CompleteGraph@#&)@5&&!h@{3,3}&&And@@(f@EdgeDelete[g,#]&&f@EdgeContract[g,#]&/@EdgeList@g);And@@(f@Subgraph[g,#]&/@ConnectedComponents[g=Graph[#<->#2&@@@#]])&

Esto se evalúa como una función sin nombre, que toma una lista de bordes como

{{0, 3}, {0, 4}, {0, 5}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}

Este es un enfoque recursivo horriblemente ineficiente basado en el teorema de Wagner :

Un gráfico finito es plano si y solo si no tiene K ₅ o K _3,3 como menor.

Aquí, K ₅ es el gráfico completo con 5 vértices, y K _3,3 es el gráfico bipartito completo con 3 vértices en cada grupo. Un gráfico A es un menor del gráfico B si se puede obtener de B mediante una secuencia de eliminaciones de bordes y contracciones de bordes.

Por lo tanto, este código solo verifica si el gráfico es isomorfo a K ₅ o K _3,3 y, de lo contrario, se llama recursivamente una vez por cada posible eliminación o contracción de bordes.

El problema es que eliminar o contraer bordes en un componente de un gráfico no conectado nunca eliminará todos los vértices allí, por lo que nunca encontraremos los isomorfismos deseados. Por lo tanto, aplicamos esta búsqueda a cada componente conectado del gráfico de entrada por separado.

Esto funciona muy rápido para las entradas dadas, pero si agrega algunos bordes más, tomará rápidamente un tiempo catastrófico (y también requerirá mucha memoria).

Aquí hay una versión con sangría de f(la función sin nombre después de que solo genera un objeto gráfico a partir de la entrada:

f@g_ := 
  EdgeCount@g < 9 || 
  ! (h = g~IsomorphicGraphQ~CompleteGraph@# &)@5 && 
  ! h@{3, 3} &&
  And @@ (f@EdgeDelete[g, #] && f@EdgeContract[g, #] & /@ EdgeList@g)

Y esta es la función sin nombre que convierte la entrada en un gráfico y llama fa cada componente conectado:

And @@ (
  f @ Subgraph[g, #] & /@ ConnectedComponents[
    g=Graph[# <-> #2 & @@@ #]
  ]
)&

Puedo guardar un par de bytes cambiando la condición de terminación de EdgeCount@g<9a g==Graph@{}, pero eso aumentará significativamente el tiempo de ejecución. El segundo caso de prueba tarda 30 segundos, y el último aún no se ha completado.