Is finding graph minors without single node pinch points possible?

Posted by Alturis on Game Development See other posts from Game Development or by Alturis
Published on 2012-09-20T19:53:07Z Indexed on 2012/09/20 21:55 UTC
Read the original article Hit count: 388

Filed under:
|
|
|

Is it possible to robustly find all the graph minors within an arbitrary node graph where the pinch points are generally not single nodes? I have read some other posts on here about how to break up your graph into a Hamiltonian cycle and then from that find the graph minors but it seems to be such an algorithm would require that each "room" had "doorways" consisting of single nodes.

To explain a bit more a visual aid is necessary. Lets say the nodes below are an example of the typical node graph. What I am looking for is a way to automatically find the different colored regions of the graph (or graph minors)

Node Example

© Game Development or respective owner

Related posts about ai

Related posts about path-finding