Algorithme pour transformer un graphe en un graphe planaire

Bonjours à tous•tes,

J'essaye de calculer la complexité d'un algorithme transformant un graphe quelconque en un graphe planaire, via l'utilisation des barycentres.

Voici l'algorithme :

Code :

Sélectionner tout -Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
Fonction G = planaire(G)
Tant que G n'est pas planaire faire 
     pour tous 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

Voici mon calcul concernant l'algorithme dont je suis pas certains :

Premièrement l'algorithme ne précise pas si l'entrée prend uniquement des graphes quelconque ou s'il peut également prendre des graphes déjà planaire. Dans ce cas :

• Meilleur cas (= graphe planaire en entrée) = C(0) (aucune opérations de complexité n'est effectué)
• Pire cas (= graphe non planaire en entrée) : il y a alors deux sous cas
  
  • le graphe peut devenir planaire : il y a donc 2 affectations (V et M) et 1 comparaison. De plus il y a 1/q * n déplacement, où q = probabilité que la condition soit remplie. La complexité dans ce cas-ci est alors, C = 3n + 1/q * n
  • le graphe ne peut pas devenir planaire : la complexité est infinie (boucle infinie)
  
  

Dans un soucis de simplification pour calculer la complexité moyenne de l'algorithme, je décide de supprimer le cas où le graphe ne peut pas devenir planaire.
Ainsi, C_moyenne = C_min + C_max
= 0 + 3n + 1/q * n
= 3n + 1/q * n
= O(n)

Qu'en pensez-vous ?
Merci pour votre aide

On dirait la résolution de sat 3 avec un graphe planaire