- This event has passed.

# Johannes Carmesin, A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings

## May 12 Wednesday @ 5:00 PM - 6:00 PM KST

Zoom ID: 934 3222 0374 (ibsdimag)

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.