Testing graph isotopies on surfaces
Arnaud de Mesmay, Éric Colin de Verdière · 2012
We investigate the following problem: Given two embeddings G1 and G2 of the same abstract graph G on an orientable surface S, decide whether G1 and G2 are isotopic; in other words, whether there exists a continuous family of embeddings between G1 and G2. We provide efficient algorithms to solve this problem in two models. In the first model, the input consists of the arrangement of G1 (resp., G2) with a fixed graph cellularly embedded on S; our algorithm is linear in the input complexity, and thus, optimal. In the second model, G1 and G2 are piecewise-linear embeddings in the plane minus a finite set of points; our algorithm runs in O(n3/2log n) time, where n is the complexity of the input.