Mixing
Finding “holes†in planar graphs
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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
graph-theory algorithms planar-graph
asked Jul 26 at 23:53
Tomer
111
add a comment |Â
up vote
1
down vote
favorite
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
graph-theory algorithms planar-graph
asked Jul 26 at 23:53
Tomer
111
1
Not to be pedantic, but it seems you're talking about a plane graph rather than a planar graph. In a planar graph, there's no way to distinguish between the inside and the outside of the circuit, is there? In any event, you seem to be considering a fixed embedding. Perhaps this will help you find some relevant material.
– saulspatz
Jul 27 at 0:03
Thanks @saulspatz , you're right, I mean a plane graph.
– Tomer
Jul 27 at 0:06
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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
graph-theory algorithms planar-graph
asked Jul 26 at 23:53
Tomer
111
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
graph-theory algorithms planar-graph
asked Jul 26 at 23:53
Tomer
111
asked Jul 26 at 23:53
Tomer
111
asked Jul 26 at 23:53
Tomer
111
asked Jul 26 at 23:53
Tomer
111
111
1
Not to be pedantic, but it seems you're talking about a plane graph rather than a planar graph. In a planar graph, there's no way to distinguish between the inside and the outside of the circuit, is there? In any event, you seem to be considering a fixed embedding. Perhaps this will help you find some relevant material.
– saulspatz
Jul 27 at 0:03
Thanks @saulspatz , you're right, I mean a plane graph.
– Tomer
Jul 27 at 0:06
add a comment |Â
1
Not to be pedantic, but it seems you're talking about a plane graph rather than a planar graph. In a planar graph, there's no way to distinguish between the inside and the outside of the circuit, is there? In any event, you seem to be considering a fixed embedding. Perhaps this will help you find some relevant material.
– saulspatz
Jul 27 at 0:03
Thanks @saulspatz , you're right, I mean a plane graph.
– Tomer
Jul 27 at 0:06
1
1
Not to be pedantic, but it seems you're talking about a plane graph rather than a planar graph. In a planar graph, there's no way to distinguish between the inside and the outside of the circuit, is there? In any event, you seem to be considering a fixed embedding. Perhaps this will help you find some relevant material.
– saulspatz
Jul 27 at 0:03
Not to be pedantic, but it seems you're talking about a plane graph rather than a planar graph. In a planar graph, there's no way to distinguish between the inside and the outside of the circuit, is there? In any event, you seem to be considering a fixed embedding. Perhaps this will help you find some relevant material.
– saulspatz
Jul 27 at 0:03
Thanks @saulspatz , you're right, I mean a plane graph.
– Tomer
Jul 27 at 0:06
Thanks @saulspatz , you're right, I mean a plane graph.
– Tomer
Jul 27 at 0:06
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
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'$.
answered Jul 28 at 0:32
Zach Langley
775919
You're absolutely right... thank you very much!
– Tomer
Jul 28 at 13:02
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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'$.
answered Jul 28 at 0:32
Zach Langley
775919
You're absolutely right... thank you very much!
– Tomer
Jul 28 at 13:02
add a comment |Â
up vote
1
down vote
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'$.
answered Jul 28 at 0:32
Zach Langley
775919
You're absolutely right... thank you very much!
– Tomer
Jul 28 at 13:02
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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'$.
answered Jul 28 at 0:32
Zach Langley
775919
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'$.
answered Jul 28 at 0:32
Zach Langley
775919
answered Jul 28 at 0:32
Zach Langley
775919
answered Jul 28 at 0:32
Zach Langley
775919
answered Jul 28 at 0:32
Zach Langley
775919
775919
You're absolutely right... thank you very much!
– Tomer
Jul 28 at 13:02
add a comment |Â
You're absolutely right... thank you very much!
– Tomer
Jul 28 at 13:02
You're absolutely right... thank you very much!
– Tomer
Jul 28 at 13:02
You're absolutely right... thank you very much!
– Tomer
Jul 28 at 13:02
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863933%2ffinding-holes-in-planar-graphs%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Not to be pedantic, but it seems you're talking about a plane graph rather than a planar graph. In a planar graph, there's no way to distinguish between the inside and the outside of the circuit, is there? In any event, you seem to be considering a fixed embedding. Perhaps this will help you find some relevant material.
– saulspatz
Jul 27 at 0:03
Thanks @saulspatz , you're right, I mean a plane graph.
– Tomer
Jul 27 at 0:06