Skip to main content
MathOverflow

Return to Answer

added 14 characters in body
Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.

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 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.

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.

Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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 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.