Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-06T22:47:02.718Z Has data issue: false hasContentIssue false

Canonical decompositions and algorithmic recognition of spatial graphs

Published online by Cambridge University Press:  14 March 2024

Stefan Friedl
Affiliation:
Fakultät für Mathematik, Universität Regensburg, Regensburg, Germany (stefan.friedl@ur.de; lars.munser@ur.de)
Lars Munser
Affiliation:
Fakultät für Mathematik, Universität Regensburg, Regensburg, Germany (stefan.friedl@ur.de; lars.munser@ur.de)
José Pedro Quintanilha
Affiliation:
Fakultät für Mathematik, Universität Bielefeld, Bielefeld, Germany (jquintan@math.uni-bielefeld.de)
Yuri Santos Rego
Affiliation:
Fakultät für Mathematik (IAG), Otto-von-Guericke-Universität Magdeburg, Magdeburg, Germany (yuri.santos@ovgu.de)
Rights & Permissions [Opens in a new window]

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 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.

Information

Type
Research Article
Copyright
© The Author(s), 2024. Published by Cambridge University Press on Behalf of The Edinburgh Mathematical Society
Figure 0

Figure 1.1. Two pairs of (decorated) spatial graphs with the same combinatorial structure, but a priori different topology.

Figure 1

Figure 3.1. The proof of associativity of the disjoint union.

Figure 2

Figure 3.2. A non-split spatial graph with disconnected support.

Figure 3

Figure 4.1. A PL annulus A ‘interpolating’ between γ and δ.

Figure 4

Figure 4.2. The 3-balls $\overline B$ and $\overline{B'}$.

Figure 5

Figure 4.3. The 3-ball $\overline{B'}$ and its Ψ-image $\widetilde B$.

Figure 6

Figure 4.4. Applying the Disc Theorem at the boundary to ambiently isotope $(\overline B \cap \overline{N_v}, D)$ onto $(\widetilde B \cap \overline{N_v}, \widetilde D)$ within (M, N).

Figure 7

Figure 4.5. The construction of Ψ.

Figure 8

Figure 4.6. An example of non-uniqueness of enclosing balls for a spatial graph with two distinguished vertices.

Figure 9

Figure 4.7 The realization of $\mathcal T= (T, I, J, L, (\Gamma_i)_{i \in I}, (v(l))_{l \in L})$.

Figure 10

Figure 4.8. The tree T, the sub-trees $T_{l_1}, T_{l_2}$ and their intersection $\dot T$. Large vertices represent elements of I, and small ones elements of J.

Figure 11

Figure 4.9. A spatial graph Γ whose vertices are cut in $\langle\Gamma \rangle$ but not in Γ.

Figure 12

Figure 4.10. Constructing T from T1 and T2. Large (resp. small) vertices represent elements of I1, I2 (resp. of J1, J2). Elements of I1, I2 whose corresponding blocks contain v are indicated. Here, v is not a cut vertex in Γ1, but it is in Γ2, where it corresponds to j2.

Figure 13

Figure 6.1. An oriented marked exterior of a spatial graph. Arrows indicate orientations.

Figure 14

Figure 6.2. Left: a $(2,4,1)$-model disc. Right: model disc for $P_\Gamma$ at the region of an isolated vertex v with colour $f(v)=1$. Arrows indicate orientations.

Figure 15

Figure 6.3. The marked exterior of a decorated spatial graph. Numbers indicate the colours of the vertices and edge.

Figure 16

Figure 6.4. A cut sphere S in Γ gives rise to a reducing disc D in $(X_\Gamma, P_\Gamma)$.