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\$
3
  • 1
    \$\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, 2015 at 19:53
  • \$\begingroup\$ Floating numbers are going to mess up some stuff here. \$\endgroup\$ Jun 13, 2015 at 9:10
  • 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, 2015 at 9:26

1 Answer 1

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\$
2
  • \$\begingroup\$ You could try and remove the named function using #0 which refers to the innermost pure function. \$\endgroup\$ Jun 13, 2015 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\$ Jun 13, 2015 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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