View abstract

Session I.4 - Computational Geometry and Topology

Tuesday, June 13, 17:30 ~ 18:00

Short decompositions and joint crossings of embedded graphs on surfaces

Arnaud de Mesmay

CNRS, Université Gustave Eiffel, France   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

The joint crossing number of two graphs $G_1$ and $G_2$ embedded on a surface is the minimum number of crossings among all homeomorphic reembeddings of one of the graphs. Intuitively, it quantifies how much it would cost to decompose $G_1$, seen as a discrete metric for the surface, along a cutting graph whose shape is specified by $G_2$. An old conjecture of Negami states that this crossing number is always $O(|E(G_1) ||E(G_2) |)$, and it is still wide open, even in the case of one-vertex graphs, i.e., systems of loops.

In this talk,we will discuss this conjecture, its numerous connections with other problems, and survey recent progress, emphasizing recent work with Fuladi and Hubard in the non-orientable case.

Joint work with Niloufar Fuladi (Université Gustave Eiffel, France) and Alfredo Hubard (Université Gustave Eiffel, France).

View abstract PDF