Polygon-circle Graph
In the mathematics, mathematical discipline of graph theory, a polygon-circle graph is an intersection graph of a set of convex polygons all of whose vertex (geometry), vertices lie on a common circle. These graphs have also been called spider graphs. This class of graphs was first suggested by Michael Fellows in 1988, motivated by the fact that it is closed under edge contraction and induced subgraph operations.. A polygon-circle graph can be represented as an "alternating sequence". Such a sequence can be gained by perturbing the polygons representing the graph (if necessary) so that no two share a vertex, and then listing for each vertex (in circular order, starting at an arbitrary point) the polygon attached to that vertex. Closure under induced minors Edge contraction, Contracting an edge of a polygon-circle graph results in another polygon-circle graph. A geometric representation of the new graph may be formed by replacing the polygons corresponding to the two endpoints ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]