# find cycle around point

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?

-
Does "shortest" mean "with the fewest edges" or "with the least total length"? – mjqxxxx Jan 11 '12 at 14:35
If the graph isn't planar, it's not clear to me what the interior of a (self-intersecting) cycle is. – Gerry Myerson Jan 11 '12 at 16:09
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. – stefan Jan 20 '12 at 9:12
@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. – Gerry Myerson Jan 20 '12 at 12:05
@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 none – stefan Jan 20 '12 at 13:44

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:

• vertices $(v,\theta)$ for all vertices $v\neq p$ of $G$ and all $-|E(G)|\pi\leq\theta\leq |E(G)|\pi$ such that $v$ is at $r\cos\theta,r\sin\theta$ for some $r>0$.
• edges between $(v,\theta)$ and $(w,\theta')$ if $vw$ is an edge in $G$ and $|\theta-\theta'|\leq \pi$.

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$.

-
The problem statement does not assume $p$ is a vertex of $G$, but your solution does make that assumption. Does that create some difficulty? – Gerry Myerson Jan 20 '12 at 12:07
@Gerry Myerson I would even be happy to have a solution for the case where $p$ is in $V(G)$ – stefan Jan 20 '12 at 13:45