Polygon-circle graph

Contracting an edge of a polygon-circle graph results in another polygon-circle graph. 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. Alternatively, in the alternating sequence representing the original graph, combining the subsequences representing the endpoints of the contracted edge into a single subsequence produces an alternating sequence representation of the contracted graph. 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. ==Recognition==

M. Koebe announced a polynomial time recognition algorithm; however, his preliminary version had "serious errors" and a final version was never published. It is also NP-complete to determine whether a given graph can be represented as a polygon-circle graph with at most vertices per polygon, for any . ==Related graph families==

The polygon-circle graphs are a generalization of the circle graphs, which are intersection graphs of the chords of a circle, and the trapezoid graphs, intersection graphs of trapezoids that all have their vertices on the same two parallel lines. They also include the circular arc graphs. 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. ==References==