Граф многоугольников на окружности

Слева — множество многоугольников, вписанных в окружность. Справа — соответствующий граф многоугольников на окружности (граф пересечений многоугольников). Внизу — чередующаяся последовательность многоугольников по окружности.

В теории графов графом многоугольников на окружности или паутиной называется граф пересечений, в котором каждая вершина соответствует многоугольнику с вершинами, лежащими на окружности, а рёбра, соединяющие две вершины графа, задаются пересечением двух многоугольников, соответствующих этим вершинам. Графы многоугольников на окружности предложены впервые в 1988 году Михаэлем Феллоузом.

Граф многоугольников на окружности можно задать «чередующейся последовательностью». Такую последовательность можно получить разорвав окружность в произвольном месте и перечислив вершины многоугольников, идя вдоль окружности. Такая последовательность единственна.

Распознавание

М. Кёбе (M. Koebe) объявил об алгоритме распознавания графа за полиномиальное время, но этот алгоритм нигде не был опубликован. Такой алгоритм впервые опубликовали Пергель (M. Pergel) и Краточвил (J. Kratochvíl).

Литература

• J. P. Spinrad. Efficient Graph Representations. American Mathematical Society, 2003.