Publication at Faculty of Mathematics and Physics |
2007
Abstract
We provide a polynomial reduction showing NP=completeness for the recognition problem of intersection graphs of convex polygons inscribed in the circle (Polygon=circle graphs) and as well for class of intersection graphs of filaments above intervals on a line. Moreover we show that between these two classes no polynomially recognizable class can be sandwiched.