| Part ofa series on | ||||
| Network science | ||||
|---|---|---|---|---|
 | ||||
| Network types | ||||
| Graphs | ||||
| ||||
| Models | ||||
| ||||
| ||||
Geometric graph theory in the broader sense is a large and amorphous subfield ofgraph theory, concerned withgraphs defined bygeometric means. In a stricter sense, geometric graph theory studiescombinatorial and geometric properties of geometric graphs, meaning graphs drawn in theEuclidean plane with possibly intersecting straight-lineedges, andtopological graphs, where the edges are allowed to be arbitrary continuous curves connecting thevertices; thus, it can be described as "the theory of geometric and topological graphs" (Pach 2013). Geometric graphs are also known asspatial networks.
Aplanar straight-line graph is a graph in which the vertices are embedded as points in theEuclidean plane, and the edges are embedded as non-crossingline segments.Fáry's theorem states that anyplanar graph may be represented as a planar straight line graph. Atriangulation 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 theDelaunay 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.
The 1-skeleton of apolyhedron orpolytope 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 anyk-dimensional convex polytope is ak-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 thepolyhedral graphs.
AEuclidean graph is a graph in which the vertices represent points in the plane, and each edge is assigned the length equal to the Euclidean distance between its endpoints. TheEuclidean minimum spanning tree is theminimum spanning tree of a Euclideancomplete graph. It is also possible to define graphs by conditions on the distances; in particular, aunit distance graph is formed by connecting pairs of points that are a unit distance apart in the plane. TheHadwiger–Nelson problem concerns thechromatic number of these graphs.
Anintersection 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. When the sets are geometric objects, the result is a geometric graph. For instance, the intersection graph of line segments in one dimension is aninterval graph; the intersection graph of unit disks in the plane is aunit disk graph. TheCircle packing theorem 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.
ALevi 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. The Levi graphs ofprojective configurations lead to many importantsymmetric graphs andcages.
Thevisibility 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.
Apartial cube is a graph for which the vertices can be associated with the vertices of ahypercube, in such a way that distance in the graph equalsHamming distance 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 ahyperplane arrangement, can be represented as partial cube graphs. An important special case of a partial cube is the skeleton of thepermutohedron, 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 includingmedian graphs have related definitions involving metric embeddings (Bandelt & Chepoi 2008).
Aflip 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 theassociahedron orStasheff polytope. The flip graph of theregular triangulations of a point set (projections of higher-dimensional convex hulls) can also be represented as a skeleton, of the so-calledsecondary polytope.
Media related toGeometric graph theory at Wikimedia Commons