Polygon-circle graph

This class of graphs was first suggested by Michael Fellows in 1988, motivated by the fact that it is closed under edge contraction and induced subgraph operations.

A geometric representation of the new graph may be formed by replacing the polygons corresponding to the two endpoints of the contracted edge by their convex hull.

Polygon circle graphs are also closed under induced subgraph or equivalently vertex deletion operations: to delete a vertex, remove its polygon from the geometric representation, or remove its subsequence of points from the alternating sequence.

[1] Martin Pergel later proved that the problem of recognizing these graphs is NP-complete.

[1][5] Polygon-circle graphs are not, in general, perfect graphs, but they are near-perfect, in the sense that their chromatic numbers can be bounded by an (exponential) function of their clique numbers.

On the left a set of polygons inscribed in a circle; on the right the relative Polygon-circle graph (intersection graph of the polygons).
On the bottom the alternating sequence of polygons around the circle.