2
\$\begingroup\$

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

Improve this question
\$\endgroup\$
5
  • 2
    \$\begingroup\$ This may be a better question for cs.stackexchange.com. I'm not sure if a game developer could answer this better. \$\endgroup\$
    – House
    Sep 20, 2012 at 20:34
  • \$\begingroup\$ I don't think the yellow nodes and green nodes would actually be separated. There's no "choke point" there. That would have to be a pretty smart algorithm to detect that difference. Perhaps you can explain more what you're trying to do? \$\endgroup\$
    – House
    Sep 20, 2012 at 22:17
  • 1
    \$\begingroup\$ Yeah, the definition of this is key. If you could define it as 'subgraphs with 2 or fewer shared nodes connecting it to the rest of the graph' then it wouldn't separate yellow and green. And if it was defined as 3 or fewer, some of those boundaries would move. I suspect this is not solely about graph theory because the definition of what makes up a pinch point seems to include the position of the nodes more than their topology and connections. \$\endgroup\$
    – Kylotan
    Sep 20, 2012 at 23:27
  • \$\begingroup\$ I suppose you could also trace the outer edge nodes and find the narrow spots. However, that's outside the bounds of graph theory. \$\endgroup\$
    – House
    Sep 21, 2012 at 2:55
  • \$\begingroup\$ A quick google suggests that you're using "graph minor" in an unusual way. The graph formed by the green and yellow nodes also is a graph minor. (Graph minors are similar to subsets). \$\endgroup\$
    – MSalters
    Sep 21, 2012 at 11:48

1 Answer 1

Reset to default
1
\$\begingroup\$

You're essentially looking for short interior paths.

I'm assuming that you have a planar embedding of your graph and can determine the circumference. An interior path is a path between nodes that doesn't contain edges on the circumference. The short paths you're looking for have the following properties:

  1. They're between two nodes that are both on the circumference, but not adjacent
  2. They're the shortest path between those two
  3. They're shorter than a non-interior path
  4. They're shorter than an adjacent path (one between one of the original nodes and a neighbor of the other)

Your "pinch points" are of course special cases where that length is zero.

Now, how would you determine such short interior paths? It's not horribly inefficient to create a NxN table listing the shortest interior paths between all N edge points. So, just get the local minima from that.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ "I'm assuming that you have a planar embedding of your graph and can determine the circumference" Not necessarily if I am understanding what you mean. If by circumference you mean identifying all out outer edge nodes and by planar embedding you mean a 2d only version of the graph where overlapping heights are extrapolated out into a separate area of the 2d graph then no. But your answer does give me some ideas to think about in terms of identifying such things. \$\endgroup\$
    – Alturis
    Sep 21, 2012 at 13:38
  • \$\begingroup\$ Your example shows a planar embedding. Essentially you have assigned X/Y coordinates to all nodes, and there are no crossing edges between the nodes. The circumference is just the set of edges on the outside, and the nodes between them. In your example, except for one node of each color, all nodes are on the circumference. \$\endgroup\$
    – MSalters
    Sep 21, 2012 at 14:36
  • \$\begingroup\$ Yes the example is as such but its a very simplified example for the purposes of this question. In actual fact the related project has overlapping areas along the vertical axis. I was thinking about a solution that didnt involve spacial knowledge only connectivity. \$\endgroup\$
    – Alturis
    Sep 23, 2012 at 15:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .