A simple construction of high representativity triangulations (Q1367040)

The representability of a graph embedded in a surface is the length of the shortest noncontractible facial walk. Informally speaking, the concept measures how well the embedding approximates the surface. High representability suggests that the embedding is ``highly locally planar.'' This paper provides polynomial-time constructions of high representability triangulations of compact surfaces. The authors give improvements of the previously known lower bound for the representability of such triangulations. The results are extended to nonorientable surfaces and surfaces with boundary.