Résumé : A cross-cap drawing of a graph G is a drawing on the sphere with g distinct points, called cross-caps, such that the drawing is an embedding except at the cross-caps, where edges cross properly. I will first outline a connection between cross-cap drawings and an algorithm coming from computational biology to compute the signed reversal distance between two permutations. Then I will explain how this connection can be leveraged to answer two computational problems on graphs embedded on surfaces. This is joint work with Alfredo Hubard and Arnaud de Mesmay.

 [Slides.pdf] [vidéo]

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr