0
$\begingroup$

This is a very basic question:

I don't see the following:

If I cut a surface with boundary along non-contracible cycles into components with genus zero, how can those components have an unbounded number of boundary cycles?

Thank you

  • 0
    How are you counting "boundary cycles" -- are these elements of some chain complex, or perhaps some kind of equivalence classes? Your question is too imprecise to have an answer. I suppose if your surface had an "unbounded number of boundary cycles" before you cut, it would have the same number afterwards. Does "unbounded" mean infinitely-many ?2011-11-23
  • 0
    I shouldn't read papers in areas in which I don't understand much: I would guess that unbounded means that it can be arbitrarily larger than the size of the input (its an algorithmic paper btw)2011-11-24
  • 0
    What is the input? Perhaps include a link to the paper you're reading.2011-11-24
  • 0
    http://www.cs.uiuc.edu/~jeffe/pubs/pdf/essential.pdf2011-11-24
  • 0
    What part of the paper are you referring to? Could you perhaps give a page and a line number?2011-11-24
  • 0
    Yes, sorry I was just about to write it. It is in the second paragraph of the Introduction. The authors write there: "Cutting a surface along non-contractible cycles decomposes the surface into components with genus zero, but those components may have an unbounded number of boundary cycles."2011-11-24

1 Answers 1

1

Okay, I see what you're referring to now. The authors are addressing the issue that if you only cut along non-contractible curves, you could be cutting off annuli. This happens if your curve is "parallel" to a boundary curve. So if you repeatedly cut along curves that are parrallel to the boundary, you'll create possibly an endless list of annuli without ever simplifying the original surface.

If $S_{g,b}$ is a connected surface of genus $g$ with $b$ boundary components, and you cut it along a curve $C$, there are two possibilities:

  • $S_{g,b}$ is cut into a connected surface of the form $S_{g-1,b+2}$
  • $S_{g,b}$ is cut into two connected surfaces of the form $S_{g_1,b_1}$ and $S_{g_2,b_2}$ where $g_1+g_2=g$, and $b_1+b_2 = b+2$.

In particular, if you cut along a boundary-parallel curve you cut $S_{g,b}$ into an $S_{0,2}$ and an $S_{g,b}$.

The first case is when the curve $C$ is non-separating, the 2nd case is when $C$ is separating.

  • 0
    Thank you: Do you understand why their algorithm takes both an abstract topological Surface M and a edge weighted cellularly embedded graph G? (On top of page 3) Apart from the fact that I don't know what an abstract topological Surface is, wouldn't G be enough?2011-11-24
  • 0
    The algorithm is for finding shortest essential curves in surfaces if I'm not mistaken. So you need the information of what the surface is, so that you can talk about how long a curve is.2011-11-24
  • 0
    Oh thats interesting. This was exactly my concern about how I determine the length of curves. But then I thought that this information is encoded in the weights of the graph. You're saying that this information is encoded in the abstract surface? Why do I need the edge weights? Could you provide me with a reference or a short explanation. Thank you so much2011-11-24
  • 0
    This paper uses conventions for surfaces that are fairly common in part of computer science. Basically you view the surface as a graph $G$ with certain 2-dimensional cells attached (topologist's terminology). So one combinatorial representation of the surface would be as a graph with a cyclic ordering of the edges incident to each vertex. In this paper they seem to like to use a hybrid description, keeping a picture of the actual (topological) surface in mind but also keeping the graph theorist's version in mind.2011-11-24
  • 0
    Ok thanks. The first part of your answer i understand, you refer to the 2-cell embedded graph encode with as a rotation system, right? Do you know why it is important that this graph is weighted? But what about the second part. How do you store the actual surface in a data structure. And I think later in the paper this is not used anymore.2011-11-24