Lectures and Colloquia during the semester
Monday, October 23, 2006
Technische Universität Berlin
Straße des 17. Juni 136
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
recent results concerning recognition of certain classes of
intersection graphs (namely so called string graphs and
graphs), and the related problem of sizes of their representations.
also mention the development in some other long standing open
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-)
and therefore it is important to explore whether such a
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.