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.