Untangling Graphs on Surfaces

Éric Colin de Verdière, Vincent Despré, Loïc Dubois

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 drawin…