https://svn.boost.org/trac10/ticket/7502 <p> The planarity test in the graph library (boyer_myrvold_planarity_test) seems to run in quadratic time for a certain class of graph. </p> <p> 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. </p> <p> 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. </p> <p> 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. </p> <p> My configuration is Mac OS 10.8 with <a class="missing wiki">MacPorts</a>, g++ 4.7 and boost 1.51. I also reproduced it on some Linux and Windows configurations. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/7502 Trac 1.4.3 Jan Hązła <jan.hazla@…> Sat, 13 Oct 2012 16:46:18 GMT https://svn.boost.org/trac10/ticket/7502 https://svn.boost.org/trac10/ticket/7502 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">quadratic.cpp</span> </li> </ul> <p> Graph generator that breaks time complexity of planarity test. </p> Ticket Jeremiah Willcock Sat, 13 Oct 2012 19:52:39 GMT