complexity-theory - 边缘添加的复杂性（平面图）？

Question

我创建了一个在顶点之间添加边的程序。目标是在不交叉的情况下添加尽可能多的边（即平面图）。复杂性是什么？

尝试：由于我使用深度优先搜索，我认为它是 O(n+m)，其中 n 是节点，m 是边缘。

此外，如果我们将边数绘制为 n 的函数，它会是什么样子？

Answer 1

您的第一个问题无法回答，因为您没有描述算法。

对于第二个问题，任何具有 v ≥ 3 个顶点的最大平面图都恰好有 3v - 6 条边。