Algorithmic recognition of spatial graphs
The preprint "Canonical decompositions and algorithmic recognition of spatial graphs" by Stefan Friedl, Lars Munser, José Pedro Quintanilha and Yuri Santos Rego has been recently uploaded to the arXiv!
Link to the paper: arXiv:2105.06905
Abstract:
We prove that there exists an algorithm for determining whether two piecewise-linear spatial graphs are isomorphic. In its most general form, our theorem applies to spatial graphs furnished with vertex colorings, edge colorings and/or edge orientations. We first show that spatial graphs admit canonical decompositions into blocks, that is, spatial graphs that are non-separable and have no cut vertices, in a suitable topological sense. Then we apply a result of Haken and Matveev in order to algorithmically distinguish these blocks.