Events

DMS Combinatorics Seminar

Time: Sep 24, 2025 (02:00 PM)
Location: ZOOM

Details:

ellingham

Speaker: Mark Ellingham (Vanderbilt University)

Title: Maximum genus directed embeddings of digraphs

 

Abstract: In topological graph theory we often want to find embeddings of a given connected graph with minimum genus, so that the underlying compact surface of the embedding is as simple as possible.  If we restrict ourselves to cellular embeddings, where all faces are homeomorphic to disks, then it is also of interest to find embeddings with maximum genus.  For undirected graphs this is a very well-solved problem.  For digraphs we can consider directed embeddings, where each face is bounded by a directed walk in the digraph.  The maximum genus problem for digraphs is related to self-assembly problems for models of graphs built from DNA or polypeptides.  Previous work by other people determined the maximum genus for the very special case of regular tournaments, and in some cases of directed 4-regular graphs the maximum genus can be found using an algorithm for the representable delta-matroid parity problem.  We describe some recent work, joint with Joanna Ellis-Monaghan of the University of Amsterdam, where we have solved the maximum directed genus problem in some reasonably general situations.