Short topological decompositions of non-orientable surfaces

1 : CNRS, LIGM

CNRS : UMR8049, Université Gustave Eiffel

Suppose that S is a surface and G is a graph embedded on S. In many applications, in algorithm design, geometry processing, or even just to represent the embedding, there is a basic task: to cut S into a single disk. When S is orientable, it has long been known how to compute a canonical cutting system that is also "short": each arc of the system runs along each edge of G at most a constant number of times.

In this talk we survey what is known about such cutting problems. We then explain how to obtain a short canonical system when S is non-orientable.