Dessin planaire de
graphes de genre supérieur
Comme nous l'avons vu dans le cours INF562,
le dessin de graphes dans le plan est un problème qui a
attiré l'attention de nombreux chercheurs dans les trois
dernières decennies. Pour le cas des graphes planaires, de
très nombreuses solutions ont été
proposées: en cours on a vu la méthode de Tutte, les
méthodes spectrales, l'algorithme de Schnyder, ...
Mais in on dispose d'un graphe (supposons triangulé, dans notre
cas) qui n'est pas planaire, mais plongé dans une surface de
genre supérieur, que peut-on faire pour le représenter
dans le plan?
Une approche intuitive et simple à mettre en place consiste
à decouper le graphe le long de 2g cycles afin d'en obtenir un
schéma polyonal canonique (un ensemble d'aretes dont la
suppression rend le graphe homeomorphe à un disque topologique).
On obtient ainsi un graphe planaire avec un bord dont les aretes sont
partitionnées en 2g cotés. Il s'agit enfin de dessiner
dans le plan ce graphe, en identifiant ses cotes avec les segments d'un
polygone. Toutes ses étapes sont bien détaillées
dans [1].
Mot
clés: planar drawing, higher genus graphs.
Références:
[1] Christian
A. Duncan, Michael
T. Goodrich, Stephen
G. Kobourov, Planar
drawing of Higher Genus Graphs, Proc. of Graph Drawing. (online
version, arxiv)
|
|
Schémas polygonaux
canoniques pour des graphes de genre 1, 2 et 3
|
Après avoir trouvé
un schéma canonique polygonal (niveau 3 du projet), on le
modifie afin de s'assurer qu'il ne contient pas de chordes.
|
|
|
|
La dernière étape
de la méthode de dessin (niveau 1 du projet), consiste à
implementer une variante de l'algorithme de dessin de graphes planaires
basé sur les ordres canoniques.
Les sommets sont ajoutés de manière incrementale dans un
certain ordre, de manière que lors de l'insertion d'un nouveau
sommet v, la chaine polygonal
constituées de ses sommets voisins est totalement visible de v (ce qui garanti l'absence de
croisements).
|
Toutes ces images sont prises de l'article de Duncan et al.
mentionné ci-dessus [1].
Finalités
du projet:
Implementer (en s'appuyant sur Jcg) la méthode proposée
dans [1] pour le dessin planaire de graphes
de genre supérieur (on pourra se limiter au cas de triangulations).
Input: un graphe
triangulé de genre g (au debut on ne
considère que g=1), au format
.off, codé sous forme de demi-aretes (ou autre
représentation fournie par Jcg)
Niveau 1: implémenter la méthode décrite
dans [1] basée sur une variante des
ordres canoniques
(Remarque:
dans cette étape on suppose de connaitre déjà un schéma polygonal canonique
sans chordes: son calcul s'effectuera au Niveau 3)
Niveau 2: implémenter la méthode qui permet d'éliminer les chordes,
afin d'obtenir un schéma polygonal sans chordes (auquel on peut
appliquer la méthode précédente)
Niveau 3: calculer un
schéma (canonique polygonal) à l'aide de l'une des
méthodes mentionnées dans [1]
Facultatif (bonus): on considère le cas de graphes
(triangulés) de genre
g quelconque.