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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Andrew D. King
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 3, 2010 at 14:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .