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.

Thanks in advance.