[home] - [up]

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

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

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.

[home] - [up] - [top]