id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
7502,Planarity test runs in quadratic time on some graphs,Jan Hązła <jan.hazla@…>,Jeremiah Willcock,"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.
",Bugs,new,To Be Determined,graph,Boost 1.52.0,Problem,,,