# Colloquium of the Department and the PhD Program

## title

*Problems on Geometric Intersection Graphs*

## speaker

## date & place

Wednesday, 16.05.2012, 15:15 h

Room C 252

## abstract

Geometric intersection graphs encode the intersection relationship
between geometric objects. Among those are the classes of intersection
graphs of simple sets in the plane, such as disks, polygons, or line
segments.
Questions of interest on these graphs are of various types. For
instance one can ask about concise encodings of these graphs; or
whether some graphs - say, planar graphs - can always be drawn as
intersection graphs of some objects. Also, the computational
complexity of standard optimization problems may change when
restricted to those graphs.
We will first give a brief survey of the current knowledge, including
contributions from the graph drawing and discrete geometry
communities. Then we will outline a recent NP-hardness proof for the
following problem: given a set of line segments in the plane, find a
largest subset of pairwise intersecting segments. This solves a
21-year old open problem posed by Kratochvíl and Nešetřil.