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 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