Soit G un graphe de taille n cellulairement plongé dans une surface S de genre g. Soit k le nombre minimal d’arêtes de tout cycle de G non-contractile dans S. Le nombre k, parfois appelé largeur en arêtes (edge-width), est un paramètre important du plongement de G; plus k est grand, plus G partage des propriétés avec les graphes planaires. Je décrirai un algorithme simple de complexité O(gnk) pour calculer un cycle non-contractile de taille minimale k dans G.
Travail réalisé en collaboration avec Sergio Cabello et Éric Colin de Verdière.
This document was translated from LATEX by HEVEA.