Polygon-circle graph
Encyclopedia
In the mathematical
discipline of graph theory
, a polygon-circle graph, also called a spider graph, is a type of an intersection graph
, where each vertex
is represented as a polygon
and each 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.
A polygon-circle graph can be represented as an "alternating sequence". Such a 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
discipline of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a polygon-circle graph, also called a spider graph, is a type of an intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
, where each vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
is represented as a polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
and each 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
Michael Fellows
Michael Ralph Fellows is Professor at Charles Darwin University, Australia, and Director of the Parameterized Complexity Research Unit . Fellows is recognized as one of the founders of Parameterized complexity, a complexity framework that uses structure in hard problems for the design and...
in 1988.
A polygon-circle graph can be represented as an "alternating sequence". Such a 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.