@techreport{TR-IC-14-10,
   number = {IC-14-10},
   author = {Lucas Moutinho Bueno and Jorge Stolfi},
   title = {3-Colored Triangulation of 2D Maps},
   month = {July},
   year = {2014},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 19 pages.
    \par\selectlanguage{english}\textbf{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.
  }
}