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.

Dernière modification : Thursday 21 November 2024

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