29
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice question ! \$\endgroup\$ – user9206 Jun 11 '15 at 8:19
  • \$\begingroup\$ It's great that this is a classic problem and there are still several possible approaches, including ones not used in code for usual purposes. \$\endgroup\$ – lirtosiast Jun 11 '15 at 19:53
  • \$\begingroup\$ A test case for a non-connected graph with one planar and one non-planar connected component would be good. \$\endgroup\$ – Peter Taylor Jun 13 '15 at 8:44
  • \$\begingroup\$ @PeterTaylor Sure, I'll add one. \$\endgroup\$ – isaacg Jun 13 '15 at 8:45
  • 5
    \$\begingroup\$ @RenaeLider Sorry, but I don't understand. The question has nothing to do with floating point numbers whatsoever - it doesn't even use numbers, really, just labels. \$\endgroup\$ – isaacg Jun 13 '15 at 9:26
14
\$\begingroup\$

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 K5 or K3,3 as a minor.

Here, K5 is the complete graph with 5 vertices, and K3,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 K5 or K3,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.

\$\endgroup\$
  • \$\begingroup\$ You could try and remove the named function using #0 which refers to the innermost pure function. \$\endgroup\$ – LegionMammal978 Jun 13 '15 at 13:29
  • \$\begingroup\$ @LegionMammal978 I know, but it doesn't really save anything, because then I need parentheses and also need to assign # to a variable g manually. \$\endgroup\$ – Martin Ender Jun 13 '15 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.