Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 15, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Marek Sulovský
We address the following question: What is the minimal number of crossings (denoted by crr(K_n)) in a straight-line drawing of K_n in the plane? This has been studied in recent years and the currently best asymptotic bounds for crr(K_n) are: 0.379 (n \choose 4) \leq crr(K_n) \leq 0.381 (n \choose 4). The talk will summarize two recent results,  and , giving lower bounds on rectilinear crossing number via proving that minimizing examples have a triangular convex hull, and for configurations with this property giving lower bounds on the number of (\leq k)-sets. The lower bound on the crossing number immediately follows from the lower bound on (\leq k)-sets.
 Aichholzer, Garcia, Orden, Ramos: On the structure of sets
attaining rectilinear crossing number (Proc. 22th European Workshop on
Computational Geometry EuroCG '06, pages 43-46).
 Abrego, Balogh, Fernandez-Merchant, Leanos, Salazar: On k-pseudoedges in generalized configurations and the pseudolinear crossing number of Kn (submitted).
Automatic MiSe System Software Version 1.4803M | admin login