|
Intersection Graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. Formal definition Formally, an intersection graph is an undirected graph formed from a family of sets : S_i, \,\,\, i = 0, 1, 2, \dots by creating one vertex for each set , and connecting two vertices and by an edge whenever the corresponding two sets have a nonempty intersection, that is, : E(G) = \. All graphs are intersection graphs Any undirected graph may be represented as an intersection graph. For each vertex of , form a set consisting of the edges incident to ; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Therefore, is the intersection graph of the sets . provide a construction that is more ef ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Intersection Graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. Formal definition Formally, an intersection graph is an undirected graph formed from a family of sets : S_i, \,\,\, i = 0, 1, 2, \dots by creating one vertex for each set , and connecting two vertices and by an edge whenever the corresponding two sets have a nonempty intersection, that is, : E(G) = \. All graphs are intersection graphs Any undirected graph may be represented as an intersection graph. For each vertex of , form a set consisting of the edges incident to ; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Therefore, is the intersection graph of the sets . provide a construction that is more ef ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Trapezoid Graph
In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988. There exists (n\log n) algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique. Definitions and characterizations Given a channel, a pair of two horizontal lines, a trapezoid between these lines is defined by two points on the top and two points on the bottom line. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
String Graph
In graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ..., a string graph is an intersection graph of Plane curve, curves in the plane; each curve is called a "string". Given a Graph (discrete mathematics), graph , is a string graph if and only if there exists a set of curves, or strings, such that the graph having a Vertex (graph theory), vertex for each curve and an edge for each intersecting pair of curves is Graph isomorphism, isomorphic to . Background described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of interval graphs. Later, specified the same idea to electrical networks and printed circuits. The mathematical st ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Line Graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every two edges in that have a vertex in common, make an edge between their corresponding vertices in . The name line graph comes from a paper by although both and used the construction before this. Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the θ-obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph., p. 71. proved that with one exceptional case the structure of a connected graph can be recovered completely from its line graph. Many other properties of line graphs follow by translating the properties of the underlying graph from vertices into edges, and by Whitney's theorem the same t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Existential Theory Of The Reals
In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form \exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n), where the variables X_i are interpreted as having real number values, and where F(X_1,\dots X_n) is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula F, make it become true.. The decision problem for the existential theory of the reals is the problem of finding an algorithm that decides, for each such sentence, whether it is true or false. Equivalently, it is the problem of testing whether a given semialgebraic set is non-empty. This decision problem is NP-hard and lies in PSPACE. Thus it has significantly lower complexity than Alfred Tarski's quantifier elimination procedure for deciding statements in the first-or ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. More formally, a problem ''p'' is called hard for a complexity class ''C'' under a given type of reduction if there exists a reduction (of the given type) from any problem in ''C'' to ''p''. If a problem is both hard for the class and a member of the class, it is complete for that class (for that type of reduction). A problem that is complete for a class ''C'' is said to be C-complete, and the class of all problems complete for ''C'' is denoted C-complete. The first complete class to be defined and the most well known is NP-complete, a class that contains many difficult-to-solve problems that arise in practice. Similarly, a problem hard for a class ''C'' is called C-hard, e.g. NP-hard. Normally, it is assumed that the reduction in question does not have higher computational co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Line Segment
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between its endpoints. A closed line segment includes both endpoints, while an open line segment excludes both endpoints; a half-open line segment includes exactly one of the endpoints. In geometry, a line segment is often denoted using a line above the symbols for the two endpoints (such as \overline). Examples of line segments include the sides of a triangle or square. More generally, when both of the segment's end points are vertices of a polygon or polyhedron, the line segment is either an edge (geometry), edge (of that polygon or polyhedron) if they are adjacent vertices, or a diagonal. When the end points both lie on a curve (such as a circle), a line segment is called a chord (geometry), chord (of that curve). In real or complex vector spa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scheinerman's Conjecture
In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis (1984), following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane . It was proven by . For instance, the graph ''G'' shown below to the left may be represented as the intersection graph of the set of segments shown below to the right. Here, vertices of ''G'' are represented by straight line segments and edges of ''G'' are represented by intersection points. Scheinerman also conjectured that segments with only three directions would be sufficient to represent 3- colorable graphs, and conjectured that analogously every planar graph could be represented using four directions. If a graph is represented with segments having only ''k'' directions and no two segments belong t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Planar Graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection. Plane graphs can be encoded by combinatorial maps or rotation systems. An equivalence class of topologically equivalent drawings on the sphere, usually with additional assumptions such as the absence of isthmuses, is called a pl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circle Packing Theorem
The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in general, on any Riemann surface) whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph: Circle packing theorem: For every connected simple planar graph ''G'' there is a circle packing in the plane whose intersection graph is (isom ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circle Graph
In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other. Algorithmic complexity gives an O(''n''2)-time algorithm that tests whether a given ''n''-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it. A number of other problems that are NP-complete on general graphs have polynomial time algorithms when restricted to circle graphs. For instance, showed that the treewidth of a circle graph can be determined, and an optimal tree decomposition constructed, in O(''n''3) time. Additionally, a minimum fill-in (that is, a chordal graph with as few edges as possible that contains the given circle graph as a subgraph) may be found in O(''n''3) time. has shown that a maximum clique of a circle graph can be found ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Unit Disk
In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1: :D_1(P) = \.\, The closed unit disk around ''P'' is the set of points whose distance from ''P'' is less than or equal to one: :\bar D_1(P)=\.\, Unit disks are special cases of disks and unit balls; as such, they contain the interior of the unit circle and, in the case of the closed unit disk, the unit circle itself. Without further specifications, the term ''unit disk'' is used for the open unit disk about the origin, D_1(0), with respect to the standard Euclidean metric. It is the interior of a circle of radius 1, centered at the origin. This set can be identified with the set of all complex numbers of absolute value less than one. When viewed as a subset of the complex plane (C), the unit disk is often denoted \mathbb. The open unit disk, the plane, and the upper half-plane The function :f(z)=\frac is an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
