Canonical decompositions and algorithmic recognition of spatial graphs

DOI10.1017/S0013091524000087arXiv2105.06905OpenAlexW3160072699MaRDI QIDQ6367665FDOQ6367665

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

Publication date: 14 May 2021

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.

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)

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)