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?

  • 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
    @Gerry Myerson I would even be happy to have a solution for the case where $p$ is in $V(G)$2012-01-20