







See by year  See by month  Jump to month  

Laszlo Szekely: Variants of the biplanar crossing number problem 



Friday, 19. May 2023, 13:30  14:00


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 FabilaMonroy, Yuga Higashikawa, Raimund Seidel, Josef Tkadlec, and Alexandra Wesolek. 
Back
JEvents v3.1.8 Stable
Copyright © 20062013