Is My Graph Planar?

Question

Your task is to determine whether a graph is planar.

A graph is planar if it can embedded in the plane, or in other words if it can be drawn without any crossing edges.

Input: You will be given an undirected graph in your choice of the following formats:

• Edge list, e.g. [(0, 1), (0, 2), (0, 3)]

• Adjacency map, e.g. {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

• Adjacent matrix, e.g. [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Node names may be numbers, strings or similar, but your chosen format must be able to support an an arbitrary graph. No putting code in the node names. There will be no self loops.

Standard choice of input, including STDIN, command line arguments and function arguments.

Output: You should return a specific output for all planar graphs, and a different specific output for all nonplanar graphs.

Standard choice of output, including STDOUT, function return value.

Examples:

Planar:

[]
[(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)]

Nonplanar:

[(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)]

Any function which explicitly performs planarity testing or otherwise specifically references planar embeddings is disallowed.

This is code golf. May the shortest code win.

Answer 1

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&@@@#]])&

This evaluates to an unnamed function, which takes an edge list like

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

This is a horribly inefficient recursive approach based on Wagner's theorem:

A finite graph is planar if and only if it does not have K₅ or K_3,3 as a minor.

Here, K₅ is the complete graph with 5 vertices, and K_3,3 is the complete bipartite graph with 3 vertices in each group. A graph A is a minor of graph B if it can be obtained from B by a sequence of edge deletions and edge contractions.

So this code just checks if the graph is isomorphic to K₅ or K_3,3 and if not then it recursively calls itself once for every possible edge deletion or contraction.

The catch is that deleting or contracting edges in one component of an unconnected graph will never get rid of all the vertices there, so we'll never find the desired isomorphisms. Hence, we apply this search to each connected component of the input graph separately.

This works very fast for the given inputs, but if you add a few more edges it will quickly take catastrophically long (and take a lot of memory as well).

Here is an indented version of f (the unnamed function after it just generates a graph object from the input:

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

And this is the unnamed function which converts the input to a graph and calls f for each connected component:

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

I can save a couple of bytes by changing the termination condition from EdgeCount@g<9 to g==Graph@{}, but that will blow up the runtime significantly. The second test case then takes 30 seconds, and the last one hasn't completed yet.