complexity-theory - エッジ追加の複雑さ（平面グラフ）？

Question

頂点間にエッジを追加するプログラムを作成しました。目標は、エッジを交差させずにできるだけ多くのエッジを追加することです（つまり、平面グラフ）。複雑さは何ですか？

試行：深さ優先探索を使用したので、O（n + m）であると思います。ここで、nはノード、mはエッジです。

また、エッジの数をnの関数としてプロットすると、どのようになりますか？