Presented by: 
Arnaud de Mesmay, ENS, Paris
Date: 
Tue 26 Jun, 3:00 pm - 4:00 pm
Venue: 
Room 442, Building 67

In the study of graphs embedded on surfaces, the notion of graph isotopy is a natural variation of the well known homotopy of paths or cycles: We say that two graphs are isotopic if there exists a continuous deformation between them. In this work, we investigate the following problem: Given two embeddings of the same abstract graph on a surface, decide whether they are isotopic.
 
We provide efficient algorithms to solve this problem in two models. In the first one the embeddings are described by their arrangements with a cellularly embedded graph on the surface; in the second one they are piecewise-linear embeddings in the plane minus a finite set of points. The main tools we use are the existing algorithms to test homotopy, which we use as a subroutine, and hyperbolic geometry. As a by-product, we reprove the following mathematical characterization, first observed by Ladegaillerie: Two graph embeddings are isotopic if and only if they are homotopic and congruent by an oriented homeomorphism.
 
This is joint work with Éric Colin de Verdière.