Canonical decompositions and algorithmic recognition of spatial graphs
| Autor: | Friedl, Stefan, Munser, Lars, Quintanilha, José Pedro, Rego, Yuri Santos |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Proceedings of the Edinburgh Mathematical Society 67 (2024) 388-430 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1017/S0013091524000087 |
| Popis: | 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. Comment: 57 pages, 16 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|