Can the genus of a graph be approximated?
Bojan Mohar (Simon Fraser University)
Abstract: The genus g(G) of a graph G is defined as the minimum genus of a surface in which G can be embedded (drawn without crossings). Thomassen proved that it is NP-hard to determine whether g(G) < k, when the graph G and an integer k are given to us as the input. Robertson and Seymour (and the speaker) proved that this problem is FPT (fixed-parameter tractable). However, it is wide open whether the value of g(G) can be approximated.
The speaker will give an overview of this problem, describe underlying conjectures, and present a complete solution for the case when the graph is dense. The solution uses Szemeredi Regularity Lemma and a result on the genus of quasi-random graphs.
This is joint work with Yifan Jing.
combinatorics
Audience: researchers in the topic
Comments: password 121323
Series comments: Check scmscomb.github.io/ for more information