  Consider a graph drawn on a surface (for example, the plane minus a finite
set of obstacle points), possibly with crossings. We provide an algorithm to
decide whether such a drawing can be untangled, namely, if one can slide the
vertices and edges of the graph on the surface (avoiding the obstacles) to
remove all crossings; in other words, whether the drawing is homotopic to an
embedding. While the problem boils down to planarity testing when the surface
is the sphere or the disk (or equivalently the plane without any obstacle), the
other cases have never been studied before, except when the input graph is a
cycle, in an abundant literature in topology and more recently by Despr\'e and
Lazarus [SoCG 2017, J. ACM 2019].
  Our algorithm runs in O(m + poly(g+b) n log n) time, where g >= 0 and b >= 0
are the genus and the number of boundary components of the input orientable
surface S, and n is the size of the input graph drawing, lying on some fixed
graph of size m cellularly embedded on S.
  We use various techniques from two-dimensional computational topology and
from the theory of hyperbolic surfaces. Most notably, we introduce reducing
triangulations, a novel discrete analog of hyperbolic surfaces in the spirit of
systems of quads by Lazarus and Rivaud [FOCS 2012] and Erickson and Whittlesey
[SODA 2013], which have the additional benefit that reduced paths are unique
and stable upon reversal; they are likely of independent interest. Tailored
data structures are needed to achieve certain homotopy tests efficiently on
these triangulations. As a key subroutine, we rely on an algorithm to test the
weak simplicity of a graph drawn on a surface by Akitaya, Fulek, and T\'oth
[SODA 2018, TALG 2019].
