In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

discipline of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a polygon-circle graph is an

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

of a set of

convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is ...

s 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 Michael Ralph Fellows AC HFRSNZ MAE (born June 15, 1952 in Upland, California) is a computer scientist and the Elite Professor of Computer Science in the Department of Informatics at the University of Bergen, Norway as of January 2016. Biogra ...

in 1988, motivated by the fact that it is closed under

edge contraction In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...

and

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

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 (if necessary) so that no two share a vertex, and then listing for each vertex (in circular order, starting at an arbitrary point) the polygon attached to that vertex.

Closure under induced minors

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 In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...

. 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

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 In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

. 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 graph In graph theory, a circle graph is the intersection graph of a Chord diagram (mathematics), chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of Chord (geometry), chords of a circle such tha ...

s, 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 graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

s, but they are near-perfect, in the sense that their

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

s can be bounded by an (exponential) function of their

clique number In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of t ...

s..

References

{{reflist Intersection classes of graphs NP-complete problems