Opened 10 years ago

Last modified 10 years ago

#7502 new Bugs

Planarity test runs in quadratic time on some graphs

Reported by: Jan Hązła <jan.hazla@…> 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)

quadratic.cpp (473 bytes ) - added by Jan Hązła <jan.hazla@…> 10 years ago.
Graph generator that breaks time complexity of planarity test.

Download all attachments as: .zip

Change History (2)

by Jan Hązła <jan.hazla@…>, 10 years ago

Attachment: quadratic.cpp added

Graph generator that breaks time complexity of planarity test.

comment:1 by Jeremiah Willcock, 10 years ago

You can also remove the last loop in the generator (the u = 0 one) and get the same behavior.

Last edited 10 years ago by Jeremiah Willcock (previous) (diff)
Note: See TracTickets for help on using tickets.