Complexité pour l'ajout de bord (graphique plan)?

Question

J'ai créé un programme qui ajoute des arêtes entre les sommets. Le but est d'ajouter autant d'arêtes que possible sans les croiser (c.-à-d. Graphe planaire). Quelle est la complexité? Tentative: Puisque j'ai utilisé la première recherche de profondeur, je pense que c'est O (n + m) où n est le nœud et m est le bord.

De plus, si nous représentons le nombre d'arêtes en fonction de n, à quoi ressemblera-t-il?

Answer 1

Votre première question est impossible à répondre, puisque vous n'avez pas décrit l'algorithme. Pour votre deuxième question, tout graphe planaire maximal avec v ≥ 3 sommets a exactement 3 - 6 arêtes.