Canonical decompositions and algorithmic recognition of spatial graphs

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 colourings, edge colourings and/or edge orientations. We first show that spatial graphs admit cano...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the Edinburgh Mathematical Society 2024-05, Vol.67 (2), p.388-430
Main Authors: Friedl, Stefan, Munser, Lars, Quintanilha, José Pedro, Santos Rego, Yuri
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Decomposition
Forests
Graph coloring
Graphs
Neighborhoods
Spheres
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 colourings, edge colourings and/or edge orientations. We first show that spatial graphs admit canonical decompositions into blocks, that is, spatial graphs that are non-split 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.
ISSN:0013-0915
1464-3839
DOI:10.1017/S0013091524000087