Geometric graph theory in the broader sense is a large and amorphous subfield of

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 conn ...

, concerned with graphs defined by

geometric Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...

means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

with possibly intersecting straight-line

edges Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices, thus it is "the theory of geometric and topological graphs" (Pach 2013). Geometric graphs are also known as spatial networks.

Different types of geometric graphs

A '' planar straight-line graph'' is a graph in which the vertices are embedded as points in the

, and the edges are embedded as non-crossing

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 ...

s. Fáry's theorem states that any

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 cro ...

may be represented as a planar straight line graph. A

triangulation In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle ...

is a planar straight line graph to which no more edges may be added, so called because every face is necessarily a triangle; a special case of this is the

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...

, 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. The 1-

skeleton A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...

of a

polyhedron In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all on ...

polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...

is the set of vertices and edges of said polyhedron or polytope. The skeleton of any convex polyhedron is a planar graph, and the skeleton of any ''k''-dimensional convex polytope is a ''k''-connected graph. Conversely, Steinitz's theorem states that any 3-connected planar graph is the skeleton of a convex polyhedron; for this reason, this class of graphs is also known as the

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-c ...

s. 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 A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

of a Euclidean

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

. It is also possible to define graphs by conditions on the distances; in particular, a

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these gr ...

is formed by connecting pairs of points that are a unit distance apart in the plane. The

Hadwiger–Nelson problem In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color ...

concerns the

chromatic number 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 graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of these graphs. An

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 ...

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. 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 In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. ...

; the intersection graph of unit disks in the plane is a unit disk graph. The

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 gen ...

states that the intersection graphs of non-crossing circles are exactly the planar graphs. Scheinerman's conjecture (proven in 2009) states that every planar graph can be represented as the intersection graph of line segments in the plane. A

Levi graph In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we ...

of a family of points and lines has a vertex for each of these objects and an edge for every incident point-line pair. The Levi graphs of projective configurations lead to many important symmetric graphs and cages. 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. It is not known how to test efficiently whether an undirected graph can be represented as a visibility graph. A

partial cube In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cub ...

is a graph for which the vertices can be associated with the vertices of a

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions ...

, in such a way that distance in the graph equals

Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...

between the corresponding hypercube vertices. 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. 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. Several other important classes of graphs including

median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pai ...

s have related definitions involving metric embeddings . 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 In mathematics, an associahedron is an -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of letters, and the edges correspond to single application ...

or Stasheff polytope. The flip graph of the 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''.

References

* * * *

External links

*{{Commons category-inline

Different types of geometric graphs

See also

References

External links