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.