Bonjour je vous contacte par rapport à un exercice que je trouve dur au niveau de la compléxité

Soit l’algorithme de construction de graphe planaire suivant
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
 
fonctionG = planaire(G)
      tant que G n’est pas planaire faire
                  pour tout x sommet de G faire
                          V = liste des voisins de x
                          M = barycentre des sommets de V
                          si on diminue le nombre d’intersections d’arcs
                                 alors placer x en M
                  fin si
      fin faire
fin faire
Les questions sont les suivantes : Quelle est la complexité de cet algorithme ? Finit-il toujours ?

En espérant être aidé