Treffer: Testing Balanced Splitting Cycles in Complete Triangulations

Let T be a triangulation of an orientable surface Σ of genus g. A cycle C of T is splitting if it cuts Σ into two noncontractible parts Σ 1 and Σ 2 , with respective genus 0 < g 1 ≤ g 2. The splitting cycle C is called balanced if g 1 ≥ g 2 − 1. The complexity of computing a balanced splitting cycle in a given triangulation is open, but seems difficult even for complete triangulations. Our main result in this paper is to show that one can rule out in polynomial time the existence of a balanced splitting cycle when the triangulation is ε-far to have one. Implementing this algorithm, we show that large Ringel and Youngs triangulations (for instance on 22.363 vertices) have no balanced splitting cycle, the only limitation being the size of the input rather than the computation time.