@article{bue-sto-16-2d-ijcga,
   author = {Lucas Moutinho Bueno and Jorge Stolfi},
   title = {{3-Colored} Triangulation of {2D} Maps},
   month = jul,
   year = 2016,
   month = jun,
   journal = {International Journal of Computational Geometry {\&} Applications},
   volume = {26},
   number = {2},
   pages = {111--133},
   doi = {10.1142/S0218195916500060},
   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-b+2(2-\chi)-n+(2(2-\chi)-b)/(D-2)$ triangles if all $n$ faces of the map have the same degree $D$. Experimental results show that the resulting triangulations have, on the average, significantly fewer triangles than these upper bounds.}
}