Polygon-circle graph

Polygon-circle graph is a type of an intersection graph, where each vertex is represented as a polygon and edge as an intersection of two polygons representing those vertices, enclosed by a bounding circle. All corners of all polygons lie on the bounding circle. They were first suggested by Michael Fellows in 1988.

Polygon-circle graph can be represented as "alternating sequence". Such sequence can be gained by cutting the bounding circle in an arbitrary point and listing the polygons, as we go along. Such sequence is unique.

They can also be referred to as "spider graphs".

Recognition

M. Koebe announced polynomial time recognition algorithm^[1], but it was never published. Algorithm was first published by M. Pergel and J. Kratochvíl^[2].

References

^ M. Koebe. On a new class of intersection graphs in Proceedings of the Fourth Czechoslovak Symposium on Combinatorics Prachatice, pages 141 - 143, 1990.
^ 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 in Proceedings of the Fourth Czechoslovak Symposium on Combinatorics Prachatice, pages 141 - 143, 1990.

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

[1]

[2]