Department of
Applied
Mathematics

A direct proof of the strong Hanani-Tutte theorem on the projective plane (J. Matousek prize talk)

Vojtěch Kaluža

Abstract

(joint work with É. Colin de Verdiere, P. Paták, Z. Patáková and M. Tancer)

The strong Hanani-Tutte theorem asserts that a graph is embeddable into the plane if and only if it can be drawn in the plane in a such way that every two independent edges cross an even number of times. In 2009 this theorem was extended to the real projective plane by Pelsmajer, Schaefer and Stasi. Beyond that the validity of the theorem on other surfaces is unknown.

We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof, our method is constructive and does not rely on the characterization of forbidden minors, which gives hope for an extension to other surfaces. Given a drawing of a graph on the real projective plane satisfying the assumptions of the strong Hanani-Tutte theorem, our method gradually transforms it into an embedding.

From a high-level point of view, our proof follows the strategy of the constructive proof of the strong Hanani-Tutte theorem in the plane by Pelsmajer, Schaefer and Štefankovič (2007). However, they method is not easy to extend to other surfaces, since a key step of their proof simply does not work on surfaces other than the plane. I will explain how we overcame this obstacle on the real projective plane.

In this talk I will recall the necessary background, give an overview of the strategy of our proof and focus only on its key steps.