See by year See by month Jump to month

Laszlo Szekely: Variants of the biplanar crossing number problem

Download as iCal file
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
Fabila-Monroy, Yuga Higashikawa, Raimund Seidel, Josef Tkadlec, and
Alexandra Wesolek.

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013