@techreport{bue-sto-14-2dmaps-tr,
   author = {Lucas Moutinho Bueno and Jorge Stolfi},
   title = {{3-Colored} Triangulation of {2D} Maps},
   month = jul,
   year = 2014,
   institution = {Institute of Computing, University of Campinas},
   number = {IC-14-10},
   note = {In English},
   pages = {19},
   abstract = {We describe an algorithm to triangulate a general map on an arbitrary surface in such way that the resulting triangulation is vertex-colorable with three colors. (Three-colorable triangulations can be efficiently represented and manipulated by the GEM data structure of Montagner and Stolfi.) The standard solution to this problem is the barycentric subdivision, which produces $4e - 2b$ triangles when applied to a map with $e$ edges, such that $b$ of them are border edges (adjacent to only one face). Our algorithm yields a subdivision with at most $2e - b + 2(2-\chi)$ triangles, where $\chi$ is the Euler Characteristic of the surface; or at most $2e - n - 2b + 4(2-\chi)$ triangles if all $n$ faces of the map have the same degree. Experiment results show that the resulting triangulations have, on the average, significantly fewer triangles than these upper bounds.}
}