В теории графов графом многоугольников на окружности или паутиной называется граф пересечений, в котором каждая вершина соответствует многоугольнику с вершинами, лежащими на окружности, а рёбра, соединяющие две вершины графа, задаются пересечением двух многоугольников, соответствующих этим вершинам. Графы многоугольников на окружности предложены впервые в 1988 году .
Граф многоугольников на окружности можно задать «чередующейся последовательностью». Такую последовательность можно получить разорвав окружность в произвольном месте и перечислив вершины многоугольников, идя вдоль окружности. Такая последовательность единственна.
Распознавание М. Кёбе (M. Koebe) объявил об алгоритме распознавания графа за полиномиальное время, но этот алгоритм нигде не был опубликован. Такой алгоритм впервые опубликовали Пергель (M. Pergel) и Краточвил (J. Kratochvíl)M. Pergel. Special Graph Classes and Algorithms on Them. Doctoral Thesis, 2007..
Примечания
Литература J. P. Spinrad. Efficient Graph Representations. American Mathematical Society, 2003.
Категория:Геометрические графы