A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The strong Hanani–Tutte theorem states that a graph admitting an independently even drawing in the plane must be planar. We present two extensions of the theorem to higher genus surfaces.
The genus $\mathrm{g}(G)$ of a graph $G$ is the minimum $g$ such that $G$ has an embedding on the orientable surface $M_g$ of genus $g$. The $\mathbb{Z}_2$-genus of a graph $G$, denoted by $g_0(G)$, is the minimum $g$ such that $G$ has an independently even drawing on the orientable surface of genus $g$. Clearly, every graph $G$ satisfies $\mathrm{g}_0(G)\le \mathrm{g}(G)$, and the strong Hanani–Tutte theorem states that $g_0(G)=0$ if and only if $g(G)=0$.
Although there exist graphs $G$, for which the value of $g(G)$ and $g_0(G)$ differ, several recent results suggest that these graph parameters are closely related. We provide further evidence of their similarity. Assuming the validity of an unpublished result by Robertson and Seymour, we show that $g(G)$ can be upper bounded by a function depending only on $g_0(G)$. This gives an approximate version of the Hanani–Tutte theorem on orientable surfaces conjectured by Schaefer and Stefankovic in 2013.
The second extension was conjectured by Repovs and A. Skopenkov in 1998 for trees, and by M. Skopenkov in 2003 for general graphs. We show that a possibly degenerate drawing of a tree on a closed surface is approximable by an embedding if and only if it is approximable by an independently even drawing. An analogous claim fails already for certain bad drawings of cycles in the plane. Nevertheless, we extend the result to general graphs by characterizing all such bad drawings.
Joint work with J. Kyncl.