Lectures and Colloquia during the semester

**Monday, October 23, 2006**

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

Math building - Room MA 041

** Lecture - 14:15**

### Jan Kratochvil - Univerzity Karlovy, Prag

### Geometric Intersection Graphs:
A survey of Recent Results and Open Problems

*Abstract:*

Geometric intersection graphs are studied both for their practical
motivations and for interesting theoretical properties. We will
survey
recent results concerning recognition of certain classes of
intersection graphs (namely so called string graphs and
polygon-circle
graphs), and the related problem of sizes of their representations.
We
also mention the development in some other long standing open
problems
in the area (representability of planar and co-planar graphs,
complexity of some optimization problems etc.).

**Colloquium - 16:00**

### Martin Pergel - Univerzity Karlovy, Prag

### Complexity of PC-graph recognition

*Abstract:*

Polygon-circle graphs (shortly PC-graphs), defined as intersection
graphs of polygons inscribed into a circle, form an intersection
class generalizing many other classes (i. e., interval, circle,
circular-arc, chordal graphs and cactus-subtree graphs).
Polynomial-time algorithms solving several (generally NP-hard)
optimization problems restricted to PC-graphs are known (and even
for graphs of interval filaments, that generalize this class).
Most of these algorithms require an appropriate (PC-)
representation,
and therefore it is important to explore whether such a
representation
can be found efficiently. We introduce a polynomial-time algorithm
for recognition of PC-graphs with girth at least 5 and show that
the general PC-graph recognition is an NP-complete problem.