<p>the more general question is the connection between knot theory and graph theory. as one possible place to start there is a connection between the <a href="http://en.wikipedia.org/wiki/Jones_polynomial">Jones polynomial</a> (used to classify knots) and the <a href="http://en.wikipedia.org/wiki/Tutte_polynomial">Tutte polynomial</a> of planar graphs. ie in knot theory, the Tutte polynomial appears as the Jones polynomial of
an alternating knot. (so maybe there is some connection of knot theory to GI on planar graphs.)</p>

<p>see thms 7,8 in:</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.1214">Computing the Tutte Polynomial of a Graph and
the Jones Polynomial of an Alternating Link of
Moderate Size</a> Sekine, Imai, Tani</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.1740">THE JONES POLYNOMIAL AND GRAPHS ON SURFACES</a>
OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN,
AND NEAL W. STOLTZFUS</p>

CC BY-SA 3.0
2012-10-01T15:56:48.580Z
2012-10-01T16:04:00.117Z
2012-10-01T16:04:00.117Z
vzn
<p>One connection is that graph isomorphism and knot isomorphism are both special cases of 3-manifold homeomorphism. In the knot case, two knots are isomorphic if their complements (manifolds formed by deleting the points of the knot from 3-space) are homeomorphic.</p>

<p>And in the graph case it's possible to transform graphs into manifolds in such a way that the graphs are isomorphic if and only if the manifolds are homeomorphic. I wrote a comment about this on a Google+ post last December, but unfortunately not on a post I can share. The construction is to start with a manifold for each vertex v, in the form of the complement in a 3-sphere of a bouquet of degree(v) loops (connected together at a common vertex). For each edge uv, connect the manifolds for u and v together by a <a href="http://en.wikipedia.org/wiki/Surgery_theory">surgery</a>, and link one loop from u and one loop from v across the surgery ball. Then every isomorphism of graphs lifts to a homeomorphism of the resulting manifold (this would be true even if we just used surgery on 3-spheres without the bouquets) and the bouquets prevent the manifold from having extra homeomorphisms that don't come from the graph.</p>

CC BY-SA 3.0
2012-10-02T00:40:53.423Z
2012-10-02T00:40:53.423Z
David Eppstein
<p><strong>GI</strong> and <a href="http://en.wikipedia.org/wiki/Knot_invariant">Knot Problem</a> both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to statistical physics have been explored via <a href="http://en.wikipedia.org/wiki/Knot_polynomial">knot polynomials</a>, are there similar results for $GI$?</p>

<p>It would be particularly helpful to know if there are any standard results/warnings/suggestions/comments before one start looking into $GI$ motivated by knot problem. Actually, I was wondering if its recommended to explore in this direction for my master's thesis. I am interested in quantum/classical approaches to $GI$ and algebraic problems. Any other suggestions are welcome.</p>

CC BY-SA 3.0
2012-10-01T15:34:24.833Z
from [mathworld isomorphic graphs](http://mathworld.wolfram.com/IsomorphicGraphs.html): "n some sense, graph isomorphism is easy in practice except for a set of pathologically difficult graphs that seem to cause all the problems. So, unlike knot theory, there have never been any significant pairs of graphs for which isomorphism was unresolved. ... Unfortunately, there is almost certainly no simple-to-calculate universal graph invariant, whether based on the graph spectrum or any other parameters of a graph (Royle 2004)."
vzn
CC BY-SA 3.0
2012-10-02T03:49:46.457Z
Apparently knot equivalence is _also_ easy in practice.
Jeffε
CC BY-SA 3.0
2012-10-08T04:54:50.060Z
I have poster similar question here http://physics.stackexchange.com/questions/39328/graph-invariants-and-statistical-mechanics also
DurgaDatta
CC BY-SA 3.0
2014-02-24T12:00:27.517Z
To my knowledge, there are no "pathologically difficult" knots that cause all of the problems. It would be very interesting to find a family of unknots that had poor running times on the various unknot recognition programs, either provably or just experimentally.
Sam Nead
<cc.complexity-theory><reference-request><graph-theory><graph-isomorphism><algebraic-topology>
Approaches to GI inspired by knot problem
DurgaDatta
# Approaches to GI inspired by knot problem

(Asked by: username_0 on 2012-10-01)

**GI** and [Knot Problem](http://en.wikipedia.org/wiki/Knot_invariant) both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to statistical physics have been explored via [knot polynomials](http://en.wikipedia.org/wiki/Knot_polynomial), are there similar results for $GI$?

It would be particularly helpful to know if there are any standard results/warnings/suggestions/comments before one start looking into $GI$ motivated by knot problem. Actually, I was wondering if its recommended to explore in this direction for my master's thesis. I am interested in quantum/classical approaches to $GI$ and algebraic problems. Any other suggestions are welcome.

**Tags:** cc.complexity-theory, reference-request, graph-theory, graph-isomorphism, algebraic-topology

> **Comments:**
> **username_1**: from [mathworld isomorphic graphs](http://mathworld.wolfram.com/IsomorphicGraphs.html): "n some sense, graph isomorphism is easy in practice except for a set of pathologically difficult graphs that seem to cause all the problems. So, unlike knot theory, there have never been any significant pairs of graphs for which isomorphism was unresolved. ... Unfortunately, there is almost certainly no simple-to-calculate universal graph invariant, whether based on the graph spectrum or any other parameters of a graph (Royle 2004)."  
> **username_2**: Apparently knot equivalence is _also_ easy in practice.  
> **username_0**: I have poster similar question here http://physics.stackexchange.com/questions/39328/graph-invariants-and-statistical-mechanics also  
> **username_3**: To my knowledge, there are no "pathologically difficult" knots that cause all of the problems. It would be very interesting to find a family of unknots that had poor running times on the various unknot recognition programs, either provably or just experimentally.  

---

## 2 answers

### Answer by username_4 on 2012-10-02. Score: 17 | Accepted answer

One connection is that graph isomorphism and knot isomorphism are both special cases of 3-manifold homeomorphism. In the knot case, two knots are isomorphic if their complements (manifolds formed by deleting the points of the knot from 3-space) are homeomorphic.

And in the graph case it's possible to transform graphs into manifolds in such a way that the graphs are isomorphic if and only if the manifolds are homeomorphic. I wrote a comment about this on a Google+ post last December, but unfortunately not on a post I can share. The construction is to start with a manifold for each vertex v, in the form of the complement in a 3-sphere of a bouquet of degree(v) loops (connected together at a common vertex). For each edge uv, connect the manifolds for u and v together by a [surgery](http://en.wikipedia.org/wiki/Surgery_theory), and link one loop from u and one loop from v across the surgery ball. Then every isomorphism of graphs lifts to a homeomorphism of the resulting manifold (this would be true even if we just used surgery on 3-spheres without the bouquets) and the bouquets prevent the manifold from having extra homeomorphisms that don't come from the graph.


---

### Answer by username_1 on 2012-10-01. Score: 7

the more general question is the connection between knot theory and graph theory. as one possible place to start there is a connection between the [Jones polynomial](http://en.wikipedia.org/wiki/Jones_polynomial) (used to classify knots) and the [Tutte polynomial](http://en.wikipedia.org/wiki/Tutte_polynomial) of planar graphs. ie in knot theory, the Tutte polynomial appears as the Jones polynomial of
an alternating knot. (so maybe there is some connection of knot theory to GI on planar graphs.)

see thms 7,8 in:

[Computing the Tutte Polynomial of a Graph and
the Jones Polynomial of an Alternating Link of
Moderate Size](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.1214) Sekine, Imai, Tani

[THE JONES POLYNOMIAL AND GRAPHS ON SURFACES](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.1740)
OLIVER T. DASBACH, DAVID FUTER, EFSTRATIA KALFAGIANNI, XIAO-SONG LIN,
AND NEAL W. STOLTZFUS


---

