polygon-circle graph

English

Noun

polygon-circle graph (plural polygon-circle graphs)

  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), 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.
This article is issued from Wiktionary. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.