2
$\begingroup$

If I have a graph (not necessarily planar ) embedded in the plane and a point $p$ in the plane.

Can I somehow efficiently find the shortest cycle containing $p$ in its interior?

  • 1
    Does "shortest" mean "with the fewest edges" or "with the least total length"?2012-01-11
  • 1
    If the graph isn't planar, it's not clear to me what the interior of a (self-intersecting) cycle is.2012-01-11
  • 0
    Although I am not sure what the OP had in mind, I am interested in the cycle with minimum number of edges. @Gerry Myerson: Even if the graph is not planar, one has a notion of inside/outside using for example the winding number.2012-01-20
  • 0
    @stefan, sounds like a tough problem to me. Maybe Colin's answer works - I can't follow it. There might not even be a cycle containing $p$ in its interior.2012-01-20
  • 0
    @Gerry Myerson Yes there might not even be a cycle containing the point, I don't even know how to detect this, i.e. how to find any cycle containing $p$ or determine that there is none2012-01-20

1 Answers 1