Problem 58384. Minimum number of crossings in a complete bipartite graph
A complete bipartite 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 elements in each of the two sets comprising the graph's vertices.
Given the number of elements in each set, m and n, calculate the upper bound, b, for the minimum number of line crossings in the resulting complete bipartite graph.
Example:
m = 3;
n = 4;
b = 2
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers8
Suggested Problems
-
16510 Solvers
-
Back to basics 2 - Function Path
181 Solvers
-
Matrix which contains the values of an other matrix A at the given locations.
227 Solvers
-
Sum the entries of each column of a matrix which satisfy a logical condition.
158 Solvers
-
Right Triangle Side Lengths (Inspired by Project Euler Problem 39)
1720 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!