Testing graph isotopy on surfaces
From MaRDI portal
Abstract: We investigate the following problem: Given two embeddings G_1 and G_2 of the same abstract graph G on an orientable surface S, decide whether G_1 and G_2 are isotopic; in other words, whether there exists a continuous family of embeddings between G_1 and G_2. We provide efficient algorithms to solve this problem in two models. In the first model, the input consists of the arrangement of G_1 (resp., G_2) with a fixed graph cellularly embedded on S; our algorithm is linear in the input complexity, and thus, optimal. In the second model, G_1 and G_2 are piecewise-linear embeddings in the plane minus a finite set of points; our algorithm runs in O(n^{3/2}log n) time, where n is the complexity of the input. The graph isotopy problem is a natural variation of the homotopy problem for closed curves on surfaces and on the punctured plane, for which algorithms have been given by various authors; we use some of these algorithms as a subroutine. As a by-product, we reprove the following mathematical characterization, first observed by Ladegaillerie (1984): Two graph embeddings are isotopic if and only if they are homotopic and congruent by an oriented homeomorphism.
Recommendations
Cites work
- scientific article; zbMATH DE number 412172 (Why is no real title available?)
- scientific article; zbMATH DE number 2079390 (Why is no real title available?)
- scientific article; zbMATH DE number 1759777 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- A primer on mapping class groups
- Algorithms for Reporting and Counting Geometric Intersections
- Classes d'isotopie de plongements de 1-complexes dans les surfaces
- Computing homotopic shortest paths efficiently
- Computing homotopic shortest paths in the plane
- Computing minimum length paths of a given homotopy class
- Curves von 2-manifolds and isotopies
- Geometry and spectra of compact Riemann surfaces
- Graph-encoded maps
- Greedy optimal homotopy and homology generators
- Homotopic Arcs are Isotopic
- LATIN 2004: Theoretical Informatics
- Linear Isotopies in E 2
- Making curves minimally crossing by Reidemeister moves
- Mapping class groups are automatic
- Morphing planar graph drawings with bent edges
- On complexity of the word problem in braid groups and mapping class groups
- Optimal pants decompositions and shortest homotopic cycles on an orientable surface
- Optimal system of loops on an orientable surface
- Teilungen der Ebenen durch Geraden oder topologische Geraden
- Testing homotopy for paths in the plane
- Tightening nonsimple paths and cycles on surfaces
- Transforming curves on surfaces
- Transforming curves on surfaces redux
- Using generic programming for designing a data structure for polyhedral surfaces
Cited in
(12)- Recognizing weak embeddings of graphs
- Embedding graphs into two-dimensional simplicial complexes
- Topological laminations on surfaces
- Planar and Toroidal Morphs Made Easier
- An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
- Planar and toroidal morphs made easier
- scientific article; zbMATH DE number 7471699 (Why is no real title available?)
- Morphing graph drawings in the presence of point obstacles
- scientific article; zbMATH DE number 4163744 (Why is no real title available?)
- scientific article; zbMATH DE number 7662167 (Why is no real title available?)
- Tutte's barycenter method applied to isotopies
- Testing graph isotopies on surfaces
This page was built for publication: Testing graph isotopy on surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441582)
