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

1

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

  • 0
    The problem statement does not assume $p$ is a vertex of $G$, but your solution does make that assumption. Does that create some difficulty?2012-01-20
  • 0
    @Gerry Myerson I would even be happy to have a solution for the case where $p$ is in $V(G)$2012-01-20