@techreport{bue-sto-12-tri2d-tr,
  author = {Lucas Moutinho Bueno and Jorge Stolfi},
  title  =  {Subdivis{\~a}o  Econ{\^o}mica  3-Color{\'\i}vel  de uma Triangula{\c{c}}{\~a}o Esf{\'e}rica},
  month = dec,
  year = 2012,
  institution = {Institute of Computing, University of Campinas},
  number = {IC-12-29},
  language = {portuguese},
  pages = {11},
  abstract = {We describe an algorithm to subdivide an arbitrary triangulation of the sphere to produce a triangulation that 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 $6n$ triangles when applied to a triangulation with $n$ faces. Our algorithm eliminates all vertices of odd degree (which are the only obstacles to 3-colorability) in pairs, by bisecting only a few triangles at a time. While our algorithm has an exponential worst-case upper bound, it is expected to produce between $n$ and $2n$ triangles in typical cases.}
}