Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 03, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Jean Cardinal (Université Libre de Bruxelles)
Ray intersection graphs are intersection graphs of rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a ray intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochvil and Nesetril. This is joint work with Sergio Cabello and Stefan Langerman.
Automatic MiSe System Software Version 1.4803M | admin login