CODEWITHSUNDEEP
graph-algorithm
Paler
Paler

Reputation: 349

Maximum number of non-intersecting edges

There are N nodes in a plane and they are connected by straight lines called edges. What is the maximum number of non-intersecting edges?

Upvotes: 0

Views: 571

Answers (1)

gue
gue

Reputation: 2028

I think the answer you are looking for is 2*N - 3. This is the number of edges if the N nodes are triangulated, with bounded triangles. Then every bounded face forms a triangle, i.e., no more non-intersecting edges can be added.

Starting from 3 nodes it is easy to see that we can add at most three bounded non-intersecting edges. Then for every additional node we can add two more edges.

If the unbounded face is triangulated as well, i.e., unbounded edges are allowed, then there are 3*N - 3 edges.

Upvotes: 1

Related Questions