How sure are you that the number of edges that would need to be removed for planarity is small?
One possible algorithm, assuming you have a planarity checker: -Construct a graph with all the nodes but no edges, and a set of all the edges. -While there are edges left in the set: -Add one to the graph, remove it from the set, check for planarity. -If still planar, keep it and move on. If not, remove it from the graph and move on.
The result will be a planar graph containing some subset of the edges, in O(83 * planarity check) time. No guarantee it's even close to a MINIMAL solution though.
Not very sure about the number of edges necessary. I tried arbitrarily nuking high-degree nodes to see if it would turn the indicator on - even after nuking all the degree 6-7 nodes (there are six of these, everything else is 3-5) it didn't become planar.
If the result *is* a low number of edges, then I could easily get a minimal solution by attacking the 2^n solution in the right order (basically binary by increasing number of ones) and stopping when I found a winner. Maybe I should just code that up and leave it running while I try to think of something better.
Another viable option - since I am not super-strict about being minimal - is to run your solution a few times but randomly ordering the edges, and take the best of those.
Comments 4
One possible algorithm, assuming you have a planarity checker:
-Construct a graph with all the nodes but no edges, and a set of all the edges.
-While there are edges left in the set:
-Add one to the graph, remove it from the set, check for planarity.
-If still planar, keep it and move on. If not, remove it from the graph and move on.
The result will be a planar graph containing some subset of the edges, in O(83 * planarity check) time. No guarantee it's even close to a MINIMAL solution though.
Reply
If the result *is* a low number of edges, then I could easily get a minimal solution by attacking the 2^n solution in the right order (basically binary by increasing number of ones) and stopping when I found a winner. Maybe I should just code that up and leave it running while I try to think of something better.
Another viable option - since I am not super-strict about being minimal - is to run your solution a few times but randomly ordering the edges, and take the best of those.
Reply
You could always code a planarity checker yourself and make it give you what you want. http://en.wikipedia.org/wiki/Planarity_testing
Reply
Reply
Leave a comment