A simple construction of high representativity triangulations Original Research Article

We show a construction of high representativity triangulations of compact surfaces, equivalently, triangulations without short non-contractible cycles, and give a polynomial-time algorithm to carry out the construction. We improve substantially the previously known lower bound for the representativity of such a triangulation. More precisely, we present an O(max(g2, n))-time algorithm that, for given g and n (g > 1 and n > cʹg log g) constructs an n-vertex triangulation of a genus g oriented surface without boundary such that the representativity of the triangulation is at least c√n/g √log g, where c, c′ are constants. We extend our result to nonorientable surfaces and surfaces with boundary. In the later case we replace the genus, g, of the surface with parameter g′ = g + d/2, where d is the number of boundary components.