polygon-circle graph

English

Noun

polygon-circle graph (plural polygon-circle graphs)

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

1. (graph theory) A graph (set of connected points) in which each vertex corresponds to a convex polygon circumscribed in a common circle, and in which (graph) vertices are adjacent iff their corresponding polygons intersect geometrically.
   • 2004, Jan Kratochvíl, Martin Pergel, “Two Results on Intersection Graphs of Polygons”, in Giuseppe Liotta, editor, GD 2003 International Symposium on Graph Drawing (Lecture Notes in Computer Science)‎^[1], volume 2912, Springer-Verlag, →DOI, →ISBN, page 60:

     A common generalization of these two [circle graphs and circular arc graphs] are polygon-circle graphs, intersection graphs of convex polygons inscribed to the circle. This class was first suggested by M. Fellows [personal communication with the first author] in 1988, when it was pointed out that this class of graphs is closed under taking induced minors.