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

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

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

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

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

Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (10 декабря 2013)