Opened 10 years ago
Last modified 10 years ago
#7502 new Bugs
Planarity test runs in quadratic time on some graphs
Reported by: | Owned by: | Jeremiah Willcock | |
---|---|---|---|
Milestone: | To Be Determined | Component: | graph |
Version: | Boost 1.52.0 | Severity: | Problem |
Keywords: | Cc: |
Description
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.
Attachments (1)
Change History (2)
by , 10 years ago
Attachment: | quadratic.cpp added |
---|
comment:1 by , 10 years ago
You can also remove the last loop in the generator (the u = 0
one) and get the same behavior.
Graph generator that breaks time complexity of planarity test.