Atlantic Graph Theory Seminar: Iain Moffat (Royal Holloway, University of London)

Spanning Trees and Graphs Embedded in Surfaces

To what extent is a graph determined by the trees contained in it? That is, if we know the edge sets of each of the spanning trees (i.e., maximal acyclic subgraphs) in a connected graph, then do we know the graph itself? It only takes a little bit of thought to see that the answer is “no” (e.g., suppose the graph is a tree).  But this “no” is really a “more or less, yes”.   A classical result of Whitney states that we know the graph up to some simple moves.

In this talk we consider what changes if we ask this question not for graphs in the abstract, but graphs that are embedded on surfaces.  We shall see how this question brings together a seemingly disjoint collection of topics in mathematics and brings new approaches to topological graph theory.