The background story is that I'm working on a computer-vision algorithm that analyzes patterns of movements of cells in time-lapse images of developing biological tissues. The mathematical problem is the following:
Assume a planar graph G=(V,E), and an induced sub-graph G'=(V',E'), where V' is partial to V and E' includes all the edges from E whose endpoints belong to V', and G' is guaranteed to be a single connected component.
The problem: find if there are vertices in V that don't belong to V', that reside within a circular path that travels only through vertices from V'. Simply put, if we draw the graph G and mark in yellow all the edges that belong to E' and all the vertices that belong to V', will we see unmarked vertices that are surrounded by yellow marked edges? Hope I made it clear enough...
I don't know whether this problem got any attention in the past - assuming a computationally fast solution is desired, and if it did - what would be good keywords for searching it.
I'll appreciate any suggestion!
Many thanks! Tomer
This can be easily inferred from the dual graph; since each vertex in the dual corresponds to a face in the primal, you are looking for the connected components of $G^* - E'$.