# Compute number vertex disjoint cycles in graph surrounding a face

Hi all,

If anyone has insight into the following variant of the classic problem of packing vertex-disjoint cycle into graphs I would be interested.

Given a finite undirected graph $G$ embedded in $\mathbb{R}^2$ with a distinguished face $t$, compute the maximum number cycles in $G$ surrounding $t$ that are mutually vertex-disjoint.

In particular I am interested in properties of graphs that allow this quantity to be efficiently computed.

CLARIFICATIONS:

• The embedding of $G$ into $\mathbb{R}^2$ need not be a planar embedding.
• Every cycle in $G$ defines a face of an embedding of $G$.
• The interior of a face is the maximal subset of points $S\subset \mathbb{R}^2$ so any path from a point $s\in S$ to the point at infinity must cross the defining cycle of the face.
• A cycle $c$ in $G$ surrounds the face $t$ if the interior of $t$ is properly contained in the interior of the face defined by $c$ and $c$ does not intersect the boundary of the defining cycle of $t$.
• A surrounding cycle may wrap multiple times around $t$.

Here are two examples.

Under the assumption that your graph is 2-connected, I think you can just proceed greedily. In this case, we know that the boundary of each face of $G$ is in fact a cycle. So, in a sense that can be made precise, there is a cycle that is 'closest' to $t$. That is, just take the symmetric difference of all faces that are inside $t$ or incident with $t$. If we are trying to pack vertex disjoint cycles that contain $t$, we might as well include this 'closest' cycle. Now just recurse.
• I don't understand why you don't just say that the closest cycle to $t$ is $t$ itself. Or are you now dropping the assumption that the graph is 2-connected? – Andrew D. King Oct 2 '10 at 23:06
• Yes, $t$ is the closest cycle to itself and may be included in any maximum collection of disjoint cycles containing $t$. Once we agree that $t$ is in said collection, then we may as well include the 'next closest' cycle to $t$. This is the cycle that I'm talking about – Tony Huynh Oct 2 '10 at 23:30
• Hi Tony, $G$ need not be planar. Here is an example where I believe a greedy approach fails. garin.med.unc.edu/~momeara/… – momeara Oct 3 '10 at 5:30
• Hi momeara. I'll just remark that embedded in $\mathbb{R}^2$ often means planar, although it could mean drawn with edge crossings too. I'll stick with your terminology from now on. Even so, your example is a bit confusing, because it looks like we can only pack one cycle containing $t$. – Tony Huynh Oct 3 '10 at 12:25