Consider a simple planar 4-valent graph. I want to find out how to break it into two pieces by removing 4 edges, if such a way exists. Removing the four edges belonging to a single vertex doesn't count.
I know how to do this in O(v^4) operations, where v is the number
of vertices, specifically by trying each possible removal of 4 edges. Is there a method faster than O(v^4) for searching for a way to do this? I have a lot of graphs to work with. Thanks.