Problem 58389. Minimum number of crossings in a complete graph
A complete graph may be drawn in different ways, such that the number of line crossings differs between drawings.
To date, the question of how to draw the graph so as to minimize the number of crossings remains unsolved.
Nevertheless, an upper bound can be calculated for the number of crossings, based on the number of vertices in the graph.
Given the number of vertices, n, calculate the upper bound, b, for the minimum number of line crossings in the resulting complete graph.
Example:
n = 6;
b = 3
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers8
Suggested Problems
-
Select every other element of a vector
31636 Solvers
-
95 Solvers
-
Calculate the area of a triangle between three points
2711 Solvers
-
Operate on matrices of unequal, yet similar, size
184 Solvers
-
Magic is simple (for beginners)
8416 Solvers
More from this Author45
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!