3
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Oct 2, 2010 at 23:06
  • $\begingroup$ 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 $\endgroup$
    – Tony Huynh
    Oct 2, 2010 at 23:30
  • $\begingroup$ Hi Tony, $G$ need not be planar. Here is an example where I believe a greedy approach fails. garin.med.unc.edu/~momeara/… $\endgroup$
    – momeara
    Oct 3, 2010 at 5:30
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Tony Huynh
    Oct 3, 2010 at 12:25
  • $\begingroup$ Sorry for the confusion--I've added some clarifications that hopefully address some of your concerns. Thanks. $\endgroup$
    – momeara
    Oct 3, 2010 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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