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?
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?
Let $G$ be any graph drawn with straight-line edges (and these edges do not pass through vertices). Let $p$ be a vertex of $G$.
Here is a polynomial-time algorithm to find a cycle which winds once around $p$. I'll assume $p$ is drawn at the origin. Let G' be the graph with:
We then try to find a shortest path from $(v,\theta)$ to $(v,\theta+2\pi)$, for each $(v,\theta)$ with $\theta< 2\pi$. The shortest cycle that winds around $p$ is the shortest such path, projected down onto $G$.