In graph theory, a graph of polygons on a circle or a web is an intersection graph in which each vertex corresponds to a polygon with vertices lying on the circle, and the edges connecting two vertices of the graph are given by the intersection of two polygons corresponding to these vertices. Graphs of polygons on a circle are proposed for the first time in 1988 by Michael Fellows .
The graph of polygons on a circle can be set to “alternating sequence”. Such a sequence can be obtained by breaking a circle in an arbitrary place and listing the vertices of polygons, going along a circle. Such a sequence is unique.
Recognition
M. Koebe announced a graph recognition algorithm in polynomial time [1] , but this algorithm was not published anywhere. This algorithm was first published by Pergel (M. Pergel) and Kratochvil (J. Kratochvíl) [2] .
Notes
- ↑ M. Koebe. 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.
Literature
- JP Spinrad. Efficient Graph Representations . American Mathematical Society, 2003.