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.

Improve this question
$\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
    Commented 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.
    Commented 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
    Commented Oct 25, 2018 at 14:14

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ And of course Tutte used "bridge" with a completely different meaning. The joys of terminology. $\endgroup$
    – Chris Godsil
    Commented 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .