Polygon-circle graph (original) (raw)
In the mathematical discipline of graph theory, a polygon-circle graph is an intersection graph of a set of convex polygons all of whose 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.
| Property | Value |
|---|---|
| dbo:abstract | In the mathematical discipline of graph theory, a polygon-circle graph is an intersection graph of a set of convex polygons all of whose 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. (en) В теории графов графом многоугольников на окружности или паутиной называется граф пересечений, в котором каждая вершина соответствует многоугольнику с вершинами, лежащими на окружности, а рёбра, соединяющие две вершины графа, задаются пересечением двух многоугольников, соответствующих этим вершинам. Графы многоугольников на окружности предложены впервые в 1988 году Михаэлем Феллоузом. Граф многоугольников на окружности можно задать «чередующейся последовательностью». Такую последовательность можно получить разорвав окружность в произвольном месте и перечислив вершины многоугольников, идя вдоль окружности. Такая последовательность единственна. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Polygon-circle_graph.svg?width=300 |
| dbo:wikiPageID | 28174525 (xsd:integer) |
| dbo:wikiPageLength | 5493 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032297127 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Induced_subgraph dbr:Mathematics dbr:Chromatic_number dbr:NP-complete dbr:Convex_hull dbr:Convex_polygon dbr:Clique_number dbr:Perfect_graph dbr:Trapezoid_graph dbr:Graph_theory dbr:Intersection_graph dbc:Intersection_classes_of_graphs dbr:Edge_contraction dbr:Circle_graph dbr:Michael_Fellows dbr:Vertex_(geometry) dbr:Circular_arc_graph dbr:File:Polygon-circle_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:Center dbt:Math dbt:Mvar dbt:Redirect dbt:Reflist |
| dct:subject | dbc:Intersection_classes_of_graphs |
| gold:hypernym | dbr:Type |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:WikicatGraphs yago:VisualCommunication106873252 |
| rdfs:comment | In the mathematical discipline of graph theory, a polygon-circle graph is an intersection graph of a set of convex polygons all of whose 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. (en) В теории графов графом многоугольников на окружности или паутиной называется граф пересечений, в котором каждая вершина соответствует многоугольнику с вершинами, лежащими на окружности, а рёбра, соединяющие две вершины графа, задаются пересечением двух многоугольников, соответствующих этим вершинам. Графы многоугольников на окружности предложены впервые в 1988 году Михаэлем Феллоузом. (ru) |
| rdfs:label | Polygon-circle graph (en) Граф многоугольников на окружности (ru) |
| owl:sameAs | freebase:Polygon-circle graph yago-res:Polygon-circle graph wikidata:Polygon-circle graph dbpedia-ru:Polygon-circle graph https://global.dbpedia.org/id/4u41P |
| prov:wasDerivedFrom | wikipedia-en:Polygon-circle_graph?oldid=1032297127&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Polygon-circle_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Polygon-circle_graph |
| is dbo:wikiPageRedirects of | dbr:Spider_graph |
| is dbo:wikiPageWikiLink of | dbr:List_of_circle_topics dbr:Intersection_graph dbr:Circle_graph dbr:Spider_graph dbr:Χ-bounded |
| is foaf:primaryTopic of | wikipedia-en:Polygon-circle_graph |
