I am dealing with a particular problem where I want to analyze the properties of a graph of connected nodes. What I am looking for are weak points in the graph (i.e. places where I can remove the fewest number of nodes to break the graph). It won't be easy to explain in text for this question, but I shall try my best.
In my problem, I have a set of points where each point is connected to all neighboring points and is not connected to any non-neighboring points. Weight of the connections is not a factor. One way to perhaps think of this would be a set of pixels that make up an object.
In the above object, each x represents a node and every node is connected to every node that is above, below, left, right, or diagonal from it. What I would like is to analyze this graph such that I could identify that the 3rd node in the 3rd row is a weak point to the graph (remove it and access from the left side of the graph to the right side of the graph is broken). Furthermore, I would also like to identify that the two nodes in the second column could be removed which would break the entire graph in half.
I clicked through all the links on the Graph Theory page of Wikipedia, but the ones I could understand almost exclusively seemed to be about finding shortest paths and similar coverage problems. I didn't see anything about looking for potential weak points in the graph, but I'm sure there must be something. Does anyone out there know of a potential avenue of research or similar solved problems that I can look at?
Thanks in advance for your help.