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:

---

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