Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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
1  
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
    
Sorry for the confusion--I've added some clarifications that hopefully address some of your concerns. Thanks. –  momeara Oct 3 '10 at 14:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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