Planarity test runs in quadratic time on some graphs

[Jan Hązła <jan.hazla@…>]

The planarity test in the graph library (boyer_myrvold_planarity_test) seems to run in quadratic time for a certain class of graph.

I attached a program that demonstrates the problem. The program reads number N from stdin, generates a certain graph and runs the planarity test on it.

The graph is a bipartite graph K_{2,n} with some additional edges -- specifically, 2 "left" vertices of the bipartite graph are connected with an edge and n "right" vertices form a path. Note that the order of edge insertion matters -- the problem disappears if we change it.

Unfortunately I don't understand the planarity test enough to fix the problem. What I established (and what makes me believe it runs in quadratic time) is that for my graph in function walkdown (in planar_details/boyer_myrvold_impl.hpp; I understand the function is called once for each vertex) there is a loop on line 663 that is executed k times when the function was called for (k+1)-th time. This loop seems to have to do with Kuratowski subgraph detection, but I can't say anything more about it.

My configuration is Mac OS 10.8 with MacPorts, g++ 4.7 and boost 1.51. I also reproduced it on some Linux and Windows configurations.

[Jan Hązła <jan.hazla@…>]

Graph generator that breaks time complexity of planarity test.

[Jeremiah Willcock]

You can also remove the last loop in the generator (the u = 0 one) and get the same behavior.