Department of
Applied
Mathematics

On Recognition of PC-graphs

Martin Pergel

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). 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.