Ce papier propose une analogie discrète du théorème d'embedding barycentrique de Tutte pour les surfaces de courbure non-positive. Le théorème stipule que tout dessin homotopique à une immersion et avec chaque sommet en position convexe (analogie discrète d'être en position convexe) est une immersion faible (proche d'une immersion).
Les auteurs introduisent un modèle combinatoire pour les surfaces de courbure non-positive appelé "triangulations réduites". Ce modèle permet une représentation discrète des surfaces de courbure non-positive et capture de nombreuses propriétés des surfaces lisses.
Les contributions principales du papier sont les suivantes :
1. **Théorème discret de Tutte** : Les auteurs prouvent une analogie discrète du théorème de Tutte pour les surfaces de courbure non-positive, basée sur la notion de triangulations réduites. Ce théorème fournit une condition nécessaire et suffisante pour qu'un dessin soit homotopique à une immersion.
2. **Algorithme pour Rendre les Dessins Harmonieux** : Les auteurs fournissent un algorithme polynomial pour rendre un dessin d'entrée harmonieux sans augmenter la longueur de n'importe quel arc. Cet algorithme permet de construire de nombreux dessins harmonieux, qui sont une analogie discrète naturelle des dessins avec des sommets en position convexe.
3. **Extensions aux Surfaces à Bordure** : Les auteurs étendent leurs résultats aux surfaces à bordure en remplissant les composantes de bordure avec des surfaces (de genre), thereby étendant la triangulation réduite.
Les contributions du papier ont plusieurs implications :
- **Modèles discrets pour les Surfaces** : Le modèle discret proposé pour les surfaces de courbure non-positive peut être utilisé pour développer des algorithmes pour divers problèmes topologiques sur les surfaces.
- **Algorithmes de Dessin de Graphes** : Les algorithmes pour rendre les dessins harmonieux peuvent être utilisés pour améliorer les algorithmes de dessin de graphes, en particulier pour les surfaces de courbure non-positive.
- **Algorithmes de Morphing** : Les résultats peuvent être utilisés pour développer des algorithmes de morphing entre deux immersions du même graphe sur une surface de courbure non-positive.
Dans l'ensemble, le papier apporte une contribution significative au domaine du dessin de graphes et de la géométrie discrète en introduisant un nouveau modèle discret pour les surfaces et en prouvant une analogie discrète du théorème de Tutte.