Polygon-circle graph


In the mathematical discipline of graph theory, a polygon-circle graph is an intersection graph of a set of convex polygons all of whose vertices lie on a common circle. These graphs have also been called spider graphs. 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 polygon-circle graph can be represented as an "alternating sequence". Such a sequence can be gained by perturbing the polygons representing the graph so that no two share a vertex, and then listing for each vertex the polygon attached to that vertex.

Closure under induced minors

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. Martin Pergel later proved that the problem of recognizing these graphs is NP-complete.
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 function of their clique numbers.