Une implémentation python : construire un bon graphe planaire

On peut construire un graphe planaire d’étirement maximal 6 et de degré maximal 12

On donnes un nuage de point, et on souhaite construire un réseau à partir de celui-ci. Comment procéder ? On souhaite que le graphe soit planaire, c’est-à-dire sans croisement. Si on fait l’analogie avec des villes et des routes, cela veut dire qu’on ne veut pas de tunnel ou de pont. Mais ce n’est pas tout : il faut que tout le monde soit bien desservi, c’est-à-dire qu’on puisse aller d’un point à un autre sans parcourir une distance beaucoup plus grande que celle qu’on aurait parcouru à vol d’oiseau : on parle pour cela de l’étirement d’un graphe. Ce TP propose une construction qui garantit qu’on parcourra au plus une distance deux fois plus grande.

Une deuxième partie du TP, un peu plus ambitieuse, propose de construire un second graphe avec un contrainte supplémentaire : pas plus de 12 routes par ville, c’est-à-dire un graphe de degré maximal 12.

Le sujet du TP est ici.

Dans un premier temps, on va regarder ce code. Le code à compléter est là et un corrigé est disponible là