Online talk: Johannes Carmesin

Monday, November 30, 3pm ET (8pm GMT, 9am Tue NZDT)
Johannes Carmesin, University of Birmingham
Matroids and embedding graphs in surfaces
Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, this problem would be NP-hard. Instead of minimum genus, here we use local planarity — and provide a polynomial algorithm.
Our embedding method is based on Whitney’s trick to use matroids to construct embeddings in the plane. Consequently we obtain a characterisation of the graphs admitting locally planar embeddings in surfaces in terms of a certain matroid being co-graphic.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.