Skip to main content
2 broken links fixed
Source Link
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

In principle, there is an algorithm to tell if two graphs in $\mathbb{R}^3$ are isotopic, using Waldhausen's method of recognizing Haken 3-manifolds. The complement of a graph (obtained by removing an open regular neighborhood) has a natural pared manifold structure (also keeping track of meridians and longitudes on closed loop components). The pared manifold just means you have a collection of annuli in the boundary, and these annuli come from the regular neighborhoods of the edges of the graph. Waldhausen's theorem may be extended to determine the homeomorphism problem for pared manifolds - although it is not explicitly stated in this form, his method makes use of a more general concept of manifolds with boundary pattern, of which pared manifolds are a special case. It's not hard to see that two graphs are isotopic if and only if their corresponding pared manifolds are equivalent. However, this algorithm has not been fully implemented by computer.

One practical method is to use the program OrbOrb. This allows you to input a graph using a mouse, similar to SnappeaSnappea/SnapPy. If the graph complement is hyperbolic (in an appropriate sense, where the pared locus corresponds to rank one cusps, and the complementary regions corresponding to vertices of the graph are totally geodesic), then Orb will allow you to tell if two graph complements are isotopic (if it doesn't crash!). There is a relative JSJ decomposition, which allows one to break up a pared manifold into hyperbolic and Seifert pieces (such as the graph generalization of connect sum), but this has not been implemented as far as I know.

In principle, there is an algorithm to tell if two graphs in $\mathbb{R}^3$ are isotopic, using Waldhausen's method of recognizing Haken 3-manifolds. The complement of a graph (obtained by removing an open regular neighborhood) has a natural pared manifold structure (also keeping track of meridians and longitudes on closed loop components). The pared manifold just means you have a collection of annuli in the boundary, and these annuli come from the regular neighborhoods of the edges of the graph. Waldhausen's theorem may be extended to determine the homeomorphism problem for pared manifolds - although it is not explicitly stated in this form, his method makes use of a more general concept of manifolds with boundary pattern, of which pared manifolds are a special case. It's not hard to see that two graphs are isotopic if and only if their corresponding pared manifolds are equivalent. However, this algorithm has not been fully implemented by computer.

One practical method is to use the program Orb. This allows you to input a graph using a mouse, similar to Snappea/SnapPy. If the graph complement is hyperbolic (in an appropriate sense, where the pared locus corresponds to rank one cusps, and the complementary regions corresponding to vertices of the graph are totally geodesic), then Orb will allow you to tell if two graph complements are isotopic (if it doesn't crash!). There is a relative JSJ decomposition, which allows one to break up a pared manifold into hyperbolic and Seifert pieces (such as the graph generalization of connect sum), but this has not been implemented as far as I know.

In principle, there is an algorithm to tell if two graphs in $\mathbb{R}^3$ are isotopic, using Waldhausen's method of recognizing Haken 3-manifolds. The complement of a graph (obtained by removing an open regular neighborhood) has a natural pared manifold structure (also keeping track of meridians and longitudes on closed loop components). The pared manifold just means you have a collection of annuli in the boundary, and these annuli come from the regular neighborhoods of the edges of the graph. Waldhausen's theorem may be extended to determine the homeomorphism problem for pared manifolds - although it is not explicitly stated in this form, his method makes use of a more general concept of manifolds with boundary pattern, of which pared manifolds are a special case. It's not hard to see that two graphs are isotopic if and only if their corresponding pared manifolds are equivalent. However, this algorithm has not been fully implemented by computer.

One practical method is to use the program Orb. This allows you to input a graph using a mouse, similar to Snappea/SnapPy. If the graph complement is hyperbolic (in an appropriate sense, where the pared locus corresponds to rank one cusps, and the complementary regions corresponding to vertices of the graph are totally geodesic), then Orb will allow you to tell if two graph complements are isotopic (if it doesn't crash!). There is a relative JSJ decomposition, which allows one to break up a pared manifold into hyperbolic and Seifert pieces (such as the graph generalization of connect sum), but this has not been implemented as far as I know.

Source Link
Ian Agol
  • 68.9k
  • 3
  • 194
  • 358

In principle, there is an algorithm to tell if two graphs in $\mathbb{R}^3$ are isotopic, using Waldhausen's method of recognizing Haken 3-manifolds. The complement of a graph (obtained by removing an open regular neighborhood) has a natural pared manifold structure (also keeping track of meridians and longitudes on closed loop components). The pared manifold just means you have a collection of annuli in the boundary, and these annuli come from the regular neighborhoods of the edges of the graph. Waldhausen's theorem may be extended to determine the homeomorphism problem for pared manifolds - although it is not explicitly stated in this form, his method makes use of a more general concept of manifolds with boundary pattern, of which pared manifolds are a special case. It's not hard to see that two graphs are isotopic if and only if their corresponding pared manifolds are equivalent. However, this algorithm has not been fully implemented by computer.

One practical method is to use the program Orb. This allows you to input a graph using a mouse, similar to Snappea/SnapPy. If the graph complement is hyperbolic (in an appropriate sense, where the pared locus corresponds to rank one cusps, and the complementary regions corresponding to vertices of the graph are totally geodesic), then Orb will allow you to tell if two graph complements are isotopic (if it doesn't crash!). There is a relative JSJ decomposition, which allows one to break up a pared manifold into hyperbolic and Seifert pieces (such as the graph generalization of connect sum), but this has not been implemented as far as I know.