University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program


Problems on Geometric Intersection Graphs


Prof. Dr. Jean Cardinal, Université Libre de Bruxelles
Brussels, Belgium

date & place

Wednesday, 16.05.2012, 15:15 h
Room C 252


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.