Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Does "shortest" mean "with the fewest edges" or "with the least total length"? –  mjqxxxx Jan 11 '12 at 14:35
1  
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
add comment

1 Answer

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.