Leírás
Biplanar crossing number problems investigate the multiplicative factor with which the crossing number of graphs decrease, if we are allowed to draw the graph on two planes instead of one plane. The problem, which came from VLSI, exists in several variants that will be reviewed:
(a) locations of vertices are unrelated in the two planes, edges are
plane curves
(b) locations of vertices are unrelated in the two planes, edges are
straight line segments
(c) locations of vertices are identical in the two planes, edges are
straight line segments.
The new result is about the (c) variant. Pick independently n random points in the unit square from the uniform distribution. Edges of the complete graph K_n, with the vertex set selected above, will be drawn in straight line segments. We want to make a policy, which decides for every line segment, in which of the two planes it will be drawn. A kind of a random policy would halve in expectation the number of crossings.With a better policy, we reduce by a factor of 9/25 the expectation.
The new result is joint work with Sergio Cabello, Eva Czabarka, Ruy
Fabila-Monroy, Yuga Higashikawa, Raimund Seidel, Josef Tkadlec, and
Alexandra Wesolek.