Talk by Tillmann Miltzow – Københavns Universitet

Videresend til en ven Resize Print kalender-ikon Bookmark and Share

Datalogisk Institut, DIKU > Begivenhedsmappen > Begivenheder 2017 > Talk by Tillmann Miltzow

Talk by Tillmann Miltzow

Title

Intersection graphs of rays and grounded segments

Abstract

We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that:

  1. Intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class,  
  2. Not every intersection graph of rays is an intersection graph of downward rays, and
  3. Not every intersection graph of rays is an outer segment graph.

The first result answers an open problem posed by Cabello and Jejcic. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characterize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.

Biography

Tillmann Miltzow is a postdoc at the Hungarian Academy of Science in Budapest in the Parameterized Complexity group of Dániel Marx.(MTA SZTAKI) He did his phd in Berlin under the supervision of Günter Rote at the department of Computer Science of the Free University of Berlin(FUB). His research interests lie mainly in computational geometry, but he also worked on combinatorial problems in the field of social choice, games in abstract graphs, geometric and abstract counting problems, graph drawing problems, approximation algorithms, combinatorial and algorithmic reconfiguration problems.

Host: Mikkel Thorup