Please join us for our next UVM Combinatorics Seminar:

Bi-Eulerian Embeddings of Dense Graphs and Digraphs

with Jo Ellis-Monaghan
University of Amsterdam

Wednesday, March 19th at 4:05 pm
Perkins Building, Room 200

Abstract: When can a graph or digraph be cellularly embedded in an orientable surface so that it has exactly two faces, each bounded by an Euler circuit? Is it possible to specify one of the Euler circuits in advance? When is it possible to specify an arbitrary circuit decomposition of the edges and complete it to an embedding with just one more face, noting that this face is then necessarily bounded by an Euler circuit?  Finding such a face achieves a maximum genus embedding having the circuits in a given decomposition as facial walks.

This leads more generally to the question of determining the maximum genus of an embedding relative to a circuit decomposition. Beyond topological graph theory, these questions arise in surprisingly diverse settings, including DNA self-assembly, Steiner triple systems, and latin squares.

We prove that if an Eulerian (di)graph is sufficiently dense, then it is indeed always possible to achieve these special embeddings of maximum orientable genus.

This is joint work with Mark Ellingham.