1
$\begingroup$

Hey guys,

The following paper uses the term `bridge' in their definition of the Tutte polynomial:

Bennett Thompson, David J. Pearce, Craig Anslow, and Gary Haggard. Visualizing the computation tree of the tutte polynomial. In Proceedings of the 4th ACM sympo- sium on Software visualization, SoftVis ’08, pages 211–212, New York, NY, USA, 2008. ACM. Available from: http://doi.acm.org/10.1145/1409720.1409760, doi:http: //doi.acm.org/10.1145/1409720.1409760.

However, the Wiki page and other papers use the term `crossing'.

Are these the same thing or am I confusing them? What do you think?

Thank you.

$\endgroup$
3
  • $\begingroup$ Since the cited paper is behind a paywall it would be helpful if you reproduced the definition you want explained in your question. $\endgroup$
    – Aaron Dall
    Oct 25, 2018 at 13:22
  • $\begingroup$ @AaronDall I had a look at the paper and the definition given is: "a bridge is an edge whose removal disconnects two or more vertices (i.e. there is no longer a path between them)." It also looks like this link homepages.ecs.vuw.ac.nz/~djp/files/TPH-SIENZ07.pdf leads to a slightly expanded version of the paper. $\endgroup$
    – j.c.
    Oct 25, 2018 at 13:59
  • $\begingroup$ Thanks for the look-up @j.c. That's the definition used below in both Greg Kuperberg's answer and in mine. $\endgroup$
    – Aaron Dall
    Oct 25, 2018 at 14:14

2 Answers 2

5
$\begingroup$

The Wikipedia page for the Tutte polynmomial doesn't use the word crossing, it also uses the word bridge. In graph theory, a bridge of a connected graph is an edge that separates the graph into two components.

However, there is a relation between the Tutte polynomial and the Jones and HOMFLY polynomials. More precisely, the HOMFLY polynomial generalizes the Tutte polynomial for planar graph. A knot diagram has crossings, which means points where two arcs of the knot cross. A knot diagram also has bridges; a bridge is a maximal sequence of over-crossings along an arc of the diagram. So there is a little bit of collision of terminology, because crossings aren't bridges and because bridges for knots aren't the same as bridges for graphs.

$\endgroup$
1
  • 1
    $\begingroup$ And of course Tutte used "bridge" with a completely different meaning. The joys of terminology. $\endgroup$ Feb 6, 2011 at 15:53
1
$\begingroup$

I don't have access to the cited paper but if the term bridge is used as in the answer of @Greg Kuperberg (edit: and it is) then other synonyms from graph theory are isthmus, cut-edge, and cut-arc. An important feature of such a bridge $e$ of a (possibly disconnected) graph $G$ is that if $F$ is any spanning forest of $G$, then $e$ must be an edge in $F$. Equivalently, $e$ is not contained in any cycle of $G$. If $G$ is planar then the dual edge $e^*$ in the dual graph $G^*$ is a loop (a cycle of length one).

More generally, one can study the Tutte polynomial of a matroid. In this context an element $e$ that is in every basis of a given matroid is called an isthmus or a coloop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.