Граф многоугольников на окружности (Ijgs bukikrikl,untkf ug ktjr'ukvmn)

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

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

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

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

Примечания

↑ M. Koebe. On a new class of intersection graphs // Proceedings of the Fourth Czechoslovak Symposium on Combinatorics Prachatice. — 1990. — P. 141—143.
↑ M. Pergel. Special Graph Classes and Algorithms on Them. Doctoral Thesis, 2007.

Литература

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

[1] M. Koebe. On a new class of intersection graphs // Proceedings of the Fourth Czechoslovak Symposium on Combinatorics Prachatice. — 1990. — P. 141—143.

[2] M. Pergel. Special Graph Classes and Algorithms on Them. Doctoral Thesis, 2007.

[1]

[2]