Canonical decompositions and algorithmic recognition of spatial graphs

DOI10.1017/S0013091524000087MaRDI QIDQ6367665zbMATH OpenOpenAlexFDO

Authors Stefan Friedl, Lars Munser, José Pedro Quintanilha, Yuri Santos Rego

Publication date 14 May 2021

Full work available at URL https://doi.org/10.1017/s0013091524000087

Mathematics Subject Classification ID

Relations of low-dimensional topology with graph theory (57M15) Embeddings and immersions in PL-topology (57Q35) Regular neighborhoods in PL-topology (57Q40) Knot theory (57K10) Computational methods for problems pertaining to manifolds and cell complexes (57-08)

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.

Recommendations

• Spatial graphs, tangles and plane trees
• Spatial graphs and their isotopy classification
• Isotopy invariants of spatial graphs
• scientific article; zbMATH DE number 568839
• Invariants of spatial graphs coming from maximal trees

This page was built for publication: Canonical decompositions and algorithmic recognition of spatial graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367665)