Bollobás–Riordan polynomial

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The Bollobás–Riordan polynomial is a generalization of the Tutte polynomial that applies to graphs drawn on surfaces, not just on a plane. There are two main versions.

- The 3-variable version works for graphs embedded on orientable surfaces. It is defined by summing over all spanning subgraphs, with each subgraph weighted by three variables that capture how the subgraph sits inside the surface.

- The 4-variable version extends this to ribbon graphs (graphs with a fixed cyclic order of edges around each vertex) and adds a fourth variable to record the number of boundary components of the subgraph.

Both polynomials were introduced by Béla Bollobás and Oliver Riordan in 2001 and 2002. When the surface is a plane, the 3-variable Bollobás–Riordan polynomial reduces to the Tutte polynomial. These polynomials are useful in topology and statistical physics for studying graph embeddings and related models.