On 16.11.2006 at 12:20 in S5, there is the following noon lecture:
On Recognition of PC-graphs
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). 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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010