In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics and Computer science, a graph is the basic object of study in Graph theory. Geometry ( Greek γεωμετρία; geo = earth metria = measure is a part of Mathematics concerned with questions of size shape and relative position Geometric graph theory is a specialization of graph theory that studies geometric graphs. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects Notable geometric graphs and geometric graph theory problems include the following.
- A planar straight line graph is a graph in which the vertices are embedded as points in the Euclidean plane, and the edges are embedded as non-crossing line segments. Planar straight-line graph ( PSLG) is a term used in Computational geometry for an embedding of a Planar graph in the plane such that Euclidean geometry is a mathematical system attributed to the Greek Mathematician Euclid of Alexandria. In Geometry, a line segment is a part of a line that is bounded by two distinct end points, and contains every point on the line between its end points Fáry's theorem states that any planar graph may be represented as a planar straight line graph. Fáry's theorem states that any simple Planar graph can be drawn without crossings so that its edges are straight Line segments That is the ability to Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden A triangulation is a planar straight line graph to which no more edges may be added; a special case of this is the Delaunay triangulation, a graph defined from a set of points in the plane by connecting two points with an edge whenever there exists a circle containing only those two points. A triangulation of a set of points P in the Plane is a triangulation of the Convex hull of P, with all points from P being In Mathematics, and Computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT( P)
- The 1-skeleton of a polyhedron or polytope is the set of vertices and edges of the polytope. This article is not about the Topological skeleton concept of Computer graphics In Mathematics, particularly in Algebraic topology What is a polyhedron? We can at least say that a polyhedron is built up from different kinds of element or entity each associated with a different number of dimensions In Geometry, polytope is a generic term that can refer to a two-dimensional Polygon, a three-dimensional Polyhedron, or any of the various generalizations The skeleton of any convex polyhedron is a planar graph, and the skeleton of any k-dimensional convex polytope is a k-connected graph. In Graph theory, a graph G with vertex set V(G is said to be Conversely, Ernst Steinitz proved that any 3-connected planar graph is the skeleton of a convex polyhedron. Ernst Steinitz ( June 13, 1871 – September 29 1928) was a German Mathematician.
- A Euclidean graph is a graph in which the vertices represent points in the plane, and the edges are assigned lengths equal to the Euclidean distance between those points. The Euclidean minimum spanning tree is the minimum spanning tree of a Euclidean complete graph. The Euclidean minimum spanning tree or EMST is a Minimum spanning tree of a set of points in the plane (or more generally in \Bbb{R}^n Given a connected, Undirected graph, a spanning tree of that graph is a Subgraph which is a tree and connects all the vertices together In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an It is also possible to define graphs by conditions on the distances; in particular, a unit distance graph is formed by connecting pairs of points that are a unit distance apart in the plane. In Mathematics, and particularly Geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane The Hadwiger–Nelson problem concerns the chromatic number of these graphs. In Geometric graph theory, the Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a
- An intersection graph is a graph in which each vertex is associated with a set and in which vertices are connected by edges whenever the corresponding sets have a nonempty intersection. In the mathematical area of Graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets When the sets are geometric objects, the result is a geometric graph. For instance, the intersection graph of line segments in one dimension is an interval graph; the intersection graph of unit disks in the plane is a unit disk graph. In Graph theory, an interval graph is the Intersection graph of a set of intervals on the real line In Geometric graph theory, a unit disk graph is the Intersection graph of a family of Unit circles in the Euclidean plane. The Circle packing theorem states that the intersection graphs of non-crossing circles are exactly the planar graphs. 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 Scheinerman's conjecture states that every planar graph can be represented as the intersection graph of line segments in the plane. In Mathematics, Scheinerman's conjecture states that every Planar graph is the Intersection graph of a set of Line segments in the plane
- A Levi graph of a family of points and lines has a vertex for each of these objects and an edge for every incident point-line pair. In Combinatorics a Levi graph or incidence graph is a Bipartite graph associated with an Incidence structure. The Levi graphs of projective configurations lead to many important symmetric graphs and cages. In Mathematics, specifically Projective geometry, a configuration consists of a finite set of points and a finite set of lines such that each point is incident to In Graph theory a graph is symmetric or arc transitive if it is both vertex transitive and edge transitive. In the mathematical area of Graph theory, a cage is a Regular graph that has as few vertices as possible for its girth.
- The visibility graph of a closed polygon connects each pair of vertices by an edge whenever the line segment connecting the vertices lies entirely in the polygon. A visibility graph is a graph of intervisible locations Each node or vertex in the graph represents a point location and each edge represents a It is not known how to test efficiently whether an undirected graph can be represented as a visibility graph.
- A partial cube is a graph for which the vertices can be associated with the vertices of a hypercube, in such a way that distance in the graph equals Hamming distance between the corresponding hypercube vertices. In Geometry, a hypercube is an n -dimensional analogue of a square ( n = 2 and a Cube ( n = 3 Examples The Hamming distance between 1011101 and 1001001 Many important families of combinatorial structures, such as the acyclic orientations of a graph or the adjacencies between regions in a hyperplane arrangement, can be represented as partial cube graphs. In Geometry and Combinatorics, an arrangement of hyperplanes is a finite set A of Hyperplanes in a linear, affine, or An important special case of a partial cube is the skeleton of the permutohedron, a graph in which vertices represent permutations of a set of ordered objects and edges represent swaps of objects adjacent in the order. The truncated octahedron is an Archimedean solid. It has 8 regular hexagonal faces 6 regular square faces 24 vertices and 36 edges Several other important classes of graphs including median graphs have related definitions involving metric embeddings (Bandelt and Chepoi). In Mathematics, and more specifically Graph theory, a median graph is an Undirected graph in which any three vertices a, b
- A flip graph is a graph formed from the triangulations of a point set, in which each vertex represents a triangulation and two triangulations are connected by an edge if they differ by the replacement of one edge for another. It is also possible to define related flip graphs for partitions into quadrilaterals or pseudotriangles, and for higher dimensional triangulations. The flip graph of triangulations of a convex polygon forms the skeleton of the associahedron or Stasheff polytope. The flip graph of regular triangulations of a point set (projections of higher dimensional convex hulls) can also be represented as a skeleton, of the so-called secondary polytope.
See also
References
- Bandelt, Hans-Jürgen; Chepoi, Victor. In Mathematics topological graph theory is a branch of Graph theory. "Metric graph theory and geometry: a survey". Contemp. Math. : to appear.
- Pach, János, ed. (2004). Towards a Theory of Geometric Graphs. Contemporary Mathematics, no. 342, American Mathematical Society.
- Pisanski, Tomaž; Randić, Milan (2000). Tomaž (Tomo Pisanski (b May 24, 1949 in Ljubljana Slovenia) is a Slovenian Mathematician working mainly in Graph theory "Bridges between geometry and graph theory". Gorini, C. A. (Ed. ) Geometry at Work: Papers in Applied Geometry: 174–194, Washington, DC: Mathematical Association of America.
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic