[Boost-bugs] [Boost C++ Libraries] #7502: Planarity test runs in quadratic time on some graphs

Subject: [Boost-bugs] [Boost C++ Libraries] #7502: Planarity test runs in quadratic time on some graphs
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-10-13 16:45:19

#7502: Planarity test runs in quadratic time on some graphs
-----------------------------------------------+----------------------------
 Reporter:  Jan Hązła <jan.hazla@…>            |       Owner:  jewillco
     Type:  Bugs                               |      Status:  new     
Milestone:  To Be Determined                   |   Component:  graph   
  Version:  Boost 1.52.0                       |    Severity:  Problem 
 Keywords:                                     |  
-----------------------------------------------+----------------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/7502>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.